今晚上撸了二叉树的的代码，要哭。指针乱☞。。

就当复习一下二叉树了。

恩。

二叉树有以下性质：

1.在二叉树第i层最多有2^（i-1）个nodes；

2.深度k的二叉树至多有2^k-1个nodes；

3.任意一颗二叉树，如果叶节点有n个，度为2的节点有m个，那么满足等式：n=m+1；

4.具有n个节点的完全二叉树的深度为ceil（log2 n）；

5.对于一颗二叉树设节点为i：

那么：

如果i>1,则它的父节点为i/2；

如果2*i>n，则无左孩子。否则左孩子为2*i；

如果2*i+1>n，则无右孩子。否则右孩子为2*i+1；

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;typedef struct node;typedef node *tree;struct node{    char data;    tree lchild,rchild;};tree bt;string s;int i;void buildtree(tree &bt)//建树{    if(s[++i]!='$')    {        bt=new node;        bt->data=s[i];        buildtree(bt->lchild);        buildtree(bt->rchild);    }    else bt=NULL;}void xianpreorder(tree &bt)//先序遍历{    if(bt)    {        cout<
          
           data; xianpreorder(bt->lchild); xianpreorder(bt->rchild); }}void zhongpreorder(tree &bt)//中序遍历{ if(bt) { cout<
           
            data; zhongpreorder(bt->lchild); zhongpreorder(bt->rchild); }}void houpreorder(tree &bt)//后序遍历{ if(bt) { cout<
            
             data; houpreorder(bt->lchild); houpreorder(bt->rchild); }}void deletetree(tree &bt)//删除树{ deletetree(bt->lchild); deletetree(bt->rchild); delete bt;}void inserttree(tree &bt,int n)//插入节点{ if(bt) { if(n
             
              data) inserttree(bt->lchild,n); else if(n>bt->data) inserttree(bt->rchild,n); } else { bt=new node; bt->data=n; bt->lchild=bt->rchild=NULL; }}tree findtree(tree bt,int n)//查找节点{ if(bt) { if(n
              
               data) findtree(bt->lchild,n); else if(n>bt->data) findtree(bt->rchild,n); else return bt; } else return NULL;}int main(){ cin>>s; i=-1; buildtree(bt); xianpreorder(bt); zhongpreorder(bt); houpreorder(bt); int n; cin>>n; inserttree(bt,n); findtree(bt,n); deletetree(bt); return 0;}