二叉树遍历C语言(递归,非递归)六种算法

安 徽电气工 程 职 业 技术学 院学报
：薹６ Ｍ２ ａ ｒ ０ ｃ ｈ ０
．
－Ｘ树后序遍历的递归和非递归算法
孙泽宇， 赵国增 ， 舒云星・
（ 洛阳工业高等专科学校计算机系 ， 河南 洛阳 ４ １０ ） ７０３
［ 要 ］ 论述了二又树后序遍历的递归算法和非递归算法， 摘 对递归算法中的工作栈 的执行过程做 了
Ｓｒｃｂｔ ｅ ｔ ｔ ｉｅ ｛ ｕ ｒ
● 收稿 日期 ：０ ５—１ ０ ７０ ． ２— ２
作者筒介： 孙泽字（９７ ． 吉林长春人． １７ 一） 男。 洛阳工业高等专科学校计算机秉麓师。研究方向： 人工智能。 趟 目增 （９７ ． 河南越壁人 。 阳工业高等专科 学校计算机 秉麓师 。研究方 向： １ 一） 男。 ７ 洛 人工智能。
ｓ ｃ ｂｒ 木ｅ ， ｒ ｈ；｝ ｔ ｔ ｉｅ ｌｔ 木 ｉ ｔ ｍ ｔｅ ｆ ｇ
后序遍历二叉树的递归算法如下 ：
Ｔ ｐ ｄ ｆｓ ｕ ｔＢＴ ｏ ｅ ｙ ｅ ｅ ｒ ｃ ｉｎ ｄ ｔ
法及执行时栈 的变化情况 ， 可设计 出较好 的非递归化算法 ， 本文讨论了二叉树后序遍历的递归和非递归
算法。 ２ 后序遍历二叉树的递归算法
１ 后序遍历左子树（ ） 若左子树不为空 ） ２ 后序遍历右子树（ ） 若右子树不为空 ） ３ 访问根结点 （ ） 若存在根结点）
二叉树数据结构如下 ：
二叉树是数据结构 中最常见 的存储形式 ， 在算法与数据结构中经常使用。树与森林都可以转换为 二叉树 ， 而遍历算法则是二叉树最重要的操作 。所谓遍历二叉树 ， 就是遵从某种次序 ， 遍访二叉树 中的
所有结点， 使得每个结点被访问一次 ， 而且仅一次。在遍历算法中， 递归算法是最普遍 的， 弄清 了递归算

后序遍历的非递归算法（C详细）后序遍历是二叉树遍历的一种方式，它的顺序是先遍历左子树，然后遍历右子树，最后访问根节点。

非递归实现后序遍历的算法可以使用栈来辅助实现。

首先，我们需要定义一个树节点的数据结构，例如：```cstruct TreeNodeint val;struct TreeNode* left;struct TreeNode* right;};```接下来，我们使用一个辅助栈来进行非递归后序遍历。

首先需要创建一个空栈，并将根节点入栈。

然后开始循环，直到栈为空为止。

在循环中，首先取出栈顶节点，如果该节点没有左子树且没有右子树，说明该节点是叶子节点，可以直接输出该节点的值。

如果该节点有左子树或者右子树，需要判断是否已经遍历过该节点的子节点。

为了实现后序遍历的顺序，我们需要一个标记变量来记录上次访问的节点。

如果上次访问的节点是该节点的右子树，说明该节点的左右子节点都已经访问过了，可以直接输出该节点的值。

反之，如果上次访问的节点不是该节点的右子树，将该节点重新入栈，并以右、左、中的顺序将其右子树、左子树入栈。

下面给出完整的代码实现：```c#include <stdio.h>#include <stdlib.h>struct TreeNodeint val;struct TreeNode* left;struct TreeNode* right;};void postOrderTraversal(struct TreeNode* root)if (root == NULL)return;}struct TreeNode* lastVisited = NULL; // 上次访问的节点struct TreeNode* node = root; // 当前遍历的节点struct TreeNode* stack[100]; // 栈int top = -1; // 栈顶指针while (node != NULL ， top != -1)if (node != NULL)stack[++top] = node; // 入栈node = node->left; // 访问左子树} elsestruct TreeNode* temp = stack[top]; // 取出栈顶节点if (temp->right == NULL ， temp->right == lastVisited) printf("%d ", temp->val);top--; // 出栈lastVisited = temp; // 记录上次访问的节点} elsenode = temp->right; // 访问右子树}}}struct TreeNode* createNode(int val)struct TreeNode* node = (structTreeNode*)malloc(sizeof(struct TreeNode));if (node != NULL)node->val = val;node->left = NULL;node->right = NULL;}return node;int mai//创建一个二叉树struct TreeNode* root = createNode(1); root->left = createNode(2);root->right = createNode(3);root->left->left = createNode(4);root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7);//后序遍历二叉树printf("后序遍历结果："); postOrderTraversal(root);printf("\n");return 0;```以上代码中，我们使用了一个辅助数组作为栈来实现非递归遍历。

⼆叉树的遍历及常⽤算法⼆叉树的遍历及常⽤算法遍历的定义:按照某种次序访问⼆叉树上的所有结点,且每个节点仅被访问⼀次;遍历的重要性:当我们需要对⼀颗⼆叉树进⾏,插⼊,删除,查找等操作时,通常都需要先遍历⼆叉树,所有说:遍历是⼆叉树的基本操作;遍历思路:⼆叉树的数据结构是递归定义(每个节点都可能包含相同结构的⼦节点),所以遍历也可以使⽤递归,即结点不为空则继续递归调⽤每个节点都有三个域,数据与,左孩⼦指针和右孩⼦之指针,每次遍历只需要读取数据,递归左⼦树,递归右⼦树,这三个操作三种遍历次序:根据访问三个域的不同顺序,可以有多种不同的遍历次序,⽽通常对于⼦树的访问都按照从左往右的顺序;设:L为遍历左⼦树,D为访问根结点,R为遍历右⼦树,且L必须位于R的前⾯可以得出以下三种不同的遍历次序:先序遍历操作次序为DLR,⾸先访问根结点，其次遍历根的左⼦树，最后遍历根右⼦树，对每棵⼦树同样按这三步(先根、后左、再右)进⾏中序遍历操作次序为LDR,⾸先遍历根的左⼦树，其次访问根结点，最后遍历根右⼦树，对每棵⼦树同样按这三步(先左、后根、再右)进⾏后序遍历操作次序为LRD,⾸先遍历根的左⼦树，其次遍历根的右⼦树，最后访问根结点，对每棵⼦树同样按这三步(先左、后右、最后根)进⾏层次遍历层次遍历即按照从上到下从左到右的顺序依次遍历所有节点,实现层次遍历通常需要借助⼀个队列,将接下来要遍历的结点依次加⼊队列中;遍历的应⽤“遍历”是⼆叉树各种操作的基础，可以在遍历过程中对结点进⾏各种操作，如:对于⼀棵已知⼆叉树求⼆叉树中结点的个数求⼆叉树中叶⼦结点的个数;求⼆叉树中度为1的结点个数求⼆叉树中度为2的结点个数5求⼆叉树中⾮终端结点个数交换结点左右孩⼦判定结点所在层次等等...C语⾔实现:#include <stdio.h>//⼆叉链表数据结构定义typedef struct TNode {char data;struct TNode *lchild;struct TNode *rchild;} *BinTree, BinNode;//初始化//传⼊⼀个指针令指针指向NULLvoid initiate(BinTree *tree) {*tree = NULL;}//创建树void create(BinTree *BT) {printf("输⼊当前结点值: (0则创建空节点)\n");char data;scanf(" %c", &data);//连续输⼊整形和字符时.字符变量会接受到换⾏,所以加空格if (data == 48) {*BT = NULL;return;} else {//创建根结点//注意开辟的空间⼤⼩是结构体的⼤⼩⽽不是结构体指针⼤⼩,写错了不会⽴马产⽣问题,但是后续在其中存储数据时极有可能出现内存访问异常(飙泪....) *BT = malloc(sizeof(struct TNode));//数据域赋值(*BT)->data = data;printf("输⼊节点 %c 的左孩⼦ \n", data);create(&((*BT)->lchild));//递归创建左⼦树printf("输⼊节点 %c 的右孩⼦ \n", data);create(&((*BT)->rchild));//递归创建右⼦树}}//求双亲结点(⽗结点)BinNode *Parent(BinTree tree, char x) {if (tree == NULL)return NULL;else if ((tree->lchild != NULL && tree->lchild->data == x) || (tree->rchild != NULL && tree->rchild->data == x))return tree;else{BinNode *node1 = Parent(tree->lchild, x);BinNode *node2 = Parent(tree->rchild, x);return node1 != NULL ? node1 : node2;}}//先序遍历void PreOrder(BinTree tree) {if (tree) {//输出数据printf("%c ", tree->data);//不为空则按顺序继续递归判断该节点的两个⼦节点PreOrder(tree->lchild);PreOrder(tree->rchild);}}//中序void InOrder(BinTree tree) {if (tree) {InOrder(tree->lchild);printf("%c ", tree->data);InOrder(tree->rchild);}}//后序void PostOrder(BinTree tree) {if (tree) {PostOrder(tree->lchild);PostOrder(tree->rchild);printf("%c ", tree->data);}}//销毁结点递归free所有节点void DestroyTree(BinTree *tree) {if (*tree != NULL) {printf("free %c \n", (*tree)->data);if ((*tree)->lchild) {DestroyTree(&((*tree)->lchild));}if ((*tree)->rchild) {DestroyTree(&((*tree)->rchild));}free(*tree);*tree = NULL;}}// 查找元素为X的结点使⽤的是层次遍历BinNode *FindNode(BinTree tree, char x) {if (tree == NULL) {return NULL;}//队列BinNode *nodes[1000] = {};//队列头尾位置int front = 0, real = 0;//将根节点插⼊到队列尾nodes[real] = tree;real += 1;//若队列不为空则继续while (front != real) {//取出队列头结点输出数据BinNode *current = nodes[front];if (current->data == x) {return current;}front++;//若当前节点还有⼦(左/右)节点则将结点加⼊队列if (current->lchild != NULL) {nodes[real] = current->lchild;real++;}if (current->rchild != NULL) {nodes[real] = current->rchild;real++;}}return NULL;}//层次遍历// 查找元素为X的结点使⽤的是层次遍历void LevelOrder(BinTree tree) {if (tree == NULL) {return;}//队列BinNode *nodes[1000] = {};//队列头尾位置int front = 0, real = 0;//将根节点插⼊到队列尾nodes[real] = tree;real += 1;//若队列不为空则继续while (front != real) {//取出队列头结点输出数据BinNode *current = nodes[front];printf("%2c", current->data);front++;//若当前节点还有⼦(左/右)节点则将结点加⼊队列if (current->lchild != NULL) {nodes[real] = current->lchild;real++;}if (current->rchild != NULL) {nodes[real] = current->rchild;real++;}}}//查找x的左孩⼦BinNode *Lchild(BinTree tree, char x) {BinTree node = FindNode(tree, x);if (node != NULL) {return node->lchild;}return NULL;}//查找x的右孩⼦BinNode *Rchild(BinTree tree, char x) {BinTree node = FindNode(tree, x);if (node != NULL) {return node->rchild;}return NULL;}//求叶⼦结点数量int leafCount(BinTree *tree) {if (*tree == NULL)return 0;//若左右⼦树都为空则该节点为叶⼦,且后续不⽤接续递归了else if (!(*tree)->lchild && !(*tree)->rchild)return 1;else//若当前结点存在⼦树,则递归左右⼦树, 结果相加return leafCount(&((*tree)->lchild)) + leafCount(&((*tree)->rchild));}//求⾮叶⼦结点数量int NotLeafCount(BinTree *tree) {if (*tree == NULL)return 0;//若该结点左右⼦树均为空,则是叶⼦,且不⽤继续递归else if (!(*tree)->lchild && !(*tree)->rchild)return 0;else//若当前结点存在左右⼦树,则是⾮叶⼦结点(数量+1),在递归获取左右⼦树中的⾮叶⼦结点,结果相加 return NotLeafCount(&((*tree)->lchild)) + NotLeafCount(&((*tree)->rchild)) + 1;}//求树的⾼度(深度)int DepthCount(BinTree *tree) {if (*tree == NULL)return 0;else{//当前节点不为空则深度+1 在加上⼦树的⾼度,int lc = DepthCount(&((*tree)->lchild)) + 1;int rc = DepthCount(&((*tree)->rchild)) + 1;return lc > rc?lc:rc;// 取两⼦树深度的最⼤值 }}//删除左⼦树void RemoveLeft(BinNode *node){if (!node)return;if (node->lchild)DestroyTree(&(node->lchild));node->lchild = NULL;}//删除右⼦树void RemoveRight(BinNode *node){if (!node)return;if (node->rchild)DestroyTree(&(node->rchild));node->rchild = NULL;}int main() {BinTree tree;create(&tree);BinNode *node = Parent(tree, 'G');printf("G的⽗结点为%c\n",node->data);BinNode *node2 = Lchild(tree, 'D');printf("D的左孩⼦结点为%c\n",node2->data);BinNode *node3 = Rchild(tree, 'D');printf("D的右孩⼦结点为%c\n",node3->data);printf("先序遍历为:");PreOrder(tree);printf("\n");printf("中序遍历为:");InOrder(tree);printf("\n");printf("后序遍历为:");PostOrder(tree);printf("\n");printf("层次遍历为:");LevelOrder(tree);printf("\n");int a = leafCount(&tree);printf("叶⼦结点数为%d\n",a);int b = NotLeafCount(&tree);printf("⾮叶⼦结点数为%d\n",b);int c = DepthCount(&tree);printf("深度为%d\n",c);//查找F节点BinNode *node4 = FindNode(tree,'C');RemoveLeft(node4);printf("删除C的左孩⼦后遍历:");LevelOrder(tree);printf("\n");RemoveRight(node4);printf("删除C的右孩⼦后遍历:");LevelOrder(tree);printf("\n");//销毁树printf("销毁树 \n");DestroyTree(&tree);printf("销毁后后遍历:");LevelOrder(tree);printf("\n");printf("Hello, World!\n");return 0;}测试:测试数据为下列⼆叉树:运⾏程序复制粘贴下列内容:ABDGHECKFIJ特别感谢:iammomo。

问一次。这里的“ 问”的含义很广 ，比如修 改或输出结点的信息， 访 删除结 我们知道 ， 二叉树有三个基本的组成部分， 根， 即： 左子树和右予 树， 只 要依次遍历这三个 部分， 能遍历整个二叉树 。 遍历二叉树的方式通常有 就
算， 所用到的数据仅为整型或实型即能满足要求 ， 计算求精课程称作数值方 点等等。
子树， 再访问右子树 ， 最后访 问根结 点） 。由于二叉树定义 的递归性， 我们很 容易就会想到用递 归算法来遍历二叉树。 设二叉树与栈 的结构如下 （ ｃ 用 语言描述） ：
ｔ ｐ ｄ ｆｓ ｒ ｃ ｉ Ｎ ｄ ｙ ｅ ｅ ｔｕ ｔ Ｂ Ｔ ｏ ｅ ｆ
ｃ ａ ｄ ｔ ｈ ｒ ａ ａ：
据结构会对应复杂程度不 同的算法 ，丽设计一个合适 的数据 结构 能使算法 三 种， 先序遍历 （ 即： 先访 问根 结点， 再访问左子树 ， 最后访问右子树） 中序 、 先访问左 予树 ， 再访 问根结点， 后访 问右子树） 后序遍历 （ 最 。 先访问左 的复杂程度大大降低。 编程人员在实践 中体会到 ； 学好～种高级语言仪能解 遍历 （ 决三成所遇到的 问题， 而学好数据结构却 能解 决八成所遇 到的问题， 因此， 在软件 设计中选择一个合适的数据结构越发显得重要 。 在 管理科学领域中， 很多问题都可 以转化 为树 Ｔ ｅ ｒ ｅ型结构 ， 而多叉树
就会不同。
）Ａ ｒ ｙｓ ｑ ｅ ｃ ［ａ ］ ｒａ ， ｅｕ ｎ ｅＭ ｘ
ｔ ｐ ｄ ｆ ｔｕ ｔ ｙ ｅ ｅ ｓ ｒ ｃ
树， 它有 ４ 个结点。为了便于理解遍历思想 ， 暂时为每个没有 予树 的结点都
ｆ
ｅ ｅｌｙ ｅ ｂ ｓ １ Ⅱ ｐ 赤 ａ ｅ： ｔ ｅ ｅ ｔ ｐ ＊ｔ ｐ＇ ｌｍｙｅ ｏ ，

右子 树还未访 问）（ 序访 问 Ａ的左子树 的根结点 Ｂ ， 和 ｌ ，先 ）Ｂ 进 栈 ． 于 Ｂ的左 子 树 为 空 ， 以 Ｂ 和 １出 栈 ，中 序 访 问 Ｂ）Ｂ 由 所 （ ， 和 Ｏ进栈 （ Ｏ表 示 开 始 遍 历 结 点 Ｂ 的 右 子 树 ） 由 于 Ｂ 的 右 子树 ． 为空 。 Ｂ和 Ｏ出栈 ，后 序访 问 Ｂ ． 和 １出 栈 。 中序 访 问 Ａ）Ａ （ ）Ａ （ ， 和 Ｏ进栈 ．先 序 访 Ａ的 右 子 树 的 根 结 点 Ｃ ， （ ）Ｃ和 １进 栈 ， 由 于 Ｃ的左子树为空 ， Ｃ和 ｌ出栈 ．中序 访问 Ｃ 。 （ ）Ｃ和 Ｏ进栈 ， 由 于 Ｃ 的 右 子 树 为 空 。 和 ０出 栈 ． 后 序 访 问 Ｃ）Ａ 和 Ｏ出 栈 ， Ｃ （ ． （ 序 访 问 Ａ）此 时 栈 已 空 ， 历 过 程 结 束 。 后 ， 遍 从 上 面可 知 ， 每个 结 点 进栈 、 出栈 都 是 两 次 。若 进 栈 前 访 问 该结点 ， 则得 到先 序 序 列 Ａ Ｃ； 在 第 一 次 出栈 时 济 问 该结 点 ， Ｂ 若 则得 到 中序 序 列 Ｂ Ｃ： 在 第 二 次 出栈 时访 问 该 结 点 ， Ａ 若 则得 到 后 序 序 列 Ｂ Ａ。 此 ． Ｃ 因 只需 对 二 叉树 遍 历 一 次 即 可 得 到 三 种 遍 历序 列 这里的关键是设置了一个标志位 ． 用来 说明该结点的右子树 是 否 已访 问 ． 以此 表 示 该 结 点 是第 一 次 出栈 还 是 第 二 次 出栈 。
维普资讯
２０ ０ ６年 第 ６期
福
建 电
脑
１１ ２
二叉树遍历的通用非递归算 法
徐凤生 １ 李立群 ２ 马夕荣 ２
（ ． 州 学 院 计算 机 系 。 东 德 州 ２ ３２ ２ 山 东省 农 业 管 理 干部 学 院 ， 东 济 南 ２ ０ ０ ） １德 山 ５０３ ． 山 ５ １０

二叉树的遍历算法实验报告二叉树的遍历算法实验报告引言：二叉树是计算机科学中常用的数据结构之一，它是由节点组成的层次结构，每个节点最多有两个子节点。

在实际应用中，对二叉树进行遍历是一项重要的操作，可以帮助我们理解树的结构和节点之间的关系。

本文将介绍二叉树的三种遍历算法：前序遍历、中序遍历和后序遍历，并通过实验验证其正确性和效率。

一、前序遍历前序遍历是指先访问根节点，然后按照先左后右的顺序遍历左右子树。

具体的实现可以通过递归或者使用栈来实现。

我们以递归方式实现前序遍历算法，并进行实验验证。

实验步骤：1. 创建一个二叉树，并手动构造一些节点和它们之间的关系。

2. 实现前序遍历算法的递归函数，函数的输入为根节点。

3. 在递归函数中，首先访问当前节点，然后递归调用函数遍历左子树，最后递归调用函数遍历右子树。

4. 调用前序遍历函数，输出遍历结果。

实验结果：经过实验，我们得到了正确的前序遍历结果。

这证明了前序遍历算法的正确性。

二、中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。

同样，我们可以使用递归或者栈来实现中序遍历算法。

在本实验中，我们选择使用递归方式来实现。

实验步骤：1. 继续使用前面创建的二叉树。

2. 实现中序遍历算法的递归函数，函数的输入为根节点。

3. 在递归函数中，首先递归调用函数遍历左子树，然后访问当前节点，最后递归调用函数遍历右子树。

4. 调用中序遍历函数，输出遍历结果。

实验结果：通过实验，我们得到了正确的中序遍历结果。

这证明了中序遍历算法的正确性。

三、后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。

同样，我们可以使用递归或者栈来实现后序遍历算法。

在本实验中，我们选择使用递归方式来实现。

实验步骤：1. 继续使用前面创建的二叉树。

2. 实现后序遍历算法的递归函数，函数的输入为根节点。

3. 在递归函数中，首先递归调用函数遍历左子树，然后递归调用函数遍历右子树，最后访问当前节点。

4. 调用后序遍历函数，输出遍历结果。

c语言二叉树的先序,中序,后序遍历1、先序遍历先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果先序遍历结果为：A B D H I E J C F K G2、中序遍历中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果中遍历结果为：H D I B E J A F K C G3、后序遍历后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。

还记得我上面提到先序遍历绕圈的路线么？（不记得翻上面理解）就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。

后序遍历中，根节点默认最后面后序遍历结果：H I D J E B K F G C A4、口诀先序遍历：先根再左再右中序遍历：先左再根再右后序遍历：先左再右再根这里的根，指的是每个分叉子树（左右子树的根节点）根节点，并不只是最开始头顶的根节点，需要灵活思考理解5、代码展示#include<stdio.h>#include<stdlib.h>typedef struct Tree{int data; // 存放数据域struct Tree *lchild; // 遍历左子树指针struct Tree *rchild; // 遍历右子树指针}Tree,*BitTree;BitTree CreateLink(){int data;int temp;BitTree T;scanf("%d",&data); // 输入数据temp=getchar(); // 吸收空格if(data == -1){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建return NULL;}else{T = (BitTree)malloc(sizeof(Tree)); // 分配内存空间T->data = data; // 把当前输入的数据存入当前节点指针的数据域中printf("请输入%d的左子树: ",data);T->lchild = CreateLink(); // 开始递归创建左子树printf("请输入%d的右子树: ",data);T->rchild = CreateLink(); // 开始到上一级节点的右边递归创建左右子树return T; // 返回根节点}}// 先序遍历void ShowXianXu(BitTree T) // 先序遍历二叉树{if(T==NULL) //递归中遇到NULL，返回上一层节点{return;}printf("%d ",T->data);ShowXianXu(T->lchild); // 递归遍历左子树ShowXianXu(T->rchild); // 递归遍历右子树}// 中序遍历void ShowZhongXu(BitTree T) // 先序遍历二叉树{if(T==NULL) //递归中遇到NULL，返回上一层节点{return;}ShowZhongXu(T->lchild); // 递归遍历左子树printf("%d ",T->data);ShowZhongXu(T->rchild); // 递归遍历右子树}// 后序遍历void ShowHouXu(BitTree T) // 后序遍历二叉树{if(T==NULL) //递归中遇到NULL，返回上一层节点{return;}ShowHouXu(T->lchild); // 递归遍历左子树ShowHouXu(T->rchild); // 递归遍历右子树printf("%d ",T->data);}int main(){BitTree S;printf("请输入第一个节点的数据:\n");S = CreateLink(); // 接受创建二叉树完成的根节点printf("先序遍历结果: \n");ShowXianXu(S); // 先序遍历二叉树printf("\n中序遍历结果: \n");ShowZhongXu(S); // 中序遍历二叉树printf("\n后序遍历结果: \n");ShowHouXu(S); // 后序遍历二叉树return 0;}。

二叉树后序遍历的非递归算法
二叉树后序遍历是指按照左子树、右子树、根节点的顺序遍历二叉树的过程。

与前序遍历和中序遍历不同，后序遍历需要考虑根节点的位置，因此需要使用栈来存储节点信息。

非递归算法一般使用栈来实现，因为后序遍历的过程中需要先遍历左子树和右子树，最后才遍历根节点，所以存储节点信息的栈需要进行一些特殊处理。

下面是二叉树后序遍历的非递归算法：
1. 创建一个空栈，并将根节点入栈。

2. 创建一个辅助变量pre表示上一个被遍历的节点。

3. 当栈不为空时，取出栈顶元素top，判断它是否为叶子节点或者它的左右子节点都被遍历过了（被遍历过的节点可以通过辅助变量pre来判断）。

4. 如果top为叶子节点或者它的左右子节点都被遍历过了，则将top出栈，并将它的值输出。

5. 如果不满足条件3，判断top的右子节点是否为pre，如果是，则说明右子树已经遍历完了，此时可以直接输出top的值，并将top出栈；如果不是，则将top的右子节点入栈。

6. 将top的左子节点入栈。

7. 将上一个被遍历的节点pre更新为top。

根据这个算法，我们可以分别对左子树和右子树进行遍历，并保证根节点最后被遍历到，从而实现二叉树的后序遍历。

这个算法的时间复杂度为O(n)，空间复杂度为O(n)。

总的来说，二叉树的后序遍历是一种比较复杂的遍历方式，需要使用栈保存节点信息，并且需要特殊处理根节点的位置。

使用非递归算法实现后序遍历可以优化空间复杂度和避免栈溢出的问题。

二叉树的各种遍历算法及其深度算法一、二叉树的遍历算法二叉树是一种常见的数据结构，遍历二叉树可以按照根节点的访问顺序将二叉树的结点访问一次且仅访问一次。

根据遍历的顺序不同，二叉树的遍历算法可以分为三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历（Pre-order Traversal）：首先访问根节点，然后遍历左子树，最后遍历右子树。

可以用递归或者栈来实现。

2. 中序遍历（In-order Traversal）：首先遍历左子树，然后访问根节点，最后遍历右子树。

可以用递归或者栈来实现。

3. 后序遍历（Post-order Traversal）：首先遍历左子树，然后遍历右子树，最后访问根节点。

可以用递归或者栈来实现。

二、二叉树的深度算法二叉树的深度，也叫做高度，指的是从根节点到叶子节点的最长路径上的节点数目。

可以使用递归或者层次遍历的方式来计算二叉树的深度。

1.递归算法：二叉树的深度等于左子树的深度和右子树的深度的较大值加一、递归的终止条件是当节点为空时，深度为0。

递归的过程中通过不断递归左子树和右子树，可以求出二叉树的深度。

2.层次遍历算法：层次遍历二叉树时，每遍历完一层节点，深度加一、使用一个队列来辅助层次遍历，先将根节点加入队列，然后依次取出队列中的节点，将其左右子节点加入队列，直到队列为空，完成层次遍历。

三、示例为了更好地理解二叉树的遍历和求深度的算法，我们以一个简单的二叉树为例进行说明。

假设该二叉树的结构如下：A/\BC/\/\DEFG其中，A、B、C、D、E、F、G分别代表二叉树的结点。

1.前序遍历：A->B->D->E->C->F->G2.中序遍历：D->B->E->A->F->C->G3.后序遍历：D->E->B->F->G->C->A4.深度：2以上是针对这个二叉树的遍历和深度的计算示例。

⼆叉树⼆叉链表的层序遍历（C语⾔）所谓⼆叉树层序遍历，即从⼆叉树根结点开始，按从上到下、从左到右的顺序访问每⼀个结点。

每个结点只访问⼀次。

#include <stdio.h>#include <stdlib.h>/*** ⼆叉树⼆叉链表之⾮递归遍历：层序遍历* 算法思想：借助⼀个队列；根树进队；队不为空时循环“从队列中出⼀个树p，访问该树根结点；* 若它有左⼦树，左⼦树进队；若它有右⼦树，右⼦树进队。

”* (保证了元素进队顺序是从树的上层到下层，且同层元素在队列中从左到右相邻)* (注：为了节约空间，这⾥的树进队，是指树的地址进队，⽽不是树结点进队，队列中存放的是对各树地址的引⽤)*/#define OK 1;#define TURE 1;#define FALSE 0;#define ERROR 0;const int OVERFLOW = -2;const int MAXSIZE = 100;typedef int Status;typedef char TElemType;//⼆叉链表结构定义typedef struct BiNode{TElemType data;struct BiNode *lchild, *rchild;} BiNode, *BiTree;//顺序循环队列定义typedef struct {BiTree *base; //存放树型指针int front; //头指针，若队列不为空，指向队列头元素int rear; //尾指针，若队列不为空，指向队列尾元素的下⼀个位置} SqQueue;//由字符序列创建⼆叉树Status CreateBiTree(BiTree *tree,TElemType data[],int *j,int len){if((*j)<=len-1){if(data[(*j)]=='#'){(*tree)=NULL;(*j)++;} else {(*tree)=(BiTree)malloc(sizeof(BiNode));if(!(*tree)) return OVERFLOW;(*tree)->data=data[(*j)]; //⽣成根结点(*j)++;CreateBiTree(&((*tree)->lchild),data,j,len); //构造左⼦树CreateBiTree(&((*tree)->rchild),data,j,len); //构造右⼦树}}return OK;}//访问⼆叉树结点Status Visit(BiTree tree){printf("%c",tree->data);return OK;}//借助队列实现⼆叉链表的层序遍历Status LevelOrder_ByQueue(BiTree tree) {BiTree p;SqQueue queue1;InitQueue(&queue1);EnQueue(&queue1,tree); //根结点⼊队while(queue1.front!=queue1.rear){ //队不为空DeQueue(&queue1,&p); //根节点出队Visit(p);if(p->lchild!=NULL) EnQueue(&queue1,p->lchild); //有左孩⼦就进队if(p->rchild!=NULL) EnQueue(&queue1,p->rchild); //有右孩⼦也进队}return OK;}/***⽤到队列的相关函数***///循环队列初始化Status InitQueue(SqQueue *queue) {queue->base=(BiTree*)malloc(sizeof(BiTree)*MAXSIZE); //分配队列数组空间if(!queue->base) return OVERFLOW; //分配失败queue->front=0;queue->rear=0;return OK;}//循环队列⼊队操作Status EnQueue(SqQueue *queue,BiTree elem){if((queue->rear+1)%MAXSIZE==queue->front){ //队满return ERROR;} else {queue->base[queue->rear]=elem;queue->rear=(queue->rear+1)%MAXSIZE;return OK;}}//循环队列出队操作Status DeQueue(SqQueue *queue,BiTree *elem){if(queue->front==queue->rear){ //队空return ERROR;} else {(*elem)=queue->base[queue->front];queue->front=(queue->front+1)%MAXSIZE;return OK;}}int main(void){//⽰例⼆叉树的结构/*A/B/ \C D/ \E F\G*///指向⼆叉树的指针BiTree bitree1;//创建⼆叉树待⽤数据TElemType data1[]={'A','B','C','#','#','D','E','#','G','#','#','F','#','#','#',}; //先序遍历序列int len1=sizeof(data1)/sizeof(data1[0]);int* j1=(int*)malloc(sizeof(int));*j1=0;//按先序遍历序列创建⼆叉树Status createBiTreeResult = CreateBiTree(&bitree1,data1,j1,len1);printf("⼆叉树创建结果：%d\n",createBiTreeResult);//层序遍历⼆叉树Status levelOrder_ByQueue = LevelOrder_ByQueue(bitree1); //注:这⾥参数是⼆叉树根结点，⽽不是指针 printf("\n层序遍历⼆叉树结果：%d\n",levelOrder_ByQueue);printf("\nEND");return0;}。

由于在非递归实现中，我们使用栈来 模拟递归的过程，因此遍历后的结果 与递归实现相同。
04 非递归中序遍历 二叉树的复杂度 分析
时间复杂度
最好情况：O(n) 最坏情况：O(n)
平均情况：O(n)
空间复杂度
最好情况：O(1) 最坏情况：O(n)
平均情况：O(n)
05 非递归中序遍历 二叉树的优缺点
优点
01
02
03
空间效率高
非递归算法通常只需要常 数级别的额外空间，相比 之下，递归算法可能需要 更多的堆栈空间。
代码简洁
非递归算法的代码通常更 简洁，更易于理解和维护。
适合处理大型数据
由于非递归算法不需要大 量的堆栈空间，因此更适 合处理大型数据集。
缺点
编程技巧要求高
非递归算法需要更多的编程技巧， 特别是对于那些不熟悉这种技术 的人来说，理解和实现可能会比 较困难。
遍历过程
01
02
03
04
弹出栈顶元素，访问该 节点。
如果该节点右子节点存 在，将右子节点入栈。
如果该节点左子节点存 在，将左子节点入栈。
重复上述步骤，直到栈 为空。
遍历后的结果
01
中序遍历的顺序为：左子树 -> 根节点 -> 右子树。
02
非递归方法利用了栈的性质，实 现了从上到下、从左到右的遍历 顺序。
THANKS
感谢观看
栈为空。
实例二：复杂的二叉树
总结词：进阶应用
详细描述：对于复杂的二叉树，非递归中序遍历需要 更加细致的处理。由于树的形状可能不规则，我们需 要更加灵活地使用栈来处理节点之间的关系。在遍历 过程中，我们需要注意处理各种特殊情况，例如循环 引用、节点值相等的情况，以避免陷入无限循环或访 问错误的节点。此外，我们还需要注意优化算法的时 间复杂度和空间复杂度，以提高遍历的效率和准确性。

C语言实现二叉树的前序遍历二叉树是一种非线性数据结构，由节点和边组成。

每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以用递归或迭代的方法进行前序、中序和后序遍历。

在本文中，我们将重点介绍如何使用递归方法实现二叉树的前序遍历。

前序遍历是指首先访问根节点，然后按照左子树->右子树的顺序遍历二叉树。

在实际编程中，我们可以通过递归的方式来遍历每个节点。

首先，让我们定义二叉树的节点结构。

```c//定义二叉树节点结构struct TreeNodeint val; // 节点值struct TreeNode* left; // 左子节点指针struct TreeNode* right; // 右子节点指针};```接下来，让我们实现二叉树的前序遍历函数。

```c//二叉树的前序遍历函数void preorderTraversal(struct TreeNode* root)if (root == NULL) { // 如果根节点为空，则返回return;}//首先打印根节点的值printf("%d ", root->val);//然后递归遍历左子树preorderTraversal(root->left);//最后递归遍历右子树preorderTraversal(root->right);```首先，我们判断根节点是否为空。

如果为空，表示已经遍历到叶子节点，直接返回。

然后，我们打印当前节点的值。

接下来，我们递归调用前序遍历函数，遍历左子树和右子树。

接下来，我们可以通过构建一个简单的二叉树来测试我们的前序遍历函数。

```c//创建一个二叉树用于测试前序遍历struct TreeNode* createTestTrestruct TreeNode* root = (structTreeNode*)malloc(sizeof(struct TreeNode)); // 创建根节点root->val = 1;root->left = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建左子节点root->left->val = 2;root->left->left = NULL;root->left->right = NULL;root->right = (struct TreeNode*)malloc(sizeof(struct TreeNode)); // 创建右子节点root->right->val = 3;root->right->left = NULL;root->right->right = NULL;return root;```在主函数中，我们创建一个测试二叉树，并调用前序遍历函数进行遍历。

⼆叉树的遍历及相关题⽬⼆叉树的遍历及相关题⽬1.1⼆叉树遍历的概念⼆叉树结构体的定义：typedef struct node{ ElemType data; struct node * lchild; struct node * rchild;}⼆叉树的遍历是指按照⼀定的次序访问⼆叉树中的所有的节点，并且每个节点仅访问⼀次的过程。

若规定先遍历左⼦树，后遍历右⼦树，则对于⾮空⼆叉树，可得到如下3种递归的遍历⽅法：（1）先序遍历访问根节点，先序遍历左⼦树，先序遍历右⼦树。

（根，左，右）（2）中序遍历中序遍历左⼦树，访问根节点，中序遍历右⼦树。

（左，根，右）（3）后序遍历后序遍历左⼦树，后序遍历右⼦树，访问根节点。

（左，右，根）除此之外也有层次遍历。

先访问根节点，在从左到右访问第⼆层的所有节点，从左到右访问第三层的所有节点......1.2⼆叉树遍历递归算法先序遍历递归算法：void PreOrder(BTNode * b){ if(n != NULL) { cout<<b->data; PreOrder(b->lchild); PreOrder(b->rchild); }}中序遍历递归算法void InOrder(BTNode * b){ if(n != NULL) { InOrder(b->lchild); cout<<b->data; InOrder(b->rchild); }}后序遍历递归算法：void PostOrder(BTNode * b){ if(b != NULL) { PostOrder(b->lchild); PostOrder(b->rchild); cout<<b->data; }}题⽬1：输出⼀个给定⼆叉树的所有的叶⼦节点：void DispLeaf(BTNode * b){ if(b != NULL) { if(b->lchild == NULL && b->rchild == NULL) cout<<b->data; DispLeaf(b->lchild); DispLeaf(b->rchild); }}以上算法采⽤先序遍历输出了所有的叶⼦节点，所以叶⼦节点是从左到右输出的。

二叉树各种计算公式总结二叉树是一种常见的数据结构，它由一个根节点和最多两个子节点组成。

许多计算问题可以通过对二叉树进行各种操作和遍历来解决。

在本文中，将总结二叉树的各种计算公式。

1.二叉树节点个数：二叉树节点个数的计算公式是N=N1+N2+1，其中N表示二叉树的节点个数，N1表示左子树的节点个数，N2表示右子树的节点个数。

2. 二叉树的高度：二叉树的高度是指从根节点到最远叶子节点的最长路径上的节点数量。

计算二叉树的高度的公式是H = max(H1, H2) + 1，其中H表示二叉树的高度，H1表示左子树的高度，H2表示右子树的高度。

3.二叉树的深度：二叉树的深度是指从根节点到当前节点的路径的长度。

计算二叉树的深度的公式是D=D1+1，其中D表示二叉树的深度，D1表示父节点的深度。

4.二叉查找树：二叉查找树是一种有序二叉树，它要求对于树中的每个节点，左子树的值都小于节点的值，右子树的值都大于节点的值。

在二叉查找树中进行的公式是：-如果目标值等于当前节点的值，则返回当前节点；-如果目标值小于当前节点的值，则在左子树中继续；-如果目标值大于当前节点的值，则在右子树中继续。

5.二叉树的遍历：二叉树的遍历是指按照一定的顺序访问二叉树中的所有节点。

常见的二叉树遍历方式有三种：- 前序遍历：先访问根节点，然后递归地访问左子树，最后递归地访问右子树。

可以表示为：root -> 左子树 -> 右子树。

- 中序遍历：先递归地访问左子树，然后访问根节点，最后递归地访问右子树。

可以表示为：左子树 -> root -> 右子树。

- 后序遍历：先递归地访问左子树，然后递归地访问右子树，最后访问根节点。

可以表示为：左子树 -> 右子树 -> root。

6.二叉树的最大路径和：二叉树的最大路径和是指二叉树中两个节点之间路径上的节点值的最大和。

可以通过递归地计算每个子树的最大路径和，然后选择最大的子树路径和来得出最终结果。

二叉树的各种算法1.二叉树的前序遍历算法：前序遍历是指先访问根节点，再访问左子树，最后访问右子树的遍历顺序。

具体算法如下：-如果二叉树为空，则直接返回。

-访问根节点，并输出或进行其他操作。

-递归地前序遍历左子树。

-递归地前序遍历右子树。

2.二叉树的中序遍历算法：中序遍历是指先访问左子树，再访问根节点，最后访问右子树的遍历顺序。

具体算法如下：-如果二叉树为空，则直接返回。

-递归地中序遍历左子树。

-访问根节点，并输出或进行其他操作。

-递归地中序遍历右子树。

3.二叉树的后序遍历算法：后序遍历是指先访问左子树，再访问右子树，最后访问根节点的遍历顺序。

具体算法如下：-如果二叉树为空，则直接返回。

-递归地后序遍历左子树。

-递归地后序遍历右子树。

-访问根节点，并输出或进行其他操作。

4.二叉树的层序遍历算法：层序遍历是按照从上到下、从左到右的顺序逐层遍历二叉树的节点。

具体算法如下：-如果二叉树为空，则直接返回。

-创建一个队列，将根节点入队。

-循环执行以下步骤，直到队列为空：-出队并访问当前节点，并输出或进行其他操作。

-若当前节点的左子节点不为空，则将左子节点入队。

-若当前节点的右子节点不为空，则将右子节点入队。

5.二叉树的深度算法：二叉树的深度是指从根节点到叶节点的最长路径的节点数。

具体算法如下：-如果二叉树为空，则深度为0。

-否则，递归地计算左子树的深度和右子树的深度，然后取较大的值加上根节点的深度作为二叉树的深度。

6.二叉树的查找算法：二叉树的查找可以使用前序、中序或后序遍历来完成。

具体算法如下：-如果二叉树为空，则返回空。

-如果当前节点的值等于目标值，则返回当前节点。

-否则，先在左子树中递归查找，如果找到则返回找到的节点。

-如果左子树中未找到，则在右子树中递归查找，如果找到则返回找到的节点。

-如果左右子树中都未找到，则返回空。

7.二叉树的插入算法：二叉树的插入可以使用递归或循环来实现。

具体算法如下：-如果二叉树为空，则创建一个新节点作为根节点，并返回根节点。

二叉树的遍历实验报告一、实验目的1.了解二叉树的基本概念和性质；2.理解二叉树的遍历方式以及它们的实现方法；3.学会通过递归和非递归算法实现二叉树的遍历。

二、实验内容1.二叉树的定义在计算机科学中，二叉树是一种重要的数据结构，由节点及它们的左右儿子组成。

没有任何子节点的节点称为叶子节点，有一个子节点的节点称为一度点，有两个子节点的节点称为二度点。

二叉树的性质：1.每个节点最多有两个子节点；2.左右子节点的顺序不能颠倒，左边是父节点的左子节点，右边是父节点的右子节点；3.二叉树可以为空，也可以只有一个根节点；4.二叉树的高度是从根节点到最深叶子节点的层数；5.二叉树的深度是从最深叶子节点到根节点的层数；6.一个深度为d的二叉树最多有2^(d+1) -1个节点，其中d>=1；7.在二叉树的第i层上最多有2^(i-1)个节点，其中i>=1。

2.二叉树的遍历方式二叉树的遍历是指从根节点出发，按照一定的顺序遍历二叉树中的每个节点。

常用的二叉树遍历方式有三种：前序遍历、中序遍历和后序遍历。

前序遍历：先遍历根节点，再遍历左子树，最后遍历右子树；中序遍历：先遍历左子树，再遍历根节点，最后遍历右子树；后序遍历：先遍历左子树，再遍历右子树，最后遍历根节点。

递归算法：利用函数调用，递归实现二叉树的遍历；非递归算法：利用栈或队列，对二叉树进行遍历。

三、实验步骤1.创建二叉树数据结构并插入节点；2.实现二叉树的前序遍历、中序遍历、后序遍历递归算法；3.实现二叉树的前序遍历、中序遍历、后序遍历非递归算法；4.测试算法功能。

四、实验结果1.创建二叉树数据结构并插入节点为了测试三种遍历方式的算法实现，我们需要创建一个二叉树并插入节点，代码如下：```c++//定义二叉树节点struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}};递归算法是实现二叉树遍历的最简单方法，代码如下：```c++//前序遍历非递归算法vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> s;vector<int> res;if (!root) return res;s.push(root);while (!s.empty()) {TreeNode* tmp = s.top();s.pop();res.push_back(tmp->val);if (tmp->right) s.push(tmp->right);if (tmp->left) s.push(tmp->left);}return res;}4.测试算法功能return 0;}```测试结果如下：preorderTraversal: 4 2 1 3 6 5 7inorderTraversal: 1 2 3 4 5 6 7postorderTraversal: 1 3 2 5 7 6 4preorderTraversalNonRecursive: 4 2 1 3 6 5 7inorderTraversalNonRecursive: 1 2 3 4 5 6 7postorderTraversalNonRecursive: 1 3 2 5 7 6 4本次实验通过实现二叉树的递归和非递归遍历算法，加深了对二叉树的理解，并熟悉了遍历算法的实现方法。

⼆叉树的四种遍历算法⼆叉树作为⼀种重要的数据结构，它的很多算法的思想在很多地⽅都⽤到了，⽐如STL算法模板，⾥⾯的优先队列、集合等等都⽤到了⼆叉树⾥⾯的思想，先从⼆叉树的遍历开始：看⼆叉树长什么样⼦：我们可以看到这颗⼆叉树⼀共有七个节点0号节点是根节点1号节点和2号节点是0号节点的⼦节点，1号节点为0号节点的左⼦节点，2号节点为0号节点的右⼦节点同时1号节点和2号节点⼜是3号节点、四号节点和五号节点、6号节点的双亲节点五号节点和6号节点没有⼦节点（⼦树），那么他们被称为‘叶⼦节点’这就是⼀些基本的概念⼆叉树的遍历⼆叉树常⽤的遍历⽅式有：前序遍历、中序遍历、后序遍历、层序遍历四种遍历⽅式，不同的遍历算法，其思想略有不同，我们来看⼀下这四种遍历⽅法主要的算法思想：1、先序遍历⼆叉树顺序：根节点 –> 左⼦树 –> 右⼦树，即先访问根节点，然后是左⼦树，最后是右⼦树。

上图中⼆叉树的前序遍历结果为：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 62、中序遍历⼆叉树顺序：左⼦树 –> 根节点 –> 右⼦树，即先访问左⼦树，然后是根节点，最后是右⼦树。

上图中⼆叉树的中序遍历结果为：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 63、后续遍历⼆叉树顺序：左⼦树 –> 右⼦树 –> 根节点，即先访问左⼦树，然后是右⼦树，最后是根节点。

上图中⼆叉树的后序遍历结果为：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 04、层序遍历⼆叉树顺序：从最顶层的节点开始，从左往右依次遍历，之后转到第⼆层，继续从左往右遍历，持续循环，直到所有节点都遍历完成上图中⼆叉树的层序遍历结果为：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6下⾯是四种算法的伪代码：前序遍历：preOrderParse(int n) {if(tree[n] == NULL)return ; // 如果这个节点不存在，那么结束cout << tree[n].w ; // 输出当前节点内容preOrderParse(tree[n].leftChild); // 递归输出左⼦树preOrderParse(tree[n].rightChild); // 递归输出右⼦树}中序遍历inOrderParse(int n) {if(tree[n] == NULL)return ; // 如果这个节点不存在，那么结束inOrderParse(tree[n].leftChild); // 递归输出左⼦树cout << tree[n].w ; // 输出当前节点内容inOrderParse(tree[n].rightChild); // 递归输出右⼦树}pastOrderParse(int n) {if(tree[n] == NULL)return ; // 如果这个节点不存在，那么结束pastOrderParse(tree[n].leftChild); // 递归输出左⼦树pastOrderParse(tree[n].rightChild); // 递归输出右⼦树cout << tree[n].w ; // 输出当前节点内容}可以看到前三种遍历都是直接通过递归来完成，⽤递归遍历⼆叉树简答⽅便⽽且好理解，接下来层序遍历就需要动点脑筋了，我们如何将⼆叉树⼀层⼀层的遍历输出？其实在这⾥我们要借助⼀种数据结构来完成：队列。