1.二叉树 和 二叉搜索树（二叉查找树）的区别：
二叉树：每个节点的子节点不允许超过两个--可以0个、1个、至多2个；
二叉搜索树：1.每个节点的子节点不能超过两个，2.同时相对较小的值保存在左节点（left-child）,较大的值保存在右节点（right-child）
2.前序、中序和后序遍历的方法和顺序：
2.1前序遍历：
2.2中序遍历：
2.3后序遍历
先访问左子节点(left-child) -> 右子节点(right-child) -> 根节点(root)
3.实例分析
3.1 普通二叉树
前序遍历(PreOrder traversal): G->D->A->F->E->M->H->Z
中序遍历(InOrder traversal): A->D->G->E->F->H->M->Z(X-error!) A->D->E->F->G->H->M->Z(√ - right)
后序遍历(PostOrder traversal): A->E->F->H->Z->D->M->G(X-error!) A->E->F->D->H->Z->M->G(√ - right)
3.1.1 已知前序、中序遍历，求后序遍历(转点击打开链接)
例：
前序遍历: GDAFEMHZ
中序遍历: ADEFGHMZ
画树求法：
第一步，根据前序遍历的特点，我们知道根结点为G
第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。
第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。
第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。
第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
那么，根据后序的遍历规则，我们可以知道，后序遍历顺序为：AEFDHZMG
编程求法：（依据上面的思路，写递归程序）
#include<iostream>
#include<fstream>
#include<string>
using std::cout;
using std::endl;
struct TreeNode{
struct TreeNode* left;
struct TreeNode* right;
char elem;
};
void BinaryTreeFromOrderings(char* inorder, char * preorder, int length){
if (length == 0){
//cout << "Invalid length!" << endl;
return;
}
TreeNode* node = new TreeNode;
node->elem = *preorder;
int rootIndex = 0;
for (; rootIndex < length; rootIndex++){
if (inorder[rootIndex] == *preorder)
break;
}
//Left
BinaryTreeFromOrderings(inorder, preorder + 1, rootIndex);
//Right
BinaryTreeFromOrderings(inorder+rootIndex+1,preorder+rootIndex+1,length-(rootIndex+1));
cout << node->elem << "->"; //输出postOrder: A->E->F->D->H->Z->M->G-> ??WHY
return;
}
int main()
{
char * pre = "GDAFEMHZ";
char * in = "ADEFGHMZ" ;
BinaryTreeFromOrderings(in, pre, 8);
cout << endl;
return 0;
}
3.1.2 已知中序和后序遍历，求前序遍历
依然是上面的题，这次我们只给出中序和后序遍历：
中序遍历: ADEFGHMZ
后序遍历: AEFDHZMG
画树求法：
第一步，根据后序遍历的特点，我们知道后序遍历最后一个结点即为根结点，即根结点为G。
第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。
第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。
第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前后序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。
第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下：
1 确定根,确定左子树，确定右子树。
2 在左子树中递归。
3 在右子树中递归。
4 打印当前根。
这样，我们就可以画出二叉树的形状，如上图所示，这里就不再赘述。
那么，前序遍历: GDAFEMHZ
编程求法：（并且验证我们的结果是否正确）
#include<iostream>
#include<fstream>
#include<string>
using std::cout;
using std::endl;
struct TreeNode{
struct TreeNode* left;
struct TreeNode* right;
char elem;
};
TreeNode* BinaryTreeFromOrderings(char* inorder, char * postorder, int length){
if (length == 0){
//cout << "Invalid length!" << endl;
return NULL;
}
TreeNode* node = new TreeNode;
node->elem = *(postorder + length - 1);
cout << node->elem << "->"; //注意cout的位置！ Preorder : G->D->A->F->E->M->H->Z->
int rootIndex = 0;
for (; rootIndex < length; rootIndex++){
if (inorder[rootIndex] == *(postorder + length - 1))
break;
}
node->left = BinaryTreeFromOrderings(inorder, postorder,rootIndex);
node->right = BinaryTreeFromOrderings(inorder+rootIndex+1,postorder+rootIndex,length-(rootIndex+1));
return node;
}
int main()
{
char * post = "AEFDHZMG";
char * in = "ADEFGHMZ";
BinaryTreeFromOrderings(in, post, 8);
cout << endl;
return 0;
}
3.2 二叉搜索树的后序遍历
题目：输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。如果是返回true,否则返回false.
解析： 例如 输入数组 {5,7,6,9,11,10,8}，则返回true。解释在【分析】中；如果输入的数组是{7,4,6,5}，则返回false;
因为二叉搜索树中会有大小关系-----left_child->value < root->value < right_child->value 而这里（右子节点->4 > root->5 不符）
分析：
1. 后序遍历最后一个节点对应的值为根节点对应的值，即root->value = 8;
2. 比8小的是左子节点对应的值--{5,7,6}； 比8大的是右子节点对应的值--{9,11,10}；
3. 递归思想：在左子节点{5,7,6}中 root->value = 6; 因为5<6,所以5是左节点对应的值，7>6，所以7是右节点对应的值
在右子节点{9,11,10}中root->value = 10; 因为9<10,所以9是左节点对应的值，11>10，所以10是右节点对应的值
4.判断是否是最后一个节点，可得下图：
代码如下：
class Solution {
public:
bool IsSubtree(vector<int> sequence){
int n = 0, root = 0;
n = sequence.size();
if(n == 1 || n == 0) return true;
//else if (n == 0) return false; 子节点可以不存在！
root = sequence[n-1];
vector<int> leftTree; //依次保存递归使用的子树
vector<int> rightTree;
int i = 0 ;// 在如下两个for循环*同使用，目的是为了顺序遍历每个节点
for(;i < n-1; i++){
if(sequence[i] < root)
leftTree.push_back(sequence[i]);
else
break;
}
for(;i < n-1; i++){
if(sequence[i] > root)
rightTree.push_back(sequence[i]);
else
return false;
}
return IsSubtree(leftTree) && IsSubtree(rightTree);
}
bool VerifySquenceOfBST(vector<int> sequence) {
int n = 0;
n = sequence.size();
if( n == 0)
return false;
return IsSubtree(sequence);
}
};
使用先序、中序、后序遍历的方法对二叉树的依次访问：
转自基于C++类和指针实现二叉树
1、二叉树的定义
二叉树（Binary Tree）是一种特殊的树型结构，每个节点至多有两棵子树，且二叉树的子树有左右之分，次序不能颠倒。
由定义可知，二叉树中不存在度（结点拥有的子树数目）大于2的节点。二叉树形状如下下图所示：
2、二叉树的性质
（1）在二叉树中的第i层上至多有2^(i-1)个结点（i>=1)。备注:^表示此方
（2）深度为k的二叉树至多有2^k-1个节点（k>=1)。
（3）对任何一棵二叉树T，如果其终端结点数目为n0，度为2的节点数目为n2，则n0=n2+1。
满二叉树：深度为k且具有2^k-1个结点的二叉树。即满二叉树中的每一层上的结点数都是最大的结点数。
完全二叉树：深度为k具有n个结点的二叉树，当且仅当每一个结点与深度为k的满二叉树中的编号从1至n的结点一一对应。
可以得到一般结论：满二叉树和完全二叉树是两种特殊形态的二叉树，满二叉树肯定是完全二叉树，但完全二叉树不不一定是满二叉树。
举例如下图是所示：
（4）具有n个节点的完全二叉树的深度为log2n + 1。
3、二叉树的存储结构
可以采用顺序存储数组和链式存储二叉链表两种方法来存储二叉树。经常使用的二叉链表方法，因为其非常灵活，方便二叉树的操作。二叉树的二叉链表存储结构如下所示：
1 typedef struct binary_tree_node 2 { 3 int elem; 4 struct binary_tree_node *left; 5 struct binary_tree_node *right; 6 }binary_tree_node,*binary_tree;举例说明二叉链表存储过程，如下图所示：
从图中可以看出：在还有n个结点的二叉链表中有n+1个空链域。
4、遍历二叉树
遍历二叉树是按照指定的路径方式访问书中每个结点一次，且仅访问一次。由二叉树的定义，我们知道二叉数是由根结点、左子树和右子树三部分构成的。通常遍历二叉树是从左向右进行，因此可以得到如下最基本的三种遍历方法：
（1）先根遍历（先序遍历）：如果二叉树为空，进行空操作；否则，先访问根节点，然后先根遍历左子树，最后先根遍历右子树。采用递归形式实现代码如下：
1 void preorder_traverse_recursive(binary_tree root) 2 { 3 if(NULL != root) 4 { 5 printf("%d\t",root->elem); 6 preorder_traverse_recursive(root->left); 7 preorder_traverse_recursive(root->right); 8 } 9 }具体过程如下图所示：
（2）中根遍历（中序遍历）：如果二叉树为空，进行空操作；否则，先中根遍历左子树，然后访问根结点，最后中根遍历右子树。递归过程实现代码如下：
1 void inorder_traverse_recursive(binary_tree root) 2 { 3 if(NULL != root) 4 { 5 inorder_traverse_recursive(root->left); 6 printf("%d\t",root->elem); 7 inorder_traverse_recursive(root->right); 8 } 9 }具体过程如下图所示：
（3）后根遍历（后序遍历）：如果二叉树为空，进行空操作；否则，先后根遍历左子树，然后后根遍历右子树，最后访问根结点。递归实现代码如下：
1 void postorder_traverse_recursive(binary_tree root) 2 { 3 if(NULL != root) 4 { 5 postorder_traverse_recursive(root->left); 6 postorder_traverse_recursive(root->right); 7 printf("%d\t",root->elem); 8 } 9 }具体过程如下图所示：
用类和指针实现的二叉树：
