遍历二叉树（递归、栈、队列）

2024-04-23 03:37| 来源: 网络整理| 查看: 265

本文着重描述链式二叉树的四种遍历算法，先序、中序、后序遍历及层序遍历，具体实现使用递归和栈来操作，层序遍历使用先进先出循环队列实现。

文章目录定义二叉树构造二叉树先序遍历中序遍历后序遍历层序遍历测试代码

定义二叉树

定义一个链式二叉树，一个节点最多存在两个不相交的子节点，本文以字符类型举例

typedef struct BinaryTree { char data; struct BinaryTree *ltree, *rtree; }BTree; 构造二叉树

二叉树有两种存储结构，顺序存储和链式存储，这里通过顺序结构的二叉树构造一个链式存储的二叉树，如下图：图中用 “#” 号代表 “NULL” 方便构造二叉树，下面就用顺序存储的二叉树创建链式二叉树，创建二叉树需要改变节点指针，所以使用二级指针存储，之后的先序、中序、后序和层序遍历算法都使用该二叉树测试

void Create_BTree(BTree **t, int i, char s[]) { // i = 1; 根节点 // 2i < n, 左孩子节点编号 2i // 2i + 1 < n, 右孩子节点编号 2i + 1 // 如果 t[2i] 或 t[2i + 1] 等于 '#' , 说明该左、右孩子节点为空 if(i > strlen(s) || s[i - 1] == '0' || s[i - 1] == '#') { *t = NULL; } else { *t = (BTree *)malloc(sizeof(BTree)); (*t) -> data = s[i - 1]; Create_BTree(&((*t) -> ltree), 2*i, s); Create_BTree(&((*t) -> rtree), 2*i+1, s); } } 先序遍历

二叉树的先序遍历：根节点 -> 左子树 -> 右子树

递归算法实现： void PreOrderRe(BTree *root) { if(root != NULL) { printf("%c ", root -> data); // 先访问根节点 PreOrderRe(root -> ltree); // 访问左子树 PreOrderRe(root -> rtree); // 访问右子树 } } 非递归算法实现：如果不用递归，就使用栈来模拟递归过程，先进后出，遍历二叉树 void PreOrderNre(BTree *root) { BTree *St[MAXSIZE] = {0}; int top = -1; BTree *p = NULL; St[++top] = root; while(top != -1) { p = St[top--]; printf("%c ", p -> data); if(p -> rtree != NULL) { St[++top] = p -> rtree; } if(p -> ltree != NULL) { St[++top] = p -> ltree; } } } 中序遍历

二叉树的中序遍历：左子树 -> 根节点 -> 右子树

递归算法实现： void MidOrderRe(BTree *root) { if(root != NULL) { MidOrderRe(root -> ltree); // 先访问左子树 printf("%c ", root -> data); // 再访问根节点 MidOrderRe(root -> rtree); // 最后访问右子树 } } 非递归算法实现： void MidOrderNre(BTree *root) { BTree *St[MAXSIZE] = {0}; int top = -1; BTree *p = root; BTree *tmp = NULL; while(p != NULL || top != -1) { if(p != NULL) { St[++top] = p; p = p -> ltree; } else { tmp = St[top--]; printf("%c ", tmp -> data); p = tmp -> rtree; } } } 后序遍历

二叉树的后序遍历：左子树 -> 右子树 -> 根节点

递归算法实现： void PostOrderRe(BTree *root) { if(root != NULL) { PostOrderRe(root -> ltree); // 先访问左子树 PostOrderRe(root -> rtree); // 再访问右子树 printf("%c ", root -> data); // 最后访问根节点 } } 非递归算法实现： void PostOrderNre(BTree *root) { BTree *St[MAXSIZE] = {0}; int top = -1; int flag = -1; BTree *p = NULL; if(root != NULL) { do { while(root != NULL) { St[++top] = root; root = root -> ltree; } p = NULL; flag = 1; // 表示 root 的左子树已访问或空 while(top != -1 && flag == 1) { root = St[top]; if(root -> rtree == p) { printf("%c ", root -> data); top--; p = root; } else { root = root -> rtree; flag = 0; } } } while(top != -1); } } 层序遍历

二叉树的层序遍历是一种逐层进行访问的方式，对某一层的节点访问完成后，再按照其访问次序对各个节点的左、右孩子进行顺序访问数据结构设计：先访问的节点，其左右孩子节点也要访问，先进先出的结构，使用循环队列实现层序遍历过程：先将根节点进队，节点出队并访问，再将左右孩子节点入队，循环直到队列为空

void LevelOrder(BTree *root) { BTree *Qu[MAXSIZE] = {0}; int head = -1; int tail = -1; Qu[++tail] = root; //根节点入队 BTree *p = NULL; while(head != tail) { head = (head + 1) % MAXSIZE; p = Qu[head]; printf("%c ", p -> data); if(p -> ltree != NULL) { tail = (tail + 1) % MAXSIZE; Qu[tail] = p -> ltree; } if(p -> rtree != NULL) { tail = (tail + 1) % MAXSIZE; Qu[tail] = p -> rtree; } } } 测试代码 void test() { char s[11] = {'A', 'B', 'C', '#', 'D', 'E', 'F', '#', '#', 'G'}; BTree *root = NULL; Create_BTree(&root, 1, s); printf("先序遍历结果\n"); PreOrderRe(root); printf("\n"); PreOrderNre(root); printf("\n"); printf("**************\n"); printf("中序遍历结果\n"); MidOrderRe(root); printf("\n"); MidOrderNre(root); printf("\n"); printf("**************\n"); printf("后序遍历结果\n"); PostOrderRe(root); printf("\n"); PostOrderNre(root); printf("\n"); printf("**************\n"); printf("层序遍历结果\n"); LevelOrder(root); printf("\n"); }

测试结果如下：

E:\C_demo>binarytree.exe 先序遍历结果 A B D G C E F A B D G C E F ************** 中序遍历结果 B G D A E C F B G D A E C F ************** 后序遍历结果 G D B E F C A G D B E F C A ************** 层序遍历结果 A B C D E F G

【本文地址】

公司简介

联系我们