二叉树遍历_递归算法底层的实现使用的是什么存储结构-程序员宅基地

技术标签：算法

二叉树的四种遍历算法
冰河世纪20 2019-03-12 15:46:06 22461 收藏 30
展开

本文转自：http://data.biancheng.net/view/194.html
二叉树

简单地理解，满足以下两个条件的树就是二叉树：

本身是有序树；
树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2；

二叉树的性质

经过前人的总结，二叉树具有以下几个性质：

二叉树中，第 i 层最多有 2i-1 个结点。
如果二叉树的深度为 K，那么此二叉树最多有 2K-1 个结点。
二叉树中，终端结点数（叶子结点数）为 n0，度为 2 的结点数为 n2，则 n0=n2+1。

性质 3 的计算方法为：对于一个二叉树来说，除了度为 0 的叶子结点和度为 2 的结点，剩下的就是度为 1 的结点（设为 n1），那么总结点 n=n0+n1+n2。
同时，对于每一个结点来说都是由其父结点分支表示的，假设树中分枝数为 B，那么总结点数 n=B+1。而分枝数是可以通过 n1 和 n2 表示的，即 B=n1+2n2。所以，n 用另外一种方式表示为 n=n1+2n2+1。
两种方式得到的 n 值组成一个方程组，就可以得出 n0=n2+1。

满二叉树
如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。图1即为满二叉树。

下图是本节二叉树用例图1：
在这里插入图片描述
满二叉树除了满足普通二叉树的性质，还具有以下性质：

满二叉树中第 i 层的节点数为 2n-1 个。
深度为 k 的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
具有 n 个节点的满二叉树的深度为 log2(n+1)。

完全二叉树
如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

在这里插入图片描述
如图 a) 所示是一棵完全二叉树，图 b) 由于最后一层的节点没有按照从左向右分布，因此只能算作是普通的二叉树。

完全二叉树除了具有普通二叉树的性质，它自身也具有一些独特的性质，比如说，n 个结点的完全二叉树的深度为 ⌊log2n⌋+1。

⌊log2n

log2n⌋ 表示取小于 log2nlog2n 的最大整数。例如，⌊log24log24⌋ = 2，而 ⌊log25

log25⌋ 结果也是 2。

对于任意一个完全二叉树来说，如果将含有的结点按照层次从左到右依次标号（如图 3a)），对于任意一个结点 i ，完全二叉树还有以下几个结论成立：

当 i>1 时，父亲结点为结点 [i/2] 。（i=1 时，表示的是根结点，无父亲结点）
如果 2i>n（总结点的个数） ，则结点 i 肯定没有左孩子（为叶子结点）；否则其左孩子是结点 2i 。
如果 2i+1>n ，则结点 i 肯定没有右孩子；否则右孩子是结点 2i+1 。

二叉树的顺序存储结构

二叉树的存储结构有两种，分别为顺序存储和链式存储。本节先介绍二叉树的顺序存储结构。

二叉树的顺序存储，指的是使用顺序表（数组）存储二叉树。需要注意的是，顺序存储只适用于完全二叉树。换句话说，只有完全二叉树才可以使用顺序表存储。因此，如果我们想顺序存储普通二叉树，需要提前将普通二叉树转化为完全二叉树。

有读者会说，满二叉树也可以使用顺序存储。要知道，满二叉树也是完全二叉树，因为它满足完全二叉树的所有特征。

普通二叉树转完全二叉树的方法很简单，只需给二叉树额外添加一些节点，将其"拼凑"成完全二叉树即可。如下图所示：
在这里插入图片描述
左侧是普通二叉树，右侧是转化后的完全（满）二叉树。解决了二叉树的转化问题，接下来学习如何顺序存储完全（满）二叉树。

完全二叉树的顺序存储，仅需从根节点开始，按照层次依次将树中节点存储到数组即可。
二叉树的链式存储结构

在这里插入图片描述
如上图所示，此为一棵普通的二叉树，若将其采用链式存储，则只需从树的根节点开始，将各个节点及其左右孩子使用链表存储即可。因此，上图对应的链式存储结构如下图所示：
在这里插入图片描述
由图可知，采用链式存储二叉树时，其节点结构由 3 部分构成（如下图所示）：

指向左孩子节点的指针（Lchild）；
节点存储的数据（data）；
指向右孩子节点的指针（Rchild）；
在这里插入图片描述
表示该节点结构的 C 语言代码为：

typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
struct BiTNode *parent;
}BiTNode,*BiTree;

链式存储结构对应的 C 语言代码为：

#include <stdio.h>
#include <stdlib.h>
#define TElemType int
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
T=(BiTNode)malloc(sizeof(BiTNode));
(*T)->data=1;
(T)->lchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(T)->rchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->rchild->data=3;
(*T)->rchild->lchild=NULL;
(*T)->rchild->rchild=NULL;
(T)->lchild->lchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->lchild->lchild->data=4;
(*T)->lchild->rchild=NULL;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf("%d",Tree->lchild->lchild->data);
return 0;
}

其实，二叉树的链式存储结构远不止上图所示的这一种。例如，在某些实际场景中，可能会做 “查找某节点的父节点” 的操作，这时可以在节点结构中再添加一个指针域，用于各个节点指向其父亲节点，如下图所示：
在这里插入图片描述

这样的链表结构，通常称为三叉链表。

利用上图所示的三叉链表，我们可以很轻松地找到各节点的父节点。因此，在解决实际问题时，用合适的链表结构存储二叉树，可以起到事半功倍的效果。
二叉树先序遍历

二叉树先序遍历的实现思想是：

访问根节点；
访问当前节点的左子树；
若当前节点无左子树，则访问当前节点的右子树；

以图 1 为例，采用先序遍历的思想遍历该二叉树的过程为：

访问该二叉树的根节点，找到 1；
访问节点 1 的左子树，找到节点 2；
访问节点 2 的左子树，找到节点 4；
由于访问节点 4 左子树失败，且也没有右子树，因此以节点 4 为根节点的子树遍历完成。但节点 2 还没有遍历其右子树，因此现在开始遍历，即访问节点 5；
由于节点 5 无左右子树，因此节点 5 遍历完成，并且由此以节点 2 为根节点的子树也遍历完成。现在回到节点 1，并开始遍历该节点的右子树，即访问节点 3；
访问节点 3 左子树，找到节点 6；
由于节点 6 无左右子树，因此节点 6 遍历完成，回到节点 3 并遍历其右子树，找到节点 7；
节点 7 无左右子树，因此以节点 3 为根节点的子树遍历完成，同时回归节点 1。由于节点 1 的左右子树全部遍历完成，因此整个二叉树遍历完成；

因此，图 1 中二叉树采用先序遍历得到的序列为：

1 2 4 5 3 6 7

递归实现

二叉树的先序遍历采用的是递归的思想，因此可以递归实现，其 C 语言实现代码为：

#include <stdio.h>
#include <string.h>
#define TElemType int
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
T=(BiTNode)malloc(sizeof(BiTNode));
(*T)->data=1;
(T)->lchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->rchild=(BiTNode)malloc(sizeof(BiTNode));

(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;

}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//先序遍历
void PreOrderTraverse(BiTree T){
if (T) {
displayElem(T);//调用操作结点数据的函数方法
PreOrderTraverse(T->lchild);//访问该结点的左孩子
PreOrderTraverse(T->rchild);//访问该结点的右孩子
}
//如果结点为空，返回上一层
return;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf(“先序遍历: \n”);
}

非递归实现

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现，其 C 语言实现代码为：

#include <stdio.h>
#include <string.h>
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
T=(BiTNode)malloc(sizeof(BiTNode));
(*T)->data=1;
(T)->lchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->rchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(T)->lchild->lchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->lchild->rchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(T)->rchild->lchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(T)->rchild->rchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->rchild->rchild->data=7;
(T)->rchild->rchild->lchild=NULL;
(T)->rchild->rchild->rchild=NULL;
(T)->lchild->lchild->data=4;
(T)->lchild->lchild->lchild=NULL;
(T)->lchild->lchild->rchild=NULL;
}
//前序遍历使用的进栈函数
void push(BiTNode a,BiTNode elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top–;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode getTop(BiTNode**a){
return a[top];
}
//先序遍历非递归算法
void PreOrderTraverse(BiTree Tree){
BiTNode a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {
p=getTop(a);//取栈顶元素
pop();//弹栈
while § {
displayElem§;//调用结点的操作函数
//如果该结点有右孩子，右孩子进栈
if (p->rchild) {
push(a,p->rchild);
}
p=p->lchild;//一直指向根结点最后一个左孩子
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf(“先序遍历: \n”);
PreOrderTraverse(Tree);
}

二叉树中序遍历

二叉树中序遍历的实现思想是：

访问当前节点的左子树；
访问根节点；
访问当前节点的右子树；

以图 1 为例，采用中序遍历的思想遍历该二叉树的过程为：

访问该二叉树的根节点，找到 1；
遍历节点 1 的左子树，找到节点 2；
遍历节点 2 的左子树，找到节点 4；
由于节点 4 无左孩子，因此找到节点 4，并遍历节点 4 的右子树；
由于节点 4 无右子树，因此节点 2 的左子树遍历完成，访问节点 2；
遍历节点 2 的右子树，找到节点 5；
由于节点 5 无左子树，因此访问节点 5 ，又因为节点 5 没有右子树，因此节点 1 的左子树遍历完成，访问节点 1 ，并遍历节点 1 的右子树，找到节点 3；
遍历节点 3 的左子树，找到节点 6；
由于节点 6 无左子树，因此访问节点 6，又因为该节点无右子树，因此节点 3 的左子树遍历完成，开始访问节点 3 ，并遍历节点 3 的右子树，找到节点 7；
由于节点 7 无左子树，因此访问节点 7，又因为该节点无右子树，因此节点 1 的右子树遍历完成，即整棵树遍历完成；

因此，图 1 中二叉树采用中序遍历得到的序列为：

4 2 5 1 6 3 7

递归实现

二叉树的中序遍历采用的是递归的思想，因此可以递归实现，其 C 语言实现代码为：

(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;

}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//中序遍历
void INOrderTraverse(BiTree T){
if (T) {
INOrderTraverse(T->lchild);//遍历左孩子
displayElem(T);//调用操作结点数据的函数方法
INOrderTraverse(T->rchild);//遍历右孩子
}
//如果结点为空，返回上一层
return;
}

int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf(“中序遍历算法: \n”);
INOrderTraverse(Tree);
}

非递归实现

而递归的底层实现依靠的是栈存储结构，因此，二叉树的先序遍历既可以直接采用递归思想实现，也可以使用栈的存储结构模拟递归的思想实现。

中序遍历的非递归方式实现思想是：从根结点开始，遍历左孩子同时压栈，当遍历结束，说明当前遍历的结点没有左孩子，从栈中取出来调用操作函数，然后访问该结点的右孩子，继续以上重复性的操作。

除此之外，还有另一种实现思想：中序遍历过程中，只需将每个结点的左子树压栈即可，右子树不需要压栈。当结点的左子树遍历完成后，只需要以栈顶结点的右孩子为根结点，继续循环遍历即可。

两种非递归方法实现二叉树中序遍历的代码实现为：

#include <stdio.h>
#include <string.h>
#define TElemType int
int top=-1;//top变量时刻表示栈顶元素所在位置
//构造结点的结构体
typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
//初始化树的函数
void CreateBiTree(BiTree *T){
T=(BiTNode)malloc(sizeof(BiTNode));
(*T)->data=1;
(T)->lchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->rchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->lchild->data=2;
(T)->lchild->lchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->lchild->rchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(T)->rchild->lchild=(BiTNode)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(T)->rchild->lchild->rchild=NULL;
(T)->rchild->rchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->rchild->rchild->data=7;
(T)->rchild->rchild->lchild=NULL;
(T)->rchild->rchild->rchild=NULL;
(T)->lchild->lchild->data=4;
(T)->lchild->lchild->lchild=NULL;
(T)->lchild->lchild->rchild=NULL;
}
//前序和中序遍历使用的进栈函数
void push(BiTNode a,BiTNode elem){
a[++top]=elem;
}
//弹栈函数
void pop( ){
if (top==-1) {
return ;
}
top–;
}
//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode elem){
printf("%d ",elem->data);
}
//拿到栈顶元素
BiTNode getTop(BiTNode**a){
return a[top];
}
//中序遍历非递归算法
void InOrderTraverse1(BiTree Tree){
BiTNode a[20];//定义一个顺序栈
BiTNode * p;//临时指针
push(a, Tree);//根结点进栈
while (top!=-1) {//top!=-1说明栈内不为空，程序继续运行
while ((p=getTop(a)) &&p){//取栈顶元素，且不能为NULL
push(a, p->lchild);//将该结点的左孩子进栈，如果没有左孩子，NULL进栈
}
pop();//跳出循环，栈顶元素肯定为NULL，将NULL弹栈
if (top!=-1) {
p=getTop(a);//取栈顶元素
pop();//栈顶元素弹栈
displayElem§;
push(a, p->rchild);//将p指向的结点的右孩子进栈
}
}
}
//中序遍历实现的另一种方法
void InOrderTraverse2(BiTree Tree){
BiTNode a[20];//定义一个顺序栈
BiTNode * p;//临时指针
p=Tree;
//当p为NULL或者栈为空时，表明树遍历完成
while (p || top!=-1) {
//如果p不为NULL，将其压栈并遍历其左子树
if § {
push(a, p);
p=p->lchild;
}
//如果p==NULL，表明左子树遍历完成，需要遍历上一层结点的右子树
else{
p=getTop(a);
pop();
displayElem§;
p=p->rchild;
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf("\n中序遍历算法1: \n");
InOrderTraverse1(Tree);
printf("\n中序遍历算法2: \n");
InOrderTraverse2(Tree);
}

二叉树后序遍历

二叉树后序遍历的实现思想是：从根节点出发，依次遍历各节点的左右子树，直到当前节点左右子树遍历完成后，才访问该节点元素。

如图 1 中，对此二叉树进行后序遍历的操作过程为：

从根节点 1 开始，遍历该节点的左子树（以节点 2 为根节点）；
遍历节点 2 的左子树（以节点 4 为根节点）；
由于节点 4 既没有左子树，也没有右子树，此时访问该节点中的元素 4，并回退到节点 2 ，遍历节点 2 的右子树（以 5 为根节点）；
由于节点 5 无左右子树，因此可以访问节点 5 ，并且此时节点 2 的左右子树也遍历完成，因此也可以访问节点 2；
此时回退到节点 1 ，开始遍历节点 1 的右子树（以节点 3 为根节点）；
遍历节点 3 的左子树（以节点 6 为根节点）；
由于节点 6 无左右子树，因此访问节点 6，并回退到节点 3，开始遍历节点 3 的右子树（以节点 7 为根节点）；
由于节点 7 无左右子树，因此访问节点 7，并且节点 3 的左右子树也遍历完成，可以访问节点 3；
节点 1 的左右子树也遍历完成，可以访问节点 1；
到此，整棵树的遍历结束。

由此，对图 1 中二叉树进行后序遍历的结果为：

4 5 2 6 7 3 1

递归实现

后序遍历的递归实现代码为：

(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;
(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;
(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;
(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;

}

//模拟操作结点元素的函数，输出结点本身的数值
void displayElem(BiTNode* elem){
printf("%d ",elem->data);
}
//后序遍历
void PostOrderTraverse(BiTree T){
if (T) {
PostOrderTraverse(T->lchild);//遍历左孩子
PostOrderTraverse(T->rchild);//遍历右孩子
displayElem(T);//调用操作结点数据的函数方法
}
//如果结点为空，返回上一层
return;
}
int main() {
BiTree Tree;
CreateBiTree(&Tree);
printf(“后序遍历: \n”);
PostOrderTraverse(Tree);
}

非递归实现

递归算法底层的实现使用的是栈存储结构，所以可以直接使用栈写出相应的非递归算法。

后序遍历是在遍历完当前结点的左右孩子之后，才调用操作函数，所以需要在操作结点进栈时，为每个结点配备一个标志位。当遍历该结点的左孩子时，设置当前结点的标志位为 0，进栈；当要遍历该结点的右孩子时，设置当前结点的标志位为 1，进栈。

这样，当遍历完成，该结点弹栈时，查看该结点的标志位的值：如果是 0，表示该结点的右孩子还没有遍历；反之如果是 1，说明该结点的左右孩子都遍历完成，可以调用操作函数。

完整实现代码为：

//后序遍历非递归算法
typedef struct SNode{
BiTree p;
int tag;
}SNode;
//后序遍历使用的进栈函数
void postpush(SNode *a,SNode sdata){
a[++top]=sdata;
}
//后序遍历函数
void PostOrderTraverse(BiTree Tree){
SNode a[20];//定义一个顺序栈
BiTNode * p;//临时指针
int tag;
SNode sdata;
p=Tree;
while (p||top!=-1) {
while § {
//为该结点入栈做准备
sdata.p=p;
sdata.tag=0;//由于遍历是左孩子，设置标志位为0
postpush(a, sdata);//压栈
p=p->lchild;//以该结点为根结点，遍历左孩子
}
sdata=a[top];//取栈顶元素
pop();//栈顶元素弹栈
p=sdata.p;
tag=sdata.tag;
//如果tag0，说明该结点还没有遍历它的右孩子
if (tag0) {
sdata.p=p;
sdata.tag=1;
postpush(a, sdata);//更改该结点的标志位，重新压栈
p=p->rchild;//以该结点的右孩子为根结点，重复循环
}
//如果取出来的栈顶元素的tag==1，说明此结点左右子树都遍历完了，可以调用操作函数了
else{
displayElem§;
p=NULL;
}
}
}
int main(){
BiTree Tree;
CreateBiTree(&Tree);
printf(“后序遍历: \n”);
PostOrderTraverse(Tree);
}

二叉树层次遍历

层次遍历方式：按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根结点开始，依次将其左孩子和右孩子入队。而后每次队列中一个结点出队，都将其左孩子和右孩子入队，直到树中所有结点都出队，出队结点的先后顺序就是层次遍历的最终结果。

层次遍历的实现过程
例如，层次遍历图 1 中的二叉树：

首先，根结点 1 入队；
根结点 1 出队，出队的同时，将左孩子 2 和右孩子 3 分别入队；
队头结点 2 出队，出队的同时，将结点 2 的左孩子 4 和右孩子 5 依次入队；
队头结点 3 出队，出队的同时，将结点 3 的左孩子 6 和右孩子 7 依次入队；
不断地循环，直至队列内为空。

实现代码

#include <stdio.h>
#define TElemType int
//初始化队头和队尾指针开始时都为0
int front=0,rear=0;

typedef struct BiTNode{
TElemType data;//数据域
struct BiTNode *lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;
void CreateBiTree(BiTree *T){
T=(BiTNode)malloc(sizeof(BiTNode));
(*T)->data=1;
(T)->lchild=(BiTNode)malloc(sizeof(BiTNode));
(T)->rchild=(BiTNode)malloc(sizeof(BiTNode));

(*T)->lchild->data=2;
(*T)->lchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->lchild->rchild->data=5;
(*T)->lchild->rchild->lchild=NULL;
(*T)->lchild->rchild->rchild=NULL;

(*T)->rchild->data=3;
(*T)->rchild->lchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->lchild->data=6;
(*T)->rchild->lchild->lchild=NULL;
(*T)->rchild->lchild->rchild=NULL;

(*T)->rchild->rchild=(BiTNode*)malloc(sizeof(BiTNode));
(*T)->rchild->rchild->data=7;
(*T)->rchild->rchild->lchild=NULL;
(*T)->rchild->rchild->rchild=NULL;

(*T)->lchild->lchild->data=4;
(*T)->lchild->lchild->lchild=NULL;
(*T)->lchild->lchild->rchild=NULL;

}
//入队函数
void EnQueue(BiTree a,BiTree node){
a[rear++]=node;
}
//出队函数
BiTNode DeQueue(BiTNode** a){
return a[front++];
}
//输出函数
void displayNode(BiTree node){
printf("%d ",node->data);
}
int main() {
BiTree tree;
//初始化二叉树
CreateBiTree(&tree);
BiTNode * p;
//采用顺序队列，初始化创建队列数组
BiTree a[20];
//根结点入队
EnQueue(a, tree);
//当队头和队尾相等时，表示队列为空
while(front<rear) {
//队头结点出队
p=DeQueue(a);
displayNode§;
//将队头结点的左右孩子依次入队
if (p->lchild!=NULL) {
EnQueue(a, p->lchild);
}
if (p->rchild!=NULL) {
EnQueue(a, p->rchild);
}
}
return 0;
}

本文链接：https://blog.csdn.net/Nail_CN/article/details/106324254

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Docker 快速上手学习入门教程_docker菜鸟教程-程序员宅基地

文章浏览阅读2.5w次，点赞6次，收藏50次。官方解释是，docker 容器是机器上的沙盒进程，它与主机上的所有其他进程隔离。所以容器只是操作系统中被隔离开来的一个进程，所谓的容器化，其实也只是对操作系统进行欺骗的一种语法糖。_docker菜鸟教程

电脑技巧：Windows系统原版纯净软件必备的两个网站_msdn我告诉你-程序员宅基地

文章浏览阅读5.7k次，点赞3次，收藏14次。该如何避免的，今天小编给大家推荐两个下载Windows系统官方软件的资源网站，可以杜绝软件捆绑等行为。该站提供了丰富的Windows官方技术资源，比较重要的有MSDN技术资源文档库、官方工具和资源、应用程序、开发人员工具（Visual Studio 、SQLServer等等）、系统镜像、设计人员工具等。总的来说，这两个都是非常优秀的Windows系统镜像资源站，提供了丰富的Windows系统镜像资源，并且保证了资源的纯净和安全性，有需要的朋友可以去了解一下。这个非常实用的资源网站的创建者是国内的一个网友。_msdn我告诉你

vue2封装对话框el-dialog组件_<el-dialog 封装成组件 vue2-程序员宅基地

文章浏览阅读1.2k次。vue2封装对话框el-dialog组件_

MFC 文本框换行_c++ mfc同一框内输入二行怎么换行-程序员宅基地

文章浏览阅读4.7k次，点赞5次，收藏6次。MFC 文本框换行标签： it mfc 文本框1.将Multiline属性设置为True2.换行是使用"\r\n" (宽字符串为L"\r\n")3.如果需要编辑并且按Enter键换行,还要将 Want Return 设置为 True4.如果需要垂直滚动条的话将Vertical Scroll属性设置为True,需要水平滚动条的话将Horizontal Scroll属性设_c++ mfc同一框内输入二行怎么换行

redis-desktop-manager无法连接redis-server的解决方法_redis-server doesn't support auth command or ismis-程序员宅基地

文章浏览阅读832次。检查Linux是否是否开启所需端口，默认为6379，若未打开，将其开启：以root用户执行iptables -I INPUT -p tcp --dport 6379 -j ACCEPT如果还是未能解决，修改redis.conf，修改主机地址：bind 192.168.85.**；然后使用该配置文件，重新启动Redis服务./redis-server redis.conf..._redis-server doesn't support auth command or ismisconfigured. try

实验四数据选择器及其应用-程序员宅基地

文章浏览阅读4.9k次。济大数电实验报告_数据选择器及其应用

随便推点

灰色预测模型matlab_MATLAB实战|基于灰色预测河南省社会消费品零售总额预测-程序员宅基地

文章浏览阅读236次。1研究内容消费在生产中占据十分重要的地位，是生产的最终目的和动力，是保持省内经济稳定快速发展的核心要素。预测河南省社会消费品零售总额，是进行宏观经济调控和消费体制改变创新的基础，是河南省内人民对美好的全面和谐社会的追求的要求，保持河南省经济稳定和可持续发展具有重要意义。本文建立灰色预测模型，利用MATLAB软件，预测出2019年~2023年河南省社会消费品零售总额预测值分别为21881...._灰色预测模型用什么软件

log4qt-程序员宅基地

文章浏览阅读1.2k次。12.4-在Qt中使用Log4Qt输出Log文件，看这一篇就足够了一、为啥要使用第三方Log库，而不用平台自带的Log库二、Log4j系列库的功能介绍与基本概念三、Log4Qt库的基本介绍四、将Log4qt组装成为一个单独模块五、使用配置文件的方式配置Log4Qt六、使用代码的方式配置Log4Qt七、在Qt工程中引入Log4Qt库模块的方法八、获取示例中的源代码一、为啥要使用第三方Log库，而不用平台自带的Log库首先要说明的是，在平时开发和调试中开发平台自带的“打印输出”已经足够了。但_log4qt

100种思维模型之全局观思维模型-67_计算机中对于全局观的-程序员宅基地

文章浏览阅读786次。全局观思维模型，一个教我们由点到线，由线到面，再由面到体，不断的放大格局去思考问题的思维模型。_计算机中对于全局观的

线程间控制之CountDownLatch和CyclicBarrier使用介绍_countdownluach于cyclicbarrier的用法-程序员宅基地

文章浏览阅读330次。一、CountDownLatch介绍CountDownLatch采用减法计算；是一个同步辅助工具类和CyclicBarrier类功能类似，允许一个或多个线程等待，直到在其他线程中执行的一组操作完成。二、CountDownLatch俩种应用场景：场景一：所有线程在等待开始信号(startSignal.await()),主流程发出开始信号通知，既执行startSignal.countDown()方法后;所有线程才开始执行；每个线程执行完发出做完信号，既执行do..._countdownluach于cyclicbarrier的用法

自动化监控系统Prometheus&Grafana_-自动化监控系统prometheus&grafana实战-程序员宅基地

文章浏览阅读508次。Prometheus 算是一个全能型选手，原生支持容器监控，当然监控传统应用也不是吃干饭的，所以就是容器和非容器他都支持，所有的监控系统都具备这个流程，_-自动化监控系统prometheus&grafana实战

React 组件封装之 Search 搜索_react search-程序员宅基地

文章浏览阅读4.7k次。输入关键字，可以通过键盘的搜索按钮完成搜索功能。_react search