二叉树的其他重要操作

 1 //建树
 2 void pre(tree &bt)     //先序次序输入
 3 {
 4     char ch;
 5     ch=getchar();    //单链表存储结构，bt为指向根结点的指针，$为空树
 6     if(ch!='$')
 7     {
 8         bt=new node;   //建立根节点
 9         bt->data=ch;
10         pre(bt->l);    //建立左子树
11         pre(bt->r);    //建立右子树
12     }
13     else bt=NULL;
14 }

1 void dis(tree &bt)
2 {
3     if(bt)
4     {
5         dis(bt->l);    //删除左子树
6         dis(bt->r);    //删除右子树
7         delete bt;     //释放父节点
8     }
9 }

 1 //插入一个节点到二叉树中
 2 void insert(tree &bt,int n)
 3 {
 4     if(bt)
 5     {
 6         if(n<bt->data)
 7           insert(bt->l,n);
 8         else if(n>bt->data)
 9                insert(bt->r,n);
10     }
11     else
12     {            //新开一个空间 
13         bt=new node;
14         bt->data=n;
15         bt->l=bt->r=NULL;
16     }
17 } 

 1 //在排序二叉树中查找一个数，找到返回该结点，否则返回NULL
 2 tree find(tree bt,int n)
 3 {
 4     if(bt)
 5     {
 6         if(n<bt->data)
 7           find(bt->l,n);
 8         else if(n>bt->data)
 9                find(bt->r,n);
10              else
11                return bt;
12     }
13     else
14       return NULL;
15 }