今天总结一下二叉树，要考离散了，求不挂！二叉树最重要的就是 建立、4种遍历方式，简单应用，如何判断两颗二叉树是否相似
二叉树分为 ：1、完全二叉树 2、满二叉树
结构性质：
1）.满二叉树 高度为h ，节点数则为 2^h - 1，且叶子节点全在最下层，且叶子节点数为2^（n-1）个｛n代表二叉树层数，也叫深度｝
2）.n个节点的 完全二叉树 深度为 int（log2n）（以2为底n的对数）+ 1；
3）.非空二叉树 叶子节点个数==双分支节点数+1
4）.非空二叉树 某节点编号 n 若有左孩子，则左孩子节点 2*n，若有右孩子，则其节点编号为2*n+1
5）.知道其中两种遍历方式，就可知第三种遍历方式。
6）.判断俩颗二叉树是否相同，只需判断他们任意俩种相对应的遍历顺序即可
建树：
已知输入的字符为某颗二叉树的先序序列，如abcXXdeXgXXfXXX (其中X表示空节点),建立二叉树
struct node *make()
{
char c;
node *st;
c = getchar();
if(c=='X')
st = NULL;
else
{
st = (struct node *)malloc(sizeof(struct node));
st ->data = c;//已知为先序遍历，先填充根节点
st ->left = make();//递归形式填充左分支
st->right = make();//递归形式填充左分支
}
return st;
}
vcq9o7o8L3N0cm9uZz48L3A+CjxwPjxzdHJvbmc+senA+re9yr263NbY0qqjrMrXz8jSqtaqtcDI57rOsenA+qOsssXE3LTys/a0+sLro6zP1tTaxNS6o8DvxKPE4tK7sek8L3N0cm9uZz48L3A+CjxzdHJvbmc+0ruhos/I0PKx6cD6PC9zdHJvbmc+PGJyPgogICAgPGJyPgo8cD4gICAgMS7PyLfDzsq4+b3ateM8L3A+CiAgICAyLtTZt8POytfzt9bWpzxicj4KCjxwPiAgICAzLtTZt8POytPSt9bWpzwvcD4KPHA+yc/K9s28xqy2/rLmyve1xM/I0PKx6cD6o7pBQkRHQ0VGPC9wPgo8YnI+CjxzdHJvbmc+tv6hotbQ0PKx6cD6PC9zdHJvbmc+PGJyPgogIDxicj4KICAgIDEuz8i3w87K1/O31tanPGJyPgogICAgMi7U2rfDzsq4+b3ateM8YnI+CiAgICAzLtTZt8POytPSt9bWpzxicj4Kyc/K9s28xqy2/rLmyve1xNbQ0PKx6cD6o7pER0JBRUNGPGJyPgo8YnI+CjxzdHJvbmc+yP2horrz0Pix6cD6PC9zdHJvbmc+PGJyPgo8YnI+CiAgICAxLs/It8POytfzt9bWpzxicj4KICAgIDIu1Nm3w87K09K31tanPGJyPgoKPHA+ICAgIDMu1Nm3w87KuPm92rXjPC9wPgo8cD7Jz8r2zbzGrLb+subK97XEuvPQ8rHpwPqjukdEQkVGQ0E8YnI+CjwvcD4KPHA+PC9wPgo8cD48c3Ryb25nPsvEoaKy47TOsenA+jwvc3Ryb25nPjwvcD4KPHA+vs3Kx7TTw7/Su7LjsLTV1bTT1/PWwdPStcTLs9Dyo6zSu7TOsenA+rjDsuPL+dPQtcS92rXjPC9wPgo8cD6yydPDu7fQzrbTwdC1xLe9t6ijrL340NC3w87KPC9wPgq3w87K0rbX073ateMKPHA+PGJyPgo8L3A+CjxwPsnPyva13bnpyr7S4s28yOfPwqO6PC9wPgo8cD48YnI+CjwvcD4KPHA+PGltZyBzcmM9"http://www.cppentry.com/upload_files/article/49/1_iahxb__.jpg" alt="\">
二叉树的深度
从当前节点的左右分支开始判断，谁大自增1
判断?颗二叉树是否相似
1.所有节点的对应左右孩子都相同
2.如过 有任意俩种遍历方式相同，那么俩颗树就相同
代码模版：
#include
#include
#include
#include
#include
const int N = 1010; using namespace std; char a[100]; struct node{ char data; node *left; node *right; }; struct node *make() { char c; node *st; c = getchar(); if(c=='X') st = NULL; else { st = (struct node *)malloc(sizeof(struct node)); st ->data = c;//已知为先序遍历，先填充根节点 st ->left = make();//递归形式填充左分支 st->right = make();//递归形式填充左分支 } return st; } void First_Order(struct node *t )//先序遍历的递归形式 { if(t==NULL) return ; printf("%c -> ",t->data); First_Order(t->left); First_Order(t->right); } void First_Order_1(struct node *t)//先序遍历非递归形式 { struct node *stk[N],*p; int top = -1; if(t!=NULL) { top++; stk[top] = t; //根节点进栈 while(top>-1) { p = stk[top];//出栈并访问该节点 top--; printf("%c -> ",p->data); if(p->right!=NULL) //右孩子进栈 { top++; stk[top] = p->right; } if(p->left!=NULL)//左孩子进栈 { top++; stk[top] = p->left; } } } } void Mid_Order(struct node *t)//中序遍历递归形式 { if(t==NULL) return ; Mid_Order(t->left); printf("%c -> ",t->data); Mid_Order(t->right); } void Mid_Order_1(struct node *t)//先序遍历非递归形式 { struct node *stk[N],*p; int top = -1; if(t!=NULL) { p = t; while(top>-1 ||p!=NULL )// 遍历左分支 { while(p!=NULL) // 将当前t节点的左分支，全部压入栈 { top++; stk[top] = p; p = p->left; } //while结束后，栈顶元素可能没有左分支节点或者左分支节点已经访问完毕 if(top>-1) { p = stk[top];//出栈 ，并打印 top--; printf("%c -> ",p->data); p = p->righ