1.1 先序遍历
遍历过程为:
访问根结点
先序遍历其左子树;
先序遍历其右子树.
- /* c 语言实现 */
- void PreOrderTraversal (BinTree BT)
- {
- if (BT) {
- printf("%d", BT->Data);
- PreOrderTraversal(BT->Left);
- PreOrderTraversal(BT->Right);
- }
- }
先序遍历: A (B D F E)(C G H I)
1.2 中序遍历
遍历过程为:
中序遍历其左子树;
访问根节点;
中序遍历其右子树.
- /* c 语言实现 */
- void InOrderTraversal (BinTree BT)
- {
- if (BT) {
- InOrderTraversal(BT->Left);
- printf("%d", BT->Data);
- InOrderTracersal(BT->Right);
- }
- }
中序遍历:(D B E F)A(G H C I)
1.3 后序遍历
遍历过程为:
后序遍历其左子树;
后序遍历其右子树;
访问根结点.
- /* c 语言实现 */
- void PostOrderTraversal (BinTree BT)
- {
- if (BT) {
- PostOrderTraversal(BT->Left);
- PostORderTraversal(BT->Right);
- printf("%d", BT->Data);
- }
- }
后序遍历:(D E F B)(H G I C)A
1.4 小结
先序, 中序和后序遍历过程: 遍历过程中经过结点的路线一样, 只是访问各结点的时机不同.
图中在从入口到出口的曲线上用 *,☆,△三种符号分别标记出了先序, 中序和后序访问各结点的时刻.
二, 二叉树的非递归遍历
非递归算法实现的基本思路: 使用堆栈
2.1 中序遍历非递归遍历算法
遇到一个结点, 就把它压栈, 并去遍历它的左子树;
当左子树遍历结束后, 从栈顶弹出这个结点并访问它;
然后按其右指针再去中序遍历该结点的右子树.
- /* c 语言实现 */
- void InOrderTraversal(BinTree BT)
- {
- BinTree T = BT;
- Stack S = CreateStack(MaxSize); // 创建并初始化堆栈 S
- while (T || !IsEmpty(S)){
- while (T) { // 一直向左并将沿途结点压入堆栈
- Push(S, T);
- T = T->Left;
- }
- if (!IsEmpty(S)){
- T = Pop(S); // 结点弹出堆栈
- printf("]", T->Data); // (访问) 打印结点
- T = T->Right; // 转向右子树
- }
- }
- }
2.2 先序遍历的非递归遍历算法
- /* c 语言实现 */
- void InOrderTraversal(BinTree BT)
- {
- BinTree T = BT;
- Stack S = CreateStack(MaxSize); // 创建并初始化堆栈 S
- while (T || !IsEmpty(s)){
- while (T) { // 一直向左并将沿途结点压入堆栈
- printf("]", T->Data); // (访问) 打印结点
- Push(S, T);
- T = T->Left;
- }
- if (!IsEmpty(S)){
- T = Pop(S); // 结点弹出堆栈
- T = T->Right; // 转向右子树
- }
- }
- }
三, 层序遍历
二叉树遍历的核心问题: 二维结构的线性化. 即从结点访问其左, 右儿子结点, 访问左儿子后, 如果根结点信息丢失, 右儿子结点也会随之丢失, 因此需要一个存储结构保存暂时不访问的结点, 这个存储结构可以为堆栈, 也可以是队列.
3.1 队列实现
遍历从根节点开始, 首先将根节点入队, 然后开始执行循环: 结点出队, 访问该结点, 其左右儿子入队.
层序基本过程: 先根结点入队, 然后:
从队列中取出一个元素;
访问该元素所指结点;
若该元素所指结点的左, 右孩子结点非空, 则将其左, 右孩子的指针顺序入队.
- /* c 语言实现 */
- void LevelOrderTraversal (BinTree BT)
- {
- Queue Q; BinTree T;
- if (!BT) return; // 若是空树则直接返回
- Q = CreateQueue(MaxSize); // 创建并初始化队列 Q
- AddQ(Q, BT);
- while (!IsEmptyQ(Q))
- {
- T = DeleteQ(Q);
- printf("%d\n", T->Data); // 访问取出队列的结点
- if (T->Left) AddQ(Q, T->Left);
- if (T->Right) AddQ(Q, T->Right);
- }
- }
四, 实际应用
4.1 遍历二叉树的应用: 输出二叉树中的叶子节点
在二叉树的遍历算法中检测结点的左右子树是否都为空.
- /* c 语言实现 */
- void PreOrderPrintLeaves (BinTree BT)
- {
- if (BT) {
- if (!BT->Left && !BT->Right)
- printf("%d", BT->Data);
- PreOrderPrintLeaves(BT->Left);
- PreOrderPrintLeaves(BT->Right);
- }
- }
4.2 求二叉树的高度
- /* c 语言实现 */
- int PostOrderGetHeight(BinTree BT)
- {
- int HL, HR, MaxH;
- if (BT) {
- HL = PostOrderGetHeight(BT->Left); // 求左子树的深度
- HR = PostOrderGetHeight(BT->Right); // 求右子树的深度
- MaxH = (HL> HR) ? HL : HR; // 取左右子树较大的深度
- return (MaxH + 1); // 返回树的深度
- }
- else return 0; // 空树深度为 0
- }
4.3 二元运算表达式树及其遍历
三种遍历可以得到三种不同的访问结果:
先序遍历得到前缀表达式:++a*bc*+*defg
中序遍历得到中缀表达式 (中缀表达式会受到运算符优先级的影响):a+b*c+d*e+f*g
后序遍历得到后缀表达式: abc*+de*f+g*+
4.4 由两种遍历序列确定二叉树
已知三种遍历中的任意两种遍历序列, 不能唯一确定一颗二叉树, 如果两种遍历序列中有中序遍历, 则可以唯一确定一颗二叉树.
对于给出的先序遍历序列为: AB 和后序遍历序列: BA, 可能有如下两种情况:
先序和中序遍历序列来确定一颗二叉树
根据先序遍历序列第一个结点确定根节点
根据根节点在中序遍历序列中分割出左右两个子序列
对左子树和右子树分别递归使用相同的方法继续分解
类似地, 后序和中序遍历序列也可以确定一颗二叉树.
来源: https://www.cnblogs.com/nickchen121/p/11516034.html