C++二叉树
什么是二叉树？
二叉树（Binary Tree）是树的一种特殊形式。二叉，顾名思义，这种树的每个结点最多有 2 个孩子结点。注意，这里是最多有 2 个，也可能只有 1 个，或者没有孩子结点。
满二叉树
**一个二叉树的所有非叶子结点都存在左右孩子，并且所有叶子结点都在同一层级上，那么这个树就是满二叉树。**
完全二叉树
对于深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全二叉树。
**前 h-1 层是满的，最后一层不满，但是最后一层从左到右是连续的。**
二叉树的五条性质
性质1
性质2
性质3
性质4
性质5
根结点位置为 1，对于第 x 位置的结点
左孩子：第 2 x位置
右孩子：第 2x+1 位置
双亲：第 x/2 位置
二叉树存储结构
二叉树数组存储
**如果对应位置没有结点，那么在存储时需要预留出这个位置。为了读取数据时可以还原出二叉树结构。**
二叉树链式存储
二叉树遍历
前序遍历
规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树（根->左子树->右子树）。
中序遍历
规则是若树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树（左子树->根->右子树）。
后序遍历
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点（左子树->右子树->根）。
层序遍历
借助队列实现层次遍历
- 访问根结点，根结点入队；
- 结点出队，访问该结点的孩子结点，并将该结点的孩子结点入队；
- 重复步骤2，直至队列为空。
随堂练习-选择题
例题1
对表达式 a+(b-c)*d 的前缀表达式为（ ），其中 +、-、* 是运算符。
A. *+a-bcd
B. +a*-bcd
C. abc-d*+
D. abc-+d
答案：B
解析：按照运算优先级建立如下表达式树，然后进行前序遍历。
例题2
**给定先序遍历和中序遍历，求后序遍历。****先序遍历 ABCDEF****中序遍历 CBDAEF**
解析：
首先在前序中找到根：A；
再中序中用根分出左右两部分：CBD 和 EF；
再先序中找到这两部分的根 B 和 E；
一直如此往复即可。
二叉树形态和数的计数问题
二叉树五种基本形态：
3 个结点二叉树五种形态：
那么 n 个结点的不同形态二叉树有多少棵？
一般情况下，一棵具有 n（n>1）个结点的二叉树可以看做是一个根节点、一颗具有 i 个结点的左子树和一颗具有 n-i-1 个结点的右子树组成，其中 0≤0≤n-1。
A[0]=1
A[1]=1
课堂例题
二叉树先序、中序求后序
题目解析：
1.通过先序遍历找到根节点；
2.在中序遍历中找到根节点位置，并划分左、右子树，且可以得到左、右子树长度；
3.在先序遍历序列中根据左、右子树长度找到对应左、右子树序列；
4.分别对得到的左、右子树继续做先序遍历划分，直至子树为空返回。
参考程序：
#include <iostream>
#include <string>
using namespace std;
void postOrder(string pre_string, string in_string){
int len = pre_string.size();
if(!len) return;
char root = pre_string[0];
int in_root_idx = in_string.find(root);
string pre_left_tree = pre_string.substr(1, in_root_idx);
string in_left_tree = in_string.substr(0, in_root_idx);
postOrder(pre_left_tree, in_left_tree);
string pre_right_tree = pre_string.substr(in_root_idx + 1);
string in_right_tree = in_string.substr(in_root_idx + 1);
postOrder(pre_right_tree, in_right_tree);
cout << root;
}
int main() {
string pre_string, in_string;
cin >> pre_string >> in_string;
postOrder(pre_string, in_string);
return 0;
}