目录
一、前序遍历
二、中序遍历
三、后序遍历
前中后序遍历总代码
四、层序遍历(队列实现(主流))
总代码
五、层序遍历(链队列实现(自创))
总代码
二叉树的遍历分为前序、中序、后序以及层序遍历。
前中后序是按照根结点的访问顺序来确定的,前中后序遍历的核心都是递归。
一、前序遍历
访问顺序:根->左->右

普通二叉树遍历(前序):ABDCG
扩展二叉树遍历(前序):ABDC#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#BGCA
实现顺序:
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
扩展二叉树遍历(后序):ABCDG
代码:
//层序遍历 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 = -1; Q.rear = -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[++Q.rear] = *node; } //出队 BiTree DeQueue() { return Q.node[++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] == '\0') //退出 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, 序号:%d\n", q->data, q->level, q->num); q = q->next; } } int main() { Init_Queue(); EnQueue(); //入队 LevelOrderTraverse(); //层序遍历 return 0; }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容,请联系我们,一经查实,本站将立刻删除。
如需转载请保留出处:https://51itzy.com/kjqy/133209.html