数据结构实验十四 二叉排序树

1. #include<iostream>
2. using namespace std;
3. #define ENDFLAG '#'
4. //char a[10]={'5','6','7','2','1','9','8','10','3','4','#'};//全局变量
5. typedef struct ElemType{ 
6.  char key;
7. }ElemType;
8. 
9. typedef struct BSTNode{
10.   ElemType data;  //结点数据域
11.   BSTNode *lchild,*rchild;  //左右孩子指针
12. }BSTNode,*BSTree;
13. 
14. 
15. //算法7.4　二叉排序树的递归查找
16. BSTree SearchBST(BSTree T,char key) {
17. //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素
18. //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针
19. if((!T)||key==T->data.key) return T;                    //查找结束
20.   else if(key<T->data.key)  return SearchBST(T->lchild,key);        //在左子树中继续查找
21. else return SearchBST(T->rchild,key);           //在右子树中继续查找
22. } // SearchBST
23. 
24. 
25. 
26. //算法7.5　二叉排序树的插入
27. void InsertBST(BSTree &T,ElemType e ) {
28. //当二叉排序树T中不存在关键字等于e.key的数据元素时，则插入该元素
29. if(!T) {                        //找到插入位置，递归结束
30.      BSTree S = new BSTNode;                //生成新结点*S
31.          S->data = e;                     //新结点*S的数据域置为e   
32.          S->lchild = S->rchild = NULL;  //新结点*S作为叶子结点
33.          T =S;                    //把新结点*S链接到已找到的插入位置
34.   }
35. else if (e.key< T->data.key) 
36.       InsertBST(T->lchild, e );     //将*S插入左子树
37. else if (e.key> T->data.key) 
38.       InsertBST(T->rchild, e);      //将*S插入右子树
39. }// InsertBST
40. 
41. 
42. 
43. //算法7.6　二叉排序树的创建
44. void CreateBST(BSTree &T ) {
45. //依次读入一个关键字为key的结点，将此结点插入二叉排序树T中
46.   T=NULL;
47.   ElemType e;
48.   cin>>e.key;        //???
49.   while(e.key!=ENDFLAG){    //ENDFLAG为自定义常量，作为输入结束标志
50.     InsertBST(T, e);            //将此结点插入二叉排序树T中
51.     cin>>e.key;     //???
52.   }//while            
53. }//CreatBST
54. 
55. void DeleteBST(BSTree &T,char key) {
56. //从二叉排序树T中删除关键字等于key的结点
57.   BSTree p=T;BSTree f=NULL;                           //初始化
58.   BSTree q;
59.   BSTree s;
60. /*------------下面的while循环从根开始查找关键字等于key的结点*p-------------*/
61.   while(p){                  
62. if (p->data.key == key) break;            //找到关键字等于key的结点*p，结束循环
63.    f=p;                                     //*f为*p的双亲结点
64. if (p->data.key> key)  p=p->lchild;       //在*p的左子树中继续查找
65. else p=p->rchild;                         //在*p的右子树中继续查找
66.   }//while
67. if(!p) return;                            //找不到被删结点则返回
68. /*―考虑三种情况实现p所指子树内部的处理：*p左右子树均不空、无右子树、无左子树―*/
69. if ((p->lchild)&& (p->rchild)) {        //被删结点*p左右子树均不空
70.      q = p;
71.    s = p->lchild;
72.      while (s->rchild)                      //在*p的左子树中继续查找其前驱结点，即最右下结点
73.        {q = s; s = s->rchild;}              //向右到尽头
74.      p->data = s->data;                     //s指向被删结点的"前驱"
75. if(q!=p){
76.      q->rchild = s->lchild;       //重接*q的右子树
77.    }
78. else q->lchild = s->lchild;           //重接*q的左子树
79. delete s;
80.   }//if
81. else{
82.   if(!p->rchild) {                  //被删结点*p无右子树，只需重接其左子树
83.       q = p; p = p->lchild; 
84.     }//else if
85.   else if(!p->lchild) {                   //被删结点*p无左子树，只需重接其右子树
86.      q = p; p = p->rchild;
87.     }//else if
88.   /*――――――――――将p所指的子树挂接到其双亲结点*f相应的位置――――――――*/
89.     if(!f) T=p;                             //被删结点为根结点
90.     else if (q==f->lchild) f->lchild = p;     //挂接到*f的左子树位置
91.     else f->rchild = p;                     //挂接到*f的右子树位置
92.     delete q;
93.   }
94. }//DeleteBST
95. 
96. //算法 7.7　二叉排序树的删除
97. 
98. //中序遍历
99. void InOrderTraverse(BSTree T)
100. { 
101.  if(T)
102.  {
103.    InOrderTraverse(T->lchild);
104.    cout<<T->data.key;
105.    InOrderTraverse(T->rchild);
106.    }    
107. }
108. 
109. int  main()
110. {
111.  BSTree T;
112.  cout<<"请输入若干字符，用回车区分，以#结束输入"<<endl;
113.  CreateBST(T);
114.  cout<<"当前有序二叉树中序遍历结果为"<<endl;
115.  InOrderTraverse(T);
116.  char key;//待查找或待删除内容
117.  cout<<"请输入待查找字符"<<endl;
118.  cin>>key;
119.  BSTree result=SearchBST(T,key);
120.  if(result)
121.  {cout<<"找到字符"<<key<<endl;}
122.  else
123.  {cout<<"未找到"<<key<<endl;}
124.  cout<<"请输入待删除的字符"<<endl;
125.  cin>>key;
126.  DeleteBST(T,key);
127.  cout<<"当前有序二叉树中序遍历结果为"<<endl;
128.  InOrderTraverse(T);
129.  return 0; 
130. }