数据结构——遍历二叉树

目录

什么是遍历二叉树

 根据遍历序列确定二叉树

例题（根据先序中序以及后序中序求二叉树）

 遍历的算法实现

先序遍历

中序遍历 

后序遍历

遍历算法的分析

二叉树的层次遍历

二叉树遍历算法的应用

二叉树的建立

复制二叉树

 计算二叉树深度

 计算二叉树结点总数

---

什么是遍历二叉树

遍历定义-- 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次(又称周游)。

• “访问”的含义很广，可以是对结点作各种处理，如：输出结点的信息、修改结点的数据值等，但要求这种访问不破坏原来的数据结构。

遍历目的-- 得到树中所有结点的一个线性排列。

遍历用途--它是树结构插入、删除、修改、查找和排序运算的前提，是二又树一切运算的基础和核心。

遍历方法

依次遍历二叉树的三个组成部分，便是遍历了整个二叉树。

若规定先左后右，则只有三种情况：

由二叉树的递归定义可知，遍历左子树和遍历右子树可如同遍历二叉树一样“递归”进行。

先序（DLR）遍历二叉树的操作定义：

(1)访问根结点；

(2)先序遍历左子树；

(3)先序遍历右子树。

注：根的左子树遍历完（左子树的左子树、左子树的右子树...）才轮到根的右子树进行遍历。

 示例如下：

 中序遍历二叉树的操作定义：

若二叉树为空，则空操作；否则

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

示例：

 后序遍历二叉树的操作定义：

若二叉树为空，则空操作;否则

(1)后序遍历左子树；

(2)后序遍历右子树；

(3)访问根结点。

 示例：

例题：

解析

先序： 先根结点A，再遍历根A的左子树，左子树遍历完，才轮到遍历右子树，左子树的根B，再根B的左子树，以D为根，再根D的左子树，没有就根D的右子树G，根G的左子树和右子树都没有，根D的树遍历完，再根B的右子树，没有，就可以遍历根A的右子树了，根C的左子树先遍历，以根E的树，根E的左子树没有，遍历根E的右子树，以H为根的左子树和右子树都没有，遍历根C的右子树，以F为根的左右子树都没有，先序遍历结束。

中序：先以A为根的左子树，再B为根的左子树，再以D为根的左子树，没有就输出根D，再根D的右子树G输出，以B为根的左子树结束就输出根B，再遍历B的右子树，没有就输出根A，再遍历根A的右子树，以C为根的左子树，再以E为根的左子树，没有就输出根E，根E的右子树H，根H的左子树没有，输出根H，根H的右子树没有，根C的左子树遍历完毕，输出根C，再遍历根C的右子树，以F为根的左子树没有，输出根F，根F的右子树没有。

后序：以A为根的左子树先遍历，以B为根的左子树先遍历，以D为根的左子树先遍历，没有就遍历根D的右子树，根G的左子树不存在，右子树也不存在，后序输出根结点G，根D的左右子树都遍历完了，输出根结点D，B的左子树遍历完，遍历其右子树，右子树不存在，输出根结点B，根A的左子树遍历完，遍历其右子树，根C的左子树先遍历，根E的左子树先遍历，不存在，遍历根E的右子树，根H的左右子树都不存在，输出根结点H，E的左右子树都遍历完，输出根结点E，C的左子树遍历完，遍历其右子树，根F的左右子树都不存在，输出根结点F，根C的左右结点都遍历完，输出根结点C，根A的左右子树都遍历完，输出根结点A。

请写出下图所示二叉树的先序、中序和后序遍历顺序。

 根据遍历序列确定二叉树

• 若二叉树中各结点的值均不相同，则二叉树结点的先序序列、中序序列和后序序列都是唯一的。
• 由二叉树的先序序列和中序序列，或由二叉树的后序序列和中序序列可以确定唯一一棵二叉树

例题（根据先序中序以及后序中序求二叉树）

已知先序和中序序列求二叉树

例：已知二叉树的先序和中序序列，构造出相应的二叉树

先序：A  B  C  D  E  F  G  H  I  J

中序：C  D  B  F  E  A  I  H  G  J

首先从先序中可以知道这棵大树的根为A，已知根A后，从中序序列中可以得知C  D  B  F  E是这棵大树的左子树，I  H  G  J是这棵大树的右子树；再从先序序列中B  C  D  E  F得知B是左子树的根，G  H  I  J是右子树的根，再从中序序列中可以知道C  D是根为B的树的左子树，F  E是右子树，以此类推，可以构造相对应的二叉树。

已知后序和中序序列求二叉树

 例：已知一棵二叉树的

中序序列：B  D  C  E  A  F  H  G

后序序列：D  E  C  B  H  G  F  A，请画出这棵二叉树。

类似的，我们可以先从后序序列中知道这棵大树的根结点为A，再从中序序列中得知B  D  C  E是以A为根结点的左子树，F  H  G是其右子树，再从后序序列D  E  C  B中知道B是左子树的根结点，F是左子树H  G  F的根结点，再从中序序列可以得出以B为根结点的树没有左子树，其右子树为D  C E，以F为根结点的左子树不存在，其右子树为H  G，以此类推可以画出完整的二叉树。

 遍历的算法实现

先序遍历

 步骤：

 先序的遍历序列为ABCD

算法实现

Status PreOrderTraverse(BiTree T)
{if (T == NULL)return OK;//空二叉树else{visit(T);//访问根结点PreOrderTraverse(T->lchild);//递归遍历左子树PreOrderTraverse(T->rchild);//递归遍历右子树}
}

过程：指针T指向我们的二叉树的根结点，把根结点的指针T传递给前序遍历，判断T是否为空，此时不为空，输出A结点的数据域上的值，然后对左子树进行先序遍历，将当前结点的左孩子的地址传递给它自身，调用自身函数后，输出当前指针的数据域的值，也就是B结点的值，接下来访问B结点的左子树，为空返回，然后再访问B的右子树，此时T指向D结点，不为空输出其值，D结点的左右子树都为空，返回，依次返回到以A结点的树，其左子树遍历完毕，继续遍历其右子树。

中序遍历 

 

 步骤：

 中序遍历序列：BDAC

算法实现

Status InOrderTraverse(BiTree T)
{if (T == NULL)return OK;else{InOrderTraverse(T->lchild);//递归遍历左子树visit(T);//访问根结点InOrderTraverse(T->rchild);//递归遍历右子树}
}

后序遍历

 

步骤：

后序遍历序列：DBCA

算法实现

Status PostOrderTraverse(BiTree T)
{if (T == NULL)return OK;else{PostOrderTraverse(T->lchild);//递归遍历左子树PostOrderTraverse(T->rchild);//递归遍历右子树visit(T);//访问根结点}
}

遍历算法的分析

 如果去掉输出语句，从递归的角度看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的时机不同。

从虚线的出发点到终点的路径上，每个结点经过3次。

第1次经过时访问=先序遍历

第2次经过时访问=中序遍历

第3次经过时访问=后序遍历

 

二叉树的层次遍历

第一个访问根结点a，然后从左到右访问第二层，a的孩子b和f，再访问孩子的孩子。

 对于一棵二叉树，从根结点开始，按从上到下、从左到右的顺序访问每一个结点。

每一个结点仅仅访问一次。

 算法设计思路：使用一个队列

 1、将根结点进队；
 2、队不空时循环：从队列中出列一个结点*p，访问它；

• 若它有左孩子结点，将左孩子结点进队；
• 若它有右孩子结点，将右孩子结点进队。

 

遍历描述：首先，根结点a入队， 队列开始出队，第一个结点是

a，a出队，然后把a的左右孩子b、f入队，再从队列中拿出最前一个结点b出队，把它的左右孩子c、d入队，再拿出f出队，把它的左孩子g入队，现在队列中还有cdg，把c出队，它的左右孩子入队，没有就拿下一个结点出队，以此类推。

代码实现：

 使用队列类型定义如下

typedef struct
{BTNode data[MaxSize];//存放队中元素int front, rear;//队头和队尾指针
}SqQueue; //顺序循环队列类型

二叉树层次遍历算法：

void LevelOrder(BTNode* b)
{BTNode* p;SqQueue* qu;InitQueue(qu);//初始化队列enQueue(qu,b);//根结点指针进入队列while (!QueueEmpty(qu)){deQueue(qu,p);//出队结点printf("%c",p->data);//访问结点pif (p->lchild != NULL)enQueue(qu,p->lchild);//有左孩子时将其出队if (p->rchild != NULL)enQueue(qu, p->rchild);//有右孩子时将其出队}
}

二叉树遍历算法的应用

二叉树的建立

• 按先序遍历序列建立二叉树的二叉链表

例：已知先序序列为：ABCDEGF

（1）从键盘输入二叉树的结点信息，建立二叉树的存储结构；

（2）在建立二叉树的过程中按照二叉树先序方式建立；

用#表示空字符

代码实现

Status CreateBiTree(BiTree& T)//链式存储
{scanf(&ch);//cin>>ch;if (ch == "#")T = NULL;else{if (!(T=(BiTNode*)malloc(sizeof(BiTree))))//从内存当中分配一个结点空间exit(OVERFLOW);//T=new NiTNode;T->data = ch;CreateBiTree(T->lchild);//构造左孩子CreateBiTree(T->rchild);//构造右孩子}return OK;
}//CreateBiTree

复制二叉树

如果是空树，递归结束；

否则，申请新结点空间，复制根结点

• 递归复制左子树
• 递归复制右子树 

代码实现

int Copy(BiTree T, BiTree& NewT)
{if (T == NULL){NewT = NULL;return 0;//如果是空树，返回0}else{NewT = new BiTNode; NewT->data = T->data;//复制结点数据Copy(T->lchild, NewT->lchild);//递归复制左子树Copy(T->rchild, NewT->rchild);//递归复制右子树}
}

 计算二叉树深度

• 如果是空树，则深度为0；
• 否则，递归计算左子树的深度记为m，递归计算右子树的深度记为n，二叉树的深度则为m与n的较大者加1。 

代码实现

int Depth(BiTree T) {if (T == NULL)return 0;else {m = Depth(T->lchild);//求左子树的深度n = Depth(T->rchild);//求右子树的深度if (m > n)return (m + 1);else      return (n + 1);}
}

 计算二叉树结点总数

•  如果是空树，则结点个数为0；
• 否则，结点个数为左子树的结点个数+右子树的结点个数再+1。

代码实现

int NodeCount(BiTree T) {if (T == NULL)return 0;else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}

计算二叉树叶子结点数

• 如果是空树，则叶子结点个数为0；
• 否则，为左子树的叶子结点个数+右子树的叶子结点个数。 

代码实现

int LeadCount(BiTree T) {if (T == NULL) return 0;if (T->lchild == NULL && T->rchild == NULL)return 1;//如果是叶子结点返回1elsereturn LeafCount(T->lchild) +LeafCount(T->rchild);
}