跳至正文
View Categories

2 min read

主要内容 #

  1. 二叉树的后序遍历
  2. 实现代码

1. 二叉树的后序遍历 #

后序遍历二叉树，指的是从根结点出发，按照以下步骤访问树中的每个结点：

  1. 优先进入当前结点的左子树，以同样的步骤遍历左子树中的结点；
  2. 如果当前结点没有左子树，则进入它的右子树，以同样的步骤遍历右子树中的结点；
  3. 直到当前结点的左子树和右子树都遍历完后，才访问该结点。

以下图所示的二叉树为例：

后序遍历这棵二叉树的过程是：

从根节点 A 出发，进入该结点的左子树；
    进入结点 B 的左子树，遍历左子树中的结点：
        进入结点 D 的左子树，但该结点没有左孩子；
        进入结点 D 的右子树，但该结点没有右子树；
        访问结点 D；
    进入结点 B 的右子树，遍历右子树中的结点：
        进入结点 E 的左子树，但该结点没有左孩子；
        进入结点 E 的右子树，但该结点没有右孩子；
        访问结点 E；
    访问结点 B；
进入结点 A 的右子树，遍历右子树中的结点：
    进入结点 C 的左子树，遍历左子树中的结点：
        进入结点 F 的左子树，但该结点没有左孩子；
        进入结点 F 的右子树，但该结点没有右子树；
        访问结点 F；
    进入结点 C 的右子树，遍历右子树中的结点：
        进入结点 G 的左子树，但该结点没有左孩子；
        进入结点 G 的右子树，但该结点没有右孩子；
        访问结点 G；
    访问结点 C；
访问结点 A。

最终，后序遍历图 1 中的二叉树，访问各个结点的顺序是：
D E B F G C A

2. 实现代码 #

后序遍历二叉树，最常用的实现方式就是递归。对于顺序表存储的二叉树，递归实现后序遍历的 C 语言程序为：

#include <stdio.h>
#define NODENUM 7
#define ElemType int
//自定义 BiTree 类型，表示二叉树
typedef ElemType BiTree[NODENUM];

//存储二叉树
void InitBiTree(BiTree T) {
    ElemType node;
    int i = 0;
    printf("按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:");
    while (scanf("%d", &node))
    {
        T[i] = node;
        i++;
    }
}

//后序遍历二叉树
void PostOrderTraverse(BiTree T, int p) {
    if ((p * 2 + 1 < NODENUM) && (T[p * 2 + 1] != 0)) {
        PostOrderTraverse(T, 2 * p + 1);
    }
    if ((p * 2 + 2 < NODENUM) && (T[p * 2 + 2] != 0)) {
        PostOrderTraverse(T, 2 * p + 2);
    }
    printf("%d ", T[p]);
}

int main() {
    int res;
    BiTree T = { 0 };
    InitBiTree(T);
    PostOrderTraverse(T,0);
    return 0;
}
/*
* 运行结果为：
* 按照层次从左往右输入树中结点的值，0 表示空结点，# 表示输入结束:1 2 3 4 5 6 7 #
* 4 5 2 6 7 3 1
*/

对于链表存储的二叉树，递归实现后序遍历的 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) {
    int num;
    scanf("%d", &num);
    //如果输入的值为 0，表示无此结点
    if (num == 0) {
        *T = NULL;
    }
    else
    {
        //创建新结点
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = num;
        CreateBiTree(&((*T)->lchild));//创建该结点的左孩子
        CreateBiTree(&((*T)->rchild));//创建该结点的右孩子
    }
}

//后序遍历
void PostOrderTraverse(BiTree T) {
    if (T) {
        PostOrderTraverse(T->lchild);//遍历左孩子
        PostOrderTraverse(T->rchild);//遍历右孩子
        printf("%d ", T->data);
    }
}

//后序遍历二叉树，释放树占用的内存
void DestroyBiTree(BiTree T) {
    if (T) {
        DestroyBiTree(T->lchild);//销毁左孩子
        DestroyBiTree(T->rchild);//销毁右孩子
        free(T);//释放结点占用的内存
    }
}

int main() {
    BiTree Tree;
    CreateBiTree(&Tree);
    PostOrderTraverse(Tree);
    DestroyBiTree(Tree);
    return 0;
}

/*
* 运行结果为：
* 1 2 4 0 0 5 0 0 3 6 0 0 7 0 0
* 4 5 2 6 7 3 1
*/
What are your Feelings