二叉树的构建、遍历及c++实现

二叉树遍历

1. 二叉树有四种遍历方式，先序遍历、中序遍历、后序遍历和层次遍历，其中层次遍历类似于图结构里面的广度优先搜索BFS，先序遍历类似于深度优先搜索DFS。
2. 遍历的实现方式有两种，递归实现和非递归实现。
3. 不管采用递归实现还是非递归实现，都需要用到栈，区别在于一个用系统栈，一个是自定义栈结构，空间复杂度都有栈深度有关，为O(logn)，由于每一个节点都需要遍历到，时间复杂度均为O(n)。
4. 有一种更高阶的遍历实现，完全不用栈结构，充分利用原有的二叉树叶子结点的左右孩子指针（nullptr），他就是Morris遍历，空间复杂度为O(1), 时间复杂度为O(n)。

二叉树构建

1. 给定二叉树的任意一个遍历序列（先序/中序/后序），可以唯一确定一颗二叉树吗？
   结论：不可以。
2. 给定二叉树的任意两个遍历序列（先序/中序/后序），可以唯一确定一颗二叉树吗？
   结论：只有给定中序序列和另外两个序列中的一个，才可以。
3. 给定一颗扩充二叉树的任意一个遍历序列（先序/中序/后序），可以唯一确定一颗二叉树吗？
   结论：只有先序或后序才可以，中序不可以，因为扩充二叉树的先序相当于“先序+中序”，后序相当于“后序+中序”。

解释：先序和后序序列可以确认根，但无法确认左右子树；中序序列可以确认左右子树，但无法确认根；要唯一确定一个二叉树，需要两个关键要素：一个是根，另一个是左右子树，因此只有给定中序序列和先序或中序序列，才可以唯一确定一个二叉树。
构建过程举例如下：
先序序列：abdgcefh
中序序列：dgbaechf
step1: 构建根
根据先序序列确定根为a，根据中序序列确定左子树为dgb，右子树为echf,根用红色标识，左子树用灰色，右子树用绿色。
先序序列：abdgcefh
中序序列：dgbaechf

step2 递归构建左子树
先序序列：bdg
中序序列：dgb
根据先序序列确定根为b，根据中序序列确定左子树为dg，右子树为空。
先序序列：bdg
中序序列：dgb

先序序列：dg
中序序列：dg
根据先序序列确定根为d，根据中序序列确定左子树为空，右子树为g。
先序序列：dg
中序序列：dg

step3 递归构建右子树
先序序列：cefh
中序序列：echf
根据先序序列确定根为c，根据中序序列确定左子树为e，右子树为hf。
先序序列：cefh
中序序列：echf

先序序列：fh
中序序列：hf
根据先序序列确定根为f，根据中序序列确定左子树为h，右子树为空。
先序序列：fh
中序序列：hf

c++实现原码

#include <iostream>
#include <stack>
#include <queue>

struct binaryTreeNode
{
    char element = '#';
    struct binaryTreeNode *left = nullptr;
    struct binaryTreeNode *right = nullptr;

    binaryTreeNode(int _element) : element(_element) {}
};

//先序创建二叉树
void createBinaryTree(binaryTreeNode * &tree)
{
    char tmp;
    std::cin >> tmp;
    if (tmp == '#') {
        tree = nullptr;
        return;
    }
    tree = new binaryTreeNode(tmp);
    createBinaryTree(tree->left);
    createBinaryTree(tree->right);
    return;
}

//先序遍历
void preOrder(binaryTreeNode *tree)
{
    if (tree) {
        std::cout << " " << tree->element;
        preOrder(tree->left);
        preOrder(tree->right);
    }
    return;
}

//先序遍历-非递归
void preOrderNonRecursive(binaryTreeNode *tree)
{
    std::stack<binaryTreeNode *> sta;
    binaryTreeNode *p = tree;
    while (!sta.empty() || p != nullptr) {
        while (p != nullptr) {
            std::cout << " " << p->element;
            sta.push(p);
            p = p->left;
        }
        if (!sta.empty()) {
            p = sta.top();
            sta.pop();
            p = p->right;
        }
    }
    return;
}

//中序遍历
void inOrder(binaryTreeNode *tree)
{
    if (tree) {
        inOrder(tree->left);
        std::cout << " " << tree->element;
        inOrder(tree->right);
    }
    return;
}

//中序遍历-非递归
void inOrderNonRecursive(binaryTreeNode *tree)
{
    std::stack<binaryTreeNode *> sta;
    binaryTreeNode *p = tree;
    while(!sta.empty() || p != nullptr) {
        while (p != nullptr) {
            sta.push(p);
            p = p->left;
        }
        if (!sta.empty()) {
            p = sta.top();
            sta.pop();
            std::cout << " " << p->element;
            p = p->right;
        }
    }
}

//后序遍历
void postOrder(binaryTreeNode *tree)
{
    if (tree) {
        postOrder(tree->left);
        postOrder(tree->right);
        std::cout << " " << tree->element;
    }
    return;
}

//后序遍历-非递归
void postOrderNonRecursive(binaryTreeNode * tree)
{
    std::stack<binaryTreeNode *> sta;
    binaryTreeNode *cur = nullptr;
    binaryTreeNode *pre = nullptr;
    sta.push(tree);
    while (!sta.empty()) {
        cur = sta.top();
        if ((cur->left == nullptr && cur->right == nullptr) || 
            (pre != nullptr && (pre == cur->left || pre == cur->right))) {
                //没有孩子节点或孩子节点已经被访问过了，直接输出
                std::cout << " " << cur->element;
		sta.pop();
                pre = cur;
        } else {
            if (cur->right != nullptr) {
                sta.push(cur->right);
            }
            if (cur->left != nullptr) {
                sta.push(cur->left);
            }
        }
    }
    return;
}

//层次遍历
void levelOrder(binaryTreeNode *tree)
{
    std::queue<binaryTreeNode *> que;
    while (tree) {
        std::cout << " " << tree->element;
        if (tree->left) {
            que.push(tree->left);
        }
        if (tree->right) {
            que.push(tree->right);
        }
        if (que.empty()) {
            return;
        }
        tree = que.front();
        que.pop();
    }
}

int main(void)
{
    //a b d # g # # # c e # # f h # # #
    std::cout << "请输入先序序列用于构建二叉树:" << std::endl;
    binaryTreeNode *tree = nullptr;
    createBinaryTree(tree);
    
    std::cout << "先序遍历结果:        ";
    preOrder(tree);
    std::cout << std::endl;

    std::cout << "先序遍历结果(非递归):";
    preOrderNonRecursive(tree);
    std::cout << std::endl;

    std::cout << "中序遍历结果:        ";
    inOrder(tree);
    std::cout << std::endl;

    std::cout << "中序遍历结果(非递归):";
    inOrderNonRecursive(tree);
    std::cout << std::endl;

    std::cout << "后序遍历结果:        ";
    postOrder(tree);
    std::cout << std::endl;

    std::cout << "后序遍历结果(非递归):";
    postOrderNonRecursive(tree);
    std::cout << std::endl;

    std::cout << "层次遍历结果(非递归):";
    levelOrder(tree);
    std::cout << std::endl;

    return 0;
}

运行结果：

请输入先序序列用于构建二叉树:
a b d # g # # # c e # # f h # # #
先序遍历结果: a b d g c e f h
先序遍历结果(非递归): a b d g c e f h
中序遍历结果: d g b a e c h f
中序遍历结果(非递归): d g b a e c h f
后序遍历结果: g d b e h f c a
后序遍历结果(非递归): g d b e h f c a
层次遍历结果(非递归): a b c d e f g h

参考：

1. 二叉树的先序、中序、后序遍历序列
2. 二叉树的前序遍历、中序遍历、后序遍历、层序遍历的时间复杂度和空间复杂度
3. Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）
4. 扩展二叉树（#号法）先序和后续可确定二叉树，中序不可
5. 经典书籍：《数据结构、算法与应用》第二版（Sartaj Sahni)