乐趣区

关于二叉树:二叉树创建后如何使用递归和栈遍历二叉树

jiezi

0. 前言

前文【二叉树的概念和原理】次要介绍了树的相干概念和原理，本文次要内容为二叉树的创立及遍历的代码实现，其中包含递归遍历和栈遍历。

1. 二叉树的实现思路

1.0. 顺序存储——数组实现

后面介绍了满二叉树和齐全二叉树，咱们对其进行了编号——从 0 到 n 的不中断程序编号，而恰好，数组也有一个这样的编号 —— 数组下标，只有咱们把二者联结起来，数组就能存储二叉树了。

那么非满、非齐全二叉树怎么应用数组存储呢？

咱们能够在二叉树中补上一些虚构的结点，结构进去一个满 / 齐全二叉树来，存储到数组中时，虚构的结点对应的数组元素不存储数据（# 代表虚构的不存在）。如下图：

这样存储的毛病是，数组中可能会有大量空间未用到，造成节约。

1.1. 链式存储——链表实现

咱们画树的图时，采纳的都是结点加箭头的形式，结点示意数据元素，箭头示意结点之间的关系，清晰明了。如果你对链表相熟，那么必定能觉察到这是典型的链式构造。链式构造完满解决了程序构造中可能会节约空间的毛病，而且也不会有数组空间限度。

上面来剖析一下结点的构造。

树的结点包含一个数据元素和若干指向其子树分支。二叉树的结点绝对简略，包含：

  • 数据元素
  • 左子树分支（结点的左孩子）
  • 右子树分支（结点的右孩子）

怎么来实现呢？单链表的结点是应用一个指向其后继结点的指针来示意其关系的。同样地，咱们也能够应用指针来示意结点和其左孩子、右孩子的关系。

剖析到这，二叉树的结点就清晰了：

  • 一个存储数据的变量——data
  • 一个指向其左孩子结点的指针——left_child
  • 一个指向其右孩子结点的指针——right_child

用 C 语言的构造体实现二叉树的结点（为了不便起见，咱们的数据全为字符类型）：

/* 二叉树的结点的构造体 */
typedef struct Node {
    char data; // 数据域
    struct Node *left_child; // 左孩子指针
    struct Node *right_child; // 右孩子指针
} TreeNode;

2. 二叉树的发明

二叉树的定义是递归的定义，所以如果你想要发明一个二叉树，也能够借助递归去发明。如何递归发明呢？在事实中，一棵树先长根、再长枝干、最初长叶子。咱们用代码发明树时，也恪守这个准则，即先发明根结点，而后左子树，最初右子树。整个过程和先序遍历类似。

我以前写过的文章中有二叉树创立过程的动态图，这里不再赘述。

这里以发明下图中的树为例：

阐明：当咱们看到如左图的二叉树时，要立刻能脑补出对应的右图。# 结点是什么？

后面咱们曾经画出了相似的图，过后是 NULL 结点，它的作用是标识某个结点没有孩子，它是咱们虚构进去的。在理论应用 C 语言发明二叉树时，须要应用 # 或者什么其余的符号来代替 NULL.

上图的先序遍历程序为：ABDEGCF，如果加上 # 结点，则为：ABD##EG###C#F##. 咱们依照此程序来发明二叉树。

代码如下：

/**
 * 发明一个二叉树
 * root: 指向根结点的指针的指针
 */
void create_binary_tree(TreeNode **root)
{
    char elem;
    scanf("%c", &elem);
    if (elem == '#') {*root = NULL;} else {*root = create_tree_node(elem); // 发明一个二叉结点
        create_binary_tree(&((*root)->left_child));
        create_binary_tree(&((*root)->right_child));
    }
}

请留神，函数 create_binary_tree 承受的是一个指向根结点的指针的指针，至于为什么要应用指针的指针，理由在介绍单链表的初始化时曾经解释了。

3. 二叉树的遍历

在文章【二叉树的概念和原理】中曾经介绍了遍历的原理了，上面应用 C 语言实现它。

3.0. 遍历本质

二叉树的定义是递归的定义，即在二叉树的定义中又用到了二叉树的定义。所以无论是在发明二叉树，还是在遍历二叉树，咱们要做的只有三件事：拜访根结点、找左子树、找右子树。所谓先序、中序、后序遍历，无非是这三件事的程序罢了。

3.1. 递归实现

咱们如果应用递归代码，很容易就能实现遍历，而且代码十分简洁。

【先序遍历】

/**
 * 先序遍历
 * root: 指向根结点的指针
 */
void preorder_traversal(TreeNode *root)
{if (root == NULL) { // 若二叉树为空，做空操作
        return;
    }
    printf("%c", root->data); // 拜访根结点
    preorder_traversal(root->left_child); // 递归遍历左子树
    preorder_traversal(root->right_child); // 递归遍历右子树
}

【中序遍历】

/**
 * 中序遍历
 * root: 指向根结点的指针
 */
void inorder_traversal(TreeNode *root)
{if (root == NULL) { // 若二叉树为空，做空操作
        return;
    }
    inorder_traversal(root->left_child); // 递归遍历左子树
    printf("%c", root->data); // 拜访根结点
    inorder_traversal(root->right_child); // 递归遍历右子树
}

【后序遍历】

/**
 * 后序遍历
 * root: 指向根结点的指针
 */
void postorder_traversal(TreeNode *root)
{if (root == NULL) { // 若二叉树为空，做空操作
        return;
    }
    postorder_traversal(root->left_child); // 递归遍历左子树
    postorder_traversal(root->right_child); // 递归遍历右子树
    printf("%c", root->data); // 拜访根结点
}

事实上，大部分应用递归做的事，应用栈也能够做到。上面介绍遍历的栈实现。

3.2. 栈实现

咱们利用了栈的后进先出的个性，

栈实现的代码较简单，受篇幅限度，这里只介绍先序遍历和后序遍历，具体代码请移步至代码仓库查看。

【先序遍历】

咱们的树的结点是要全副都入栈的（暂不论程序如何），那么入栈的条件是什么？就是该结点能够被看作某棵树（子树）的根结点的时候。即，curr 指针指向的结点肯定为某颗树（子树）的根结点。

在【二叉树的概念和原理】中，咱们曾经看到了，遍历完某个子树时，肯定要回到其双亲结点。这种回溯如何实现？能够利用栈的先进后出、后进先出的特点，这个特点能在栈中完满保留结点在树中父子关系，栈顶元素即为以后子树的双亲结点。

/**
 * 应用栈实现的先序遍历
 */
void preorder_traversal_by_stack(TreeNode *root)
{
    // 发明并初始化栈
    Stack stack;
    init_stack(&stack);
    
    TreeNode *curr = root; // 辅助指针 curr

    while (curr != NULL || !stack_is_empty(&stack)) {while (curr != NULL) {printf("%c", curr->data); // 打印根结点
            push(&stack, curr); // 根结点入栈
            curr = curr->left_child; // 进入左子树
        }
        if (!stack_is_empty(&stack)) {pop(&stack, &curr); // 出栈，回到上一个根结点
            curr = curr->right_child; // 进入右子树
        }
    }
}

【后序遍历】

后序遍历相较于前序和中序较为麻烦，不像前序和中序遍历那样。因为前序和种序的根结点在右子树之前，所以咱们能够在出栈的时候同时进行打印根结点和进入右子树。

后序遍历的根结点在右子树之后，这就要求咱们再遍历完左子树后，先返回到根结点，而后进入右子树，遍历完右子树之后，再回到根结点，能力打印它。

要害之处还在于左子树、右子树、根结点的程序。

所以当 curr 指针遍历完左子树后，咱们不能间接将根结点出栈，而是先从栈顶读取到根结点，而后 curr 指针返回到根结点，而后 curr 指针进入右子树进行遍历，当右子树遍历实现后，将根结点出栈，能力打印根结点。

这样一来，后序遍历就有两次回到根结点的动作，且这两次的后续动作不一样。第一次通过读取栈顶回到根结点，而后进入右子树；第二次通过出栈回到根结点，而后打印根结点。

这样看似解决了后序遍历的程序问题，但其实又失去了一个新的问题，即，咱们如何晓得右子树被遍历完了？

咱们有两次回到根结点的动作，对于写代码的人来说，咱们晓得两次回到根结点之后该干什么，晓得右子树是否被遍历完了。然而对于 curr 指针来说，它不晓得，两次回到根结点，它都不晓得右子树是否被遍历实现了。

此时，对于 curr 指针来说，就像有两条路摆在它背后让它抉择其中一条，它难以抉择。如果当其中一条有过它的足迹，那么它就很容易抉择那条没走过的路了。

所以咱们当初还须要一个“足迹”指针——prev，prev 指针用来记录 curr 拜访过的结点。

当 curr 指针第二次回到根结点的时候，一看，哦！我的足迹留在那呢！（prev 指针指在右子树那里）curr 指针就间接释怀打印根结点了。

/**
 * 应用栈实现的后序遍历
 */
void postorder_traversal_by_stack(TreeNode *root)
{
    Stack stack;
    init_stack(&stack);

    TreeNode *curr = root; // 辅助指针 curr，记录以后拜访结点
    TreeNode *prev = NULL; // 足迹指针 prev，记录上一个拜访过的结点

    while (curr != NULL || !stack_is_empty(&stack)) {if (curr != NULL) {push(&stack, curr); // 根结点入栈
            curr = curr->left_child; // 进入左子树
        } else {get_top(&stack, &curr); // 读栈顶元素，不是出栈
            // 右子树不为空，且右子树没被遍历
            if (curr->right_child != NULL && curr->right_child != prev) { 
                curr = curr->right_child; // 进入右子树
                push(&stack, curr); // 根结点入栈
                curr = curr->left_child; // 进入左子树
            } else { // 右子树已被遍历或者右子树为空，能够打印根结点了
                pop(&stack, &curr); // 根结点出栈
                printf("%c", curr->data); // 打印根结点
                prev = curr; // 记录
                curr = NULL; // 置空，进入下一轮循环
            }
        }
    }
}

以上代码中的栈的相干函数这里不再给出，具体代码请移步至代码仓库（文末获取）。

4. 总结

递归的代码尽管简洁，然而对老手来说却有点难以了解，这是因为接触的太少。栈的代码相对来说容易了解一些，但代码比较复杂，特地是后序遍历的代码。

不过当你真正了解了二叉树的定义、概念、原理之后，代码相干的问题就不再是问题了，最终只落在六个字上——无他，惟手熟尔。

以上就是二叉树的创立和遍历的实现。

残缺代码请移步至 GitHub | Gitee 获取。

如有谬误，还请斧正。

如果感觉写的不错，能够点个赞和关注。后续会有更多数据结构和算法相干文章。

退出移动版