这篇博客主要针对代码实现，有关树和二叉树的基本概念书上讲的贼清楚，我觉得我再讲一遍也不会讲的比书上好了，所以大家如果基本概念有问题，直接看书吧 ^ ç ^
二叉树的存储结构有顺序存储结构和链式存储结构两种，其中顺序存储结构的操作相对简单，但在二叉树较空的情况下空间利用率很低，所以在实际应用中，链式存储结构的应用更广泛。
二叉树的链式存储结构中，每个节点都包含如下成分：
struct BTNode{ //"二叉树点" ElemType data; //用define把char定义为ElemType BTNode *lc,*rc; //lc是"left child"左孩子，rc是"right child"右孩子 };用data存储数据，lc和rc分别指向左、右节点，相当于每个节点都有两个指针域的链表
在下面的代码中，部分代码用到STL中的栈stack和队列queue，头文件分别为<stack>和<queue>。STL中的栈和队列采用类的成员函数的形式调用，这很方便地提供了一种可用的栈和队列的结构。
对栈和队列还不太熟悉的可以看一下之前的文章：
数据结构与算法——栈
数据结构与算法——队列
里面提到了栈和队列的基本思想，以及STL库的简单用法。
二叉树有一种表示法为括号表示法，本算法的功能是读取一段括号表示法的二叉树，把它转化为链式存储结构的二叉树。
要成功设计本算法，就要先弄懂什么是括号表示法
括号表示法：将树的根结点写在括号的左边，除根结点外的其余节点写在括号中，并用逗号分隔
在二叉树中，除叶子结点外，每个节点都有两个子结点——左孩子和右孩子，所以“括号”的形式被固定下来了：父结点(左孩子,右孩子)，比如：
A(B,C)是指这样的一个二叉树：
A(B, )则是这样的：
我们推广“左孩子”和“右孩子”的定义——不光是结点，我们把子树也看作孩子，那么:
对于A(B,C(D,E))，A的左孩子是B，右孩子是一颗子树C(D,E)，这棵子树是这样的：
把整个子树作为“右孩子”，接到根结点上，得到了整体的二叉树，它应该是这样的：
所以，如果我们有一段复杂一点的括号表示：
A(B(D,E(G, ) ),C( ,F) )
ps. 实际表达式中是不带空格的，我加上空格是为了方便大家看
那么，它应该是长这个样子的：
回顾上面的定义，结合这个复杂一点的例子，我们不难发现以下规律：
从头到尾扫描字符串，每当读取到：
左括号 (的时候，代表接下来的元素应该是个孩子，而且是左孩子逗号 ,的时候，代表左孩子录入完了，该录入右孩子了，所以接下来应该出现一个右孩子右括号 )的时候，代表右孩子也录入完了，这个结点一共就俩孩子，也就是说这个结点的孩子全都录入完了，那么接着看下一个结点字符 的时候，根据之前读取到的是左括号还是逗号，决定这个元素当左儿子还是右儿子接下来，我们用代码把上面的逻辑翻译一遍：
如果不懂STL的栈，不要抗拒它，用我们学的同名函数来理解它的功能，比如入栈都是push，出栈都是pop，栈顶都是top
void CreateBTree(BTNode *&bt,char *str){ stack<BTNode*> st; //STL的栈，类型为BTNode的指针 bt=NULL; //根结点初始化为空 int k; //用k记录左右儿子，1为左，2为右 BTNode *p=NULL; //用p存储读取到的字符 int len=strlen(str); //字符串str的长度为len for(int i=0;i<len;i++){ if(str[i]=='('){ k=1; //k计为左儿子 st.push(p); //入栈 continue; } else if(str[i]==')'){ st.pop(); //出栈 continue; //继续往后看 } else if(str[i]==','){ k=2; //k计为右儿子 continue; } else{ p=new BTNode(); //为p申请空间 p->data=str[i]; //赋值 p->lc=p->rc=NULL; if(bt==NULL) //如果bt为空，代表p为最开始的根结点 bt=p; else if(k==1) //之前读取到左括号，说明p是左孩子 st.top()->lc=p; else if(k==2) //之前读取到逗号，说明p是右孩子 st.top()->rc=p; } } }你可能有个疑问：
如果是A(,B)，那么读入(后，下一个字符是右孩子，不是左孩子呀
在上面的代码中，往二叉树插入元素的操作不是跟判断操作同步的，所以在找到(以后，我们进行的操作不是立马把p设为左孩子，而是继续扫描字符串，这样的话，紧接着我们又扫描到了,，这时候k又变成了2，所以最后p还是被安排为右儿子。
销毁二叉树的核心思想是，递归地找到二叉树的每个节点，然后分别释放它们的空间。
递归过程很像：
先让某个节点把它的俩儿子都叫来，再把它嫩死，再让俩儿子把他们俩的孩子（一共四个孙子）叫来，来了以后再把俩儿子嫩死······
需要注意的是，要在某个节点彻底失去利用价值后再释放它，也就是说释放语句应该放在递归调用语句的后面，否则，释放后无法通过该结点找到它后面的节点。就像上面的例子中，如果儿子还没来，就把老子嫩死了，那就再也找不到儿子在哪了，儿子就失联了。
void DestoryBTree(BTNode *&bt){ if(bt!=NULL){ //bt只要不是NULL，就把它的孩子叫来 DestoryBTree(bt->lc); //让它叫左孩子 DestoryBTree(bt->rc); //让它叫右孩子 delete bt; //嫩死它 } }我们约定每个节点都有一个左子树，有一个右子树，它俩的深度分别为lch和rch，那么该结点的深度h满足
h=max(lch,rch)+1比如在下面的二叉树中，求从节点B开始的树的深度：
由图：
左子树的深度lch=1——D右子树的深度rch=2——E->G所以从B开始计算的话，深度应该为2+1=3，也就是B->E->G
由此看来，我们只要从根结点开始，递归地找它的左右子树，按照上面的规则，就可以得到总的深度。
int BTHeight(BTNode *bt){ int lch, rch; //左子树深度lch和右子树深度rch if(bt==NULL) return 0; //如果是空的，就说明没有长度，返回0 else{ lch=BTHeight(bt->lc); //左子树的深度 rch=BTHeight(bt->rc); //右子树的深度 if(lch>rch)return lch+1; else return rch+1; } }与求深度的思想类似，对于每个节点，它的左子树有num1个节点，右子树有num2个节点，那么从它开始的结点个数sum满足
sum=num1+num2+1;利用上面的关系，递归地访问每个节点，就可以得到总的结点数
int NodeCount(BTNode *bt){ int num1,num2; if(bt==NULL) return 0; else{ num1=NodeCount(bt->lc); //左子树的结点个数 num2=NodeCount(bt->rc); //右子树的结点个数 return num1+num2+1; } }与求结点个数一样，对于每个节点，它的左子树有num1个叶子节点，右子树有num2个叶子节点，它拥有sum个叶子节点，满足
sum=num1+num2;利用上面的关系，递归地访问每个节点，就可以得到总的结点数
int LeafCount(BTNode *bt){ int num1,num2; if(bt==NULL) return 0; else if(bt->lc==NULL&&bt->rc==NULL) //如果当前结点为叶子结点，说明找到了一个叶子结点，返回1 return 1; else{ num1=LeafCount(bt->lc); //左子树的叶子结点 num2=LeafCount(bt->rc); //右子树的叶子结点 return num1+num2; } }采用上面“用字符串建立二叉树”的逆向思维。
由于二叉树的括号表达式格式被固定为父结点(左孩子,右孩子)，所以我们直接按照固定的格式输出。
输出父节点判断它是不是有孩子，如果没有就算了；如果有，那么不管有几个，我们都要先输出一个(由于左孩子不仅可能是结点，还可能是个子树，所以要递归地调用输出函数判断有没有右孩子，如果有，就需要输出一个,与左孩子一样，递归地调用输出函数，输出右孩子输出) void DispBTree(BTNode *bt){ if(bt!=NULL){ cout<<bt->data; if(bt->lc!=NULL|| bt->rc != NULL) { cout<<'('; DispBTree(bt->lc); if(bt->rc != NULL) cout<<','; DispBTree(bt->rc); cout<<')'; } } }二叉树的每一层都有一个宽度，树的宽度就是这些宽度中的最大宽度。我们如果能用一个数组记录每一层的宽度，最后再查找数组中的最大值，这个最大值就是树的宽度。
int Count[10010]; //用Count数组记录每一层的宽度，下标为层数，根结点是第0层 void WidConut(BTNode *bt, int dep){ if(bt==NULL) return ; Count[dep]++;//记录当前层结点数+1 dep++; //访问孩子结点时，层数+1 WidConut(bt->lc,dep); WidConut(bt->rc,dep); }现在我们有了一个数组Count，在主函数中只要找到它的最大值，就可以得到整棵树的宽度：
int wid=0; for(int i=0;Count[i]!=0;i++) wid=max(wid, Count[i]);遍历主要分为：
先序遍历中序遍历后序遍历层次遍历可以直观地看出前三种之间的关系比较密切！没错！前三种的代码基本一样，只是执行顺序不同，其中：
先序遍历
操作递归访问左孩子递归访问右孩子中序遍历
递归访问左孩子操作递归访问右孩子后序遍历
递归访问左孩子递归访问右孩子操作我们以输出代替上面的“操作”，给出如下的遍历方案：
层次遍历与其他三种不同，其他三种人比较难理解，所以计算机理解起来比较容易，但最后一种人一看就懂，这就说明计算机理解起来会有点费劲。
层次遍历是从根结点出发，按照从上到下、从左到右的次序依次访问所有结点
人来理解这东西，就是把二叉树画出来，辈分一样的结点画在同一行，然后从上到下、从左到右遍历。
但问题是，计算机它不会画图，所以你就要想一个别的法子
void LevelOrder(BTNode *bt){ queue<BTNode*> q; //STL中的队列 q.push(bt); //根结点入队 while (!q.empty()){ //当队伍非空的时候 BTNode *p=q.front(); //取队首 q.pop(); //队首元素出栈 cout<<p->data<<" "; if(p->lc!=NULL) //如果有左孩子 q.push(p->lc); //左孩子入队 if(p->rc!=NULL) //如果有右孩子 q.push(p->rc); //右孩子入队 } }可能有点抽象，怎么就跟队列扯上关系了？？
我们举个例子
对于图中这个二叉树：
A入队
p=A，操作p相当于操作A，A出队，B入队，C入队，队列如图
p=B，操作p相当于操作B，B出队，D入队，E入队，队列如图
p=C，操作p相当于操作C，C出队，F入队，队列如图
p=D，操作p相当于操作D，D出队，没孩子，队列如图
p=E，操作p相当于操作E，E出队，G入队，队列如图
p依次为F``G，依次对二者进行操作，二者依次出队，队空，循环结束
至此，我们依次操作了A、B、C、D、E、F、G，也就是按照从上到下、从左到右的顺序遍历了树
