数据结构与算法（6

数据结构与算法（6

目录

一、前序遍历

二、中序遍历

三、后序遍历

 前中后序遍历总代码

四、层序遍历（队列实现(主流)）

总代码 

五、层序遍历（链队列实现(自创)）

 总代码

---

二叉树的遍历分为前序、中序、后序以及层序遍历。

前中后序是按照根结点的访问顺序来确定的，前中后序遍历的核心都是递归。

一、前序遍历

访问顺序：根->左->右

普通二叉树遍历（前序）：ABDCG

扩展二叉树遍历（前序）：ABD###C#G##

实现顺序：

1、生成根结点

2、递归遍历左子树

3、递归遍历右子树

代码：

//先序遍历（根->左->右）
void PreOrderTraverse(BiTree* T)
{//空if (T->data == ' ' || T->data == '#'){printf("%c", T->data);return;}//非空printf("%c", T->data);					//访问根结点PreOrderTraverse(T->lchild);		//左子树PreOrderTraverse(T->rchild);		//右子树
}

二、中序遍历

访问顺序：左->根->右

普通二叉树遍历（中序）：DBACG

扩展二叉树遍历（中序）：#D#B#A#C#G#

实现顺序：

1、递归遍历左子树

2、生成根结点

3、递归遍历右子树

代码：

//中序遍历（左->根->右）
void InOrderTraverse(BiTree* T)
{//空if (T->data == ' ' || T->data == '#'){printf("%c", T->data);return;}//非空InOrderTraverse(T->lchild);		//左子树printf("%c", T->data);					//访问根结点InOrderTraverse(T->rchild);		//右子树
}

三、后序遍历

访问顺序：左->右->根

普通二叉树遍历（后序）：DBGCA

扩展二叉树遍历（后序）：##D#B###GCA

实现顺序：

1、递归遍历左子树

2、递归遍历右子树

3、生成根结点

代码：

//后序遍历（左->右->根）
void PostOrderTraverse(BiTree* T)
{int i = 0;//空if (T->data == ' ' || T->data == '#'){printf("%c", T->data);return;}//非空PostOrderTraverse(T->lchild);		//左子树PostOrderTraverse(T->rchild);		//右子树printf("%c", T->data);				//访问根结点
}

 前中后序遍历总代码

//二叉树的遍历
//先序遍历：根左右			中序遍历：左根右			后序遍历：左右根
//(创建默认先序遍历)
#include<stdio.h>
#include<malloc.h>int flag = 0, index = 0;
char str[30];//二叉树结点
typedef struct BiTree
{char data;struct BiTree* lchild, * rchild;
}BiTree;
BiTree* head = NULL;void Init_Bitree()
{head = (BiTree*)malloc(sizeof(BiTree));
}//创建树（先序遍历）
void Create_BiTree(BiTree* T)
{char ch;scanf_s("%c", &ch);//退出递归if (ch == 'n' || flag == 1){flag = 1;return;}//空元素if (ch == ' ' || ch == '#'){T->data = ch;return;}//非空元素T->data = ch;										//构造根结点T->lchild = (BiTree*)malloc(sizeof(BiTree));T->rchild = (BiTree*)malloc(sizeof(BiTree));Create_BiTree(T->lchild);						//构造左子树Create_BiTree(T->rchild);						//构造右子树
}//先序遍历（根->左->右）
void PreOrderTraverse(BiTree* T)
{//空if (T->data == ' ' || T->data == '#'){printf("%c", T->data);return;}//非空printf("%c", T->data);					//访问根结点PreOrderTraverse(T->lchild);		//左子树PreOrderTraverse(T->rchild);		//右子树
}//中序遍历（左->根->右）
void InOrderTraverse(BiTree* T)
{//空if (T->data == ' ' || T->data == '#'){printf("%c", T->data);return;}//非空InOrderTraverse(T->lchild);		//左子树printf("%c", T->data);					//访问根结点InOrderTraverse(T->rchild);		//右子树
}//后序遍历（左->右->根）
void PostOrderTraverse(BiTree* T)
{int i = 0;//空if (T->data == ' ' || T->data == '#'){printf("%c", T->data);return;}//非空PostOrderTraverse(T->lchild);		//左子树PostOrderTraverse(T->rchild);		//右子树printf("%c", T->data);				//访问根结点
}int main()
{Init_Bitree();printf("请按照扩展二叉树前序遍历顺序输入需要创建的二叉树结点：n");Create_BiTree(head);						//创建二叉树flag = 0;printf("n先序遍历：n");PreOrderTraverse(head);							//先序遍历printf("n中序遍历：n");InOrderTraverse(head);							//中序遍历printf("n后序遍历：n");PostOrderTraverse(head);						//后序遍历return 0;
}

四、层序遍历（队列实现(主流)）

访问顺序：逐层从左往右访问。

 思想：利用队列，把根结点入队，再依次出队，再让其左右孩子结点入队，以此类推。

普通二叉树遍历（层序）：ABCDG

扩展二叉树遍历（后序）：ABCD##G 

代码：

//层序遍历
void LevelOrderTraverse(BiTree* N)
{EnQueue(N);								//根元素入队while (Q.front != Q.rear)				//队列不为空{*N = DeQueue();						//队首元素出队（并以它为根，进行遍历）if (N->lchild != NULL)EnQueue(N->lchild);			//入队左结点if (N->rchild != NULL)EnQueue(N->rchild);			//入队右结点cout << N->data;}
}

总代码 

//二叉树的层序遍历（队列）
//先放入根结点，然后判断是否有孩子结点，有则放入队列。
//最后取出队列的首结点，把它作为根继续遍历
//这样就达到了按层依次遍历的效果
//附加内容：二级指针（可以修改地址）
#include<iostream>
#include<malloc.h>
using namespace std;#define MAXSIZE 100
int index = 0;//二叉树
typedef struct BiTree
{char data;struct BiTree* lchild, * rchild;
}BiTree, * pBiTree;
BiTree* head;				//二叉树根结点//队列
typedef struct
{BiTree node[MAXSIZE];int front;int rear;
}Queue;
Queue Q;void Init()
{//二叉树head = (BiTree*)malloc(sizeof(BiTree));head->lchild = NULL;head->rchild = NULL;//队列Q.front = -ar = -1;
}//创建二叉树
void Create_BiTree(pBiTree* N)
{char ch;cin >> ch;if (ch != '#')				//不为空{(*N)->lchild = (BiTree*)malloc(sizeof(BiTree));(*N)->rchild = (BiTree*)malloc(sizeof(BiTree));Create_BiTree(&(*N)->lchild);(*N)->data = ch;Create_BiTree(&(*N)->rchild);}else{(*N) = NULL;			//地址赋空			（二级指针，可以改变地址）}
}//入队
void EnQueue(BiTree* node)
{Q.node[+&#ar] = *node;
}//出队
BiTree DeQueue()
{de[++Q.front];
}//层序遍历
void LevelOrderTraverse(BiTree* N)
{EnQueue(N);								//根元素入队while (Q.front != Q.rear)				//队列不为空{*N = DeQueue();						//队首元素出队（并以它为根，进行遍历）if (N->lchild != NULL)EnQueue(N->lchild);			//入队左结点if (N->rchild != NULL)EnQueue(N->rchild);			//入队右结点cout << N->data;}
}int main()
{Init();cout << "请输入需要创建二叉树的字符串：n";Create_BiTree(&head);LevelOrderTraverse(head);return 0;
}

五、层序遍历（链队列实现(自创)）

每2^(n-1)个元素为一层，按照层序遍历的方式输入，存入链队列，最后层序输出。

 总代码

//二叉树的层序遍历（链队列）
#include<stdio.h>
#include<malloc.h>
#include<string>
#include<iostream>
#include<math.h>
using namespace std;int flag = 0;
std::string str;//队列（用于存放元素）
typedef struct Queue
{char data;struct Queue* next;int level;						//层数int num;						//序号
}Queue;
Queue* front, * rear;void Init_Queue()
{front = (Queue*)malloc(sizeof(Queue));rear = (Queue*)malloc(sizeof(Queue));rear = front;
}//入队
void EnQueue()
{int i, j, level = 0, count = 0;printf("请按照层序遍历顺序输入需要创建的二叉树结点(普通二叉树，空结点以#代替)：n");cin >> str;i = 0;while (pow(2, i) <= strlen(str.c_str()) - 2)i++;level = i;for (i = 0; i < level; i++)						//层{for (j = 0; j < pow(2, i); j++)				//序号{if (str[count] == '')			//退出return;Queue* q = (Queue*)malloc(sizeof(Queue));q = rear;q->data = str[count++];q->level = i + 1;					//层q->num = j + 1;					//序号q->next = NULL;if (i == 0)						//首次front = q;rear->next = (Queue*)malloc(sizeof(Queue));rear = rear->next;		//后移rear->next = NULL;}}
}//层序遍历
void LevelOrderTraverse()
{Queue* q = front;while (q->next != NULL){if (q->data != '#')printf("%c的层：%d,   序号：%dn", q->data, q->level, q->num);q = q->next;}
}int main()
{Init_Queue();EnQueue();					//入队LevelOrderTraverse();	//层序遍历return 0;
}