一、二叉树的定义

二叉树(Binary Tree) 是由n个结点构成的有限集(n≥0)，n=0时为空树，n>0时为非空树。对于非空树T：

• 有且仅有一个根结点；
• 除根结点外的其余结点又可分为两个不相交的子集TL和TR，分别称为T的左子树和右子树，且TL和TR本身又都是二叉树。

很明显该定义属于递归定义，所以有关二叉树的操作使用递归往往更容易理解和实现。

从定义也可以看出二叉树与一般树的区别主要是两点，

• 一是每个结点的度最多为2；
• 二是结点的子树有左右之分，不能随意调换，调换后又是一棵新的二叉树。

二、二叉树的形态

五种基本形态

从上面二叉树的递归定义可以看出，二叉树或为空，或为一个根结点加上两棵左右子树，因为两棵左右子树也是二叉树也可以为空，所以二叉树有5种基本形态：

三种特殊形态

三、二叉树的存储

存的目的是为了取，而取的关键在于如何通过父结点拿到它的左右子结点，不同存储方式围绕的核心也就是这。

1.顺序存储

使用一组地址连续的存储单元存储，例如数组。为了在存储结构中能得到父子结点之间的映射关系，二叉树中的结点必须按层次遍历的顺序存放。具体是：

• 对于完全二叉树，只需要自根结点起从上往下、从左往右依次存储。
• 对于非完全二叉树，首先将它变换为完全二叉树，空缺位置用某个特殊字符代替（比如#），然后仍按完全二叉树的存储方式存储。

假设将一棵二叉树按此方式存储到数组后，左子结点下标=2倍的父结点下标+1，右子节点下标=2倍的父结点下标+2。若数组某个位置处值为#，代表此处对应的结点为空。

可以看出顺序存储非常适合存储接近完全二叉树类型的二叉树，对于一般二叉树有很大的空间浪费，所以对于一般二叉树，一般用下面这种链式存储。

2.链式存储

对每个结点，除数据域外再多增加左右两个指针域，分别指向该结点的左孩子和右孩子结点，再用一个头指针指向根结点。对应的存储结构：

四、二叉树的创建与遍历（递归）

二叉树由三个基本单元组成：根结点，左子树，右子树，因此存在6种遍历顺序，若规定先左后右，则只有以下3种：

1.先序遍历

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

（1）访问根结点

（2）先序遍历左子树

（3）先序遍历右子树

2.中序遍历

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

（1）中序遍历左子树

（2）访问根结点

（3）中序遍历右子树

3.后序遍历

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

（1）后序遍历左子树

（2）后序遍历右子树

（3）访问根结点

从上可以看出先中后其实是相对根结点来说。

对于下面这棵二叉树，其遍历顺序：

先序：ABDEHCFIG

中序：DBHEAFICG

后序：DHEBIFGCA

4.实例

下面是将以下二叉树的顺序存储[A,B,C,D,E,F,G,#,#,H,#,#,I]转换为链式存储的代码，结点不存在用字符#表示，并分别遍历。

#include <iostream>
#include <vector>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

// 将二叉树的顺序存储变为链式存储
TreeNode* buildTree(std::vector<char>& arr, int index) {
    TreeNode* root = nullptr;
    if (index < arr.size()) {
        if (arr[index] == '#') {
            return nullptr;
        }
        root = new TreeNode(arr[index]);
        root->lchild = buildTree(arr, 2 * index + 1);
        root->rchild = buildTree(arr, 2 * index + 2);
    }
    return root;
}

// 先序遍历
void preOrderTraverse(TreeNode* T) {
    if (T != nullptr) {
        std::cout << T->data;
        preOrderTraverse(T->lchild);
        preOrderTraverse(T->rchild);
    }
}

// 中序遍历
void inOrderTraverse(TreeNode* T) {
    if (T != nullptr) {
        inOrderTraverse(T->lchild);
        std::cout << T->data;
        inOrderTraverse(T->rchild);
    }
}

// 后序遍历
void postOrderTraverse(TreeNode* T) {
    if (T != nullptr) {
        postOrderTraverse(T->lchild);
        postOrderTraverse(T->rchild);
        std::cout << T->data;
    }
}

int main() {
    std::vector<char> arr = { 'A', 'B', 'C', 'D', 'E', 'F', 'G', '#', '#', 'H', '#', '#', 'I' };
    TreeNode* T = buildTree(arr, 0);

    std::cout << "先序遍历-->";
    preOrderTraverse(T);
    std::cout << std::endl;

    std::cout << "中序遍历-->";
    inOrderTraverse(T);
    std::cout << std::endl;

    std::cout << "后序遍历-->";
    postOrderTraverse(T);
    std::cout << std::endl;

    return 0;
}

5.总结：

五、二叉树的非递归遍历

以上二叉树的创建及遍历都是通过递归实现，利用栈将递归转换为非递归可以将二叉树的递归遍历转换为非递归。

非递归的先序遍历

#include <iostream>
#include <stack>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

// 先序遍历（非递归）
void preOrderWithoutRecursion(TreeNode* T) {
    std::stack<TreeNode*> s;
    while (T != nullptr || !s.empty()) {
        if (T != nullptr) {
            std::cout << T->data;
            s.push(T);
            T = T->lchild;
        } else {
            T = s.top();
            s.pop();
            T = T->rchild;
        }
    }
}

int main() {
    // 构建二叉树
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');

    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = E;

    // 执行先序遍历（非递归）
    std::cout << "先序遍历（非递归）-->";
    preOrderWithoutRecursion(A);
    std::cout << std::endl;

    return 0;
}

非递归的中序遍历

#include <iostream>
#include <stack>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

// 中序遍历（非递归）
void inOrderWithoutRecursion(TreeNode* T) {
    std::stack<TreeNode*> s;
    while (T != nullptr || !s.empty()) {
        if (T != nullptr) {
            s.push(T);
            T = T->lchild;
        } else {
            T = s.top();
            s.pop();
            std::cout << T->data;
            T = T->rchild;
        }
    }
}

int main() {
    // 构建二叉树
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');

    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = E;

    // 执行中序遍历（非递归）
    std::cout << "中序遍历（非递归）-->";
    inOrderWithoutRecursion(A);
    std::cout << std::endl;

    return 0;
}

非递归的后序遍历

* 后序遍历要比先序中序遍历复杂一些，原因是需要判断上次访问的结点是位于左子树还是位于右子树。

* 若位于左子树，需要跳过根结点并进入右子树，回头再访问根结点。

* 若位于右子树，则直接访问根结点

#include <iostream>
#include <stack>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

// 后序遍历（非递归）
void postOrderWithoutRecursion(TreeNode* T) {
    std::stack<TreeNode*> s;
    TreeNode* lastVisit = nullptr;

    while (T != nullptr || !s.empty()) {
        while (T != nullptr) {
            s.push(T);
            T = T->lchild;
        }

        T = s.top();
        if (T->rchild == nullptr || T->rchild == lastVisit) {
            std::cout << T->data;
            lastVisit = T;
            s.pop();
            T = nullptr;
        } else {
            T = T->rchild;
        }
    }
}

int main() {
    // 构建二叉树
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');

    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = E;

    // 执行后序遍历（非递归）
    std::cout << "后序遍历（非递归）-->";
    postOrderWithoutRecursion(A);
    std::cout << std::endl;

    return 0;
}

六、二叉树的层序遍历（递归与非递归）

层次遍历是指从二叉树的根结点开始，按从上到下，从左到右的顺序遍历，也就是按从左往右的顺序先遍历第一层即根结点，再遍历第二层，…，直至最后一层。

还是上面的那棵二叉树，层序遍历顺序为：ABCDEFGHI。

递归

* 递归相比非递归优点就是思路清晰，代码易读，缺点是系统开销大。

* 但是层序遍历的递归实现反而使算法更复杂。

* 下面代码只提供层序遍历的一种递归思路，并不能算是真正意义上的递归。

#include <iostream>
#include <queue>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

// 层序遍历（递归）
void levelOrderWithRecursion(TreeNode* T) {
    int depth = getDepth(T);
    for (int i = 1; i <= depth; ++i) {
        levelOrder(T, i);
    }
}

void levelOrder(TreeNode* T, int level) {
    if (T == nullptr || level < 1) {
        return;
    }

    if (level == 1) {
        std::cout << T->data;
    }
    levelOrder(T->lchild, level - 1);
    levelOrder(T->rchild, level - 1);
}

int getDepth(TreeNode* T) {
    if (T == nullptr) {
        return 0;
    }

    int l = getDepth(T->lchild);
    int r = getDepth(T->rchild);
    return (l > r) ? (l + 1) : (r + 1);
}

int main() {
    // 构建二叉树
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');

    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = E;

    // 执行层序遍历（递归）
    std::cout << "层序遍历（递归）-->";
    levelOrderWithRecursion(A);
    std::cout << std::endl;

    return 0;
}

非递归

* 非递归遍历需要借助队列完成。

* 因为对同一层的结点A和结点B，如果A在B的左边先被遍历，那么下一层中A的孩子也一定在B的孩子左边先被遍历。

#include <iostream>
#include <queue>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

// 层序遍历（使用队列）
void levelOrderTraverse(TreeNode* T) {
    if (T == nullptr) {
        return;
    }

    std::queue<TreeNode*> q;
    TreeNode* node = nullptr;
    // 首先根结点入队
    q.push(T);

    while (!q.empty()) {
        // 队头出队
        node = q.front();
        q.pop();
        std::cout << node->data;

        // 左右子结点入队
        if (node->lchild != nullptr) {
            q.push(node->lchild);
        }
        if (node->rchild != nullptr) {
            q.push(node->rchild);
        }
    }
}

int main() {
    // 构建二叉树
    TreeNode* A = new TreeNode('A');
    TreeNode* B = new TreeNode('B');
    TreeNode* C = new TreeNode('C');
    TreeNode* D = new TreeNode('D');
    TreeNode* E = new TreeNode('E');

    A->lchild = B;
    A->rchild = C;
    B->lchild = D;
    B->rchild = E;

    // 执行层序遍历（使用队列）
    std::cout << "层序遍历（使用队列）-->";
    levelOrderTraverse(A);
    std::cout << std::endl;

    return 0;
}

六、根据遍历序列确定二叉树

（一）、根据先序、中序、后序遍历序列重建二叉树

从上面二叉树的遍历可以看出：如果二叉树中各结点值不同，那么先序、中序、以及后序遍历所得到的序列也是唯一。反过来，如果知道任意两种遍历序列，能否唯一确定这棵二叉树？

首先明确：只有先序中序，后序中序这两种组合可以唯一确定，先序后序不能。

如果知道的是先序中序，那么根据先序遍历先访问根结点的特点在中序序列中找到这个结点，该结点将中序序列分成两部分，左边是这个根结点的左子树中序序列，右边是这个根结点的右子树中序序列。根据这个序列，在先序序列中找到对应的左子序列和右子序列，根据先序遍历先访问根的特点又可以确定两个子序列的根结点，并根据这两个根结点可以将上次划分的两个中序子序列继续划分，如此下去，直到取尽先序序列中的结点时，便可得到对应的二叉树。

后序中序同理，区别是先序序列中第一个结点是根结点，而后序序列中最后一个结点是根结点。

先序和后序不能确定的原因在于不能确定根结点的左右子树。 比如先序序列AB，后序序列BA，根结点是A可以确定，但B是A的左子结点还是右子结点就确定不了了。

例题解释

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题代码：

*下面代码来源原题下面的解答，思路很强！

*用的是递归思想，每次将左右两棵子树当成新的子树进行处理，中序的左右子树开始结束索引很好找。

*前序的左右子树的开始结束索引通过根结点与中序中左右子树的大小来计算。

*然后递归求解，直到startPre>endPre||startIn>endIn说明子树整理完到。方法每次返回左子树和右子树的根结点。

*事实上startPre>endPre||startIn>endIn两条件任选其一即可。为什么？仔细想想！

#include <iostream>
#include <unordered_map>

class TreeNode {
public:
    int data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(int data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

TreeNode* reBuildBinaryTree(int pre[], int in[], int startPre, int endPre, int startIn, int endIn, std::unordered_map<int, int>& map) {
    if (startPre > endPre || startIn > endIn) {
        return nullptr;
    }

    TreeNode* root = new TreeNode(pre[startPre]);
    int index = map[root->data];

    root->lchild = reBuildBinaryTree(pre, in, startPre + 1, startPre + index - startIn, startIn, index - 1, map);
    root->rchild = reBuildBinaryTree(pre, in, startPre + index - startIn + 1, endPre, index + 1, endIn, map);

    return root;
}

TreeNode* reBuildBinaryTree(int pre[], int in[], int length) {
    if (pre == nullptr || in == nullptr || length <= 0) {
        return nullptr;
    }

    std::unordered_map<int, int> map;
    for (int i = 0; i < length; ++i) {
        map[in[i]] = i;
    }

    return reBuildBinaryTree(pre, in, 0, length - 1, 0, length - 1, map);
}

void preOrder(TreeNode* root) {
    if (root == nullptr) {
        return;
    }

    std::cout << root->data << " ";
    preOrder(root->lchild);
    preOrder(root->rchild);
}

int main() {
    int pre[] = {1, 2, 4, 7, 3, 5, 6, 8};
    int in[] = {4, 7, 2, 1, 5, 3, 8, 6};
    int length = sizeof(pre) / sizeof(pre[0]);

    TreeNode* root = reBuildBinaryTree(pre, in, length);

    std::cout << "重建的二叉树的前序遍历结果为：";
    preOrder(root);
    std::cout << std::endl;

    return 0;
}

七、二叉树遍历算法的应用

在上面二叉树递归遍历的基础上，将具体的访问结点操作换成其它的某些操作就可以实现另外的一些功能。

1.按先序遍历的顺序建立二叉树

比如图(a)中的这棵二叉树，左子树或右子树不存在用字符#表示，对应的先序序列[ABC##DE#G##F###]，那么根据这个先序序列，也可以还原这棵二叉树。

要注意的是下面代码看似没有递归出口，其实不是，当输入的先序序列已经可以唯一确定二叉树的时候程序也会随之停止调用并结束。（写这块的时候花了一个晚上，原因是方法里的参数开始传的是先序数组和数组下标，然后递归的时候数组下标+1，忽视了逐层往里递归的时候虽然数组下标也逐层+1正确但最内部递归结束返回次内部往另一个方向递归的时候传入的数组下标还是该层数组下标没有+1时的值）

#include <iostream>
#include <string>
#include <sstream>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

TreeNode* build(std::istringstream& iss) {
    std::string line;
    std::getline(iss, line);
    char ch = line[0];

    if (ch == '#') {
        return nullptr;
    }

    TreeNode* root = new TreeNode(ch);
    root->lchild = build(iss);
    root->rchild = build(iss);
    return root;
}

int main() {
    // 构建输入数据流，这里用字符串模拟输入
    std::string input = "A\nB\n#\n#\nC\n#\n#\n";
    std::istringstream iss(input);

    // 调用build函数构建二叉树
    TreeNode* root = build(iss);

    // 输出构建的二叉树，这里可以自定义遍历方式
    // 例如前序遍历、中序遍历、后序遍历等
    // 这里以简单方式输出根节点的值
    if (root != nullptr) {
        std::cout << "Root data: " << root->data << std::endl;
    } else {
        std::cout << "Root is null." << std::endl;
    }

    // 释放二叉树内存，这里需要自行实现释放内存的函数
    // 可以使用递归方式遍历树释放每个节点的内存
    // 在这里简化处理，不进行内存释放

    return 0;
}

2.按先序遍历的顺序复制二叉树

#include <iostream>
#include <string>
#include <stack>
#include <sstream>

class TreeNode {
public:
    char data;
    TreeNode* lchild;
    TreeNode* rchild;

    TreeNode(char data) : data(data), lchild(nullptr), rchild(nullptr) {}
};

TreeNode* build(std::istringstream& iss) {
    std::stack<TreeNode*> nodeStack;
    std::string line;
    TreeNode* root = nullptr;

    while (std::getline(iss, line)) {
        char ch = line[0];

        if (ch == '#') {
            if (nodeStack.empty()) {
                break;
            }
            nodeStack.pop();
        } else {
            TreeNode* newNode = new TreeNode(ch);
            if (nodeStack.empty()) {
                root = newNode;
            } else {
                TreeNode* parent = nodeStack.top();
                if (!parent->lchild) {
                    parent->lchild = newNode;
                } else {
                    parent->rchild = newNode;
                }
            }
            nodeStack.push(newNode);
        }
    }

    return root;
}

int main() {
    // 构建输入数据流，这里用字符串模拟输入
    std::string input = "A\nB\n#\n#\nC\n#\n#\n";
    std::istringstream iss(input);

    // 调用build函数构建二叉树
    TreeNode* root = build(iss);

    // 输出构建的二叉树，这里可以自定义遍历方式
    // 例如前序遍历、中序遍历、后序遍历等
    // 这里以简单方式输出根节点的值
    if (root != nullptr) {
        std::cout << "Root data: " << root->data << std::endl;
    } else {
        std::cout << "Root is null." << std::endl;
    }

    // 释放二叉树内存，这里需要自行实现释放内存的函数
    // 可以使用递归方式遍历树释放每个节点的内存
    // 在这里简化处理，不进行内存释放

    return 0;
}

3.按后序遍历的顺序计算二叉树深度

二叉树深度为左右子树深度中的最大值+1，代码在二叉树递归的层序遍历中含有。