4-12 二叉搜索树的操作集 (30分)
本题要求实现给定二叉搜索树的5种常用操作。
函数接口定义:
BinTree Insert( BinTree BST, ElementType X );
BinTree Delete( BinTree BST, ElementType X );
Position Find( BinTree BST, ElementType X );
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
其中BinTree
结构定义如下:
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
- 函数
Insert
将X
插入二叉搜索树BST
并返回结果树的根结点指针; - 函数
Delete
将X
从二叉搜索树BST
中删除,并返回结果树的根结点指针;如果X
不在树中,则打印一行Not Found
并返回原树的根结点指针; - 函数
Find
在二叉搜索树BST
中找到X
,返回该结点的指针;如果找不到则返回空指针; - 函数
FindMin
返回二叉搜索树BST
中最小元结点的指针; - 函数
FindMax
返回二叉搜索树BST
中最大元结点的指针;
输入样例:
10
5 8 6 2 4 1 0 10 9 7
5
6 3 10 0 5
5
5 7 0 10 3
输出样例:
Preorder: 5 2 1 0 4 8 6 7 10 9
6 is found
3 is not found
10 is found
10 is the largest key
0 is found
0 is the smallest key
5 is found
Not Found
Inorder: 1 2 4 6 8 9
二叉查找树重要性质:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
现有,如下一棵二叉查找树。
(图1)
现在,若要删除图1中,任意节点,需要考虑如下三种情况:
(1)需要删除的节点下并没有其他子节点。
(2)需要删除的节点下有一个子节点(左或右)。
(3)需要删除的节点下有两个子节点(既左右节点都存在)。
第一种情况直接删除即可,下面,直接讨论第二种情况。
若我们要删除的是3号节点,由图1可以看到,它下面还有一个4号子节点。由下图2,可以看出,对于这种办法,我们只需要想办法,让5号节点的左子树的指针指向4就可以了。
(图2)
第三种情况,既我们要删除的节点下,有2个子节点。如图3,我们先在需要删除的节点的右子树中,找到一个最小的值(因为右子树中的节点的值一定大于根节点)。然后,用找到的最小的值与需要删除的节点的值替换。然后,再将最小值的原节点进行删除(图4)。
(图3)
1 #include <iostream> 2 #include <stdio.h> 3 #include <stdlib.h> 4 typedef int ElementType; 5 typedef struct TNode *Position; 6 typedef Position BinTree; 7 struct TNode{ 8 ElementType Data; 9 BinTree Left; 10 BinTree Right; 11 }; 12 13 void PreorderTraversal( BinTree BT ); /* 先序遍历,由裁判实现,细节不表 */ 14 void InorderTraversal( BinTree BT ); /* 中序遍历,由裁判实现,细节不表 */ 15 BinTree Insert( BinTree BST, ElementType X ); 16 BinTree Delete( BinTree BST, ElementType X ); 17 Position Find( BinTree BST, ElementType X ); 18 Position FindMin( BinTree BST ); 19 Position FindMax( BinTree BST ); 20 int main() 21 { 22 BinTree BST, MinP, MaxP, Tmp; 23 ElementType X; 24 int N, i; 25 BST = NULL; 26 scanf("%d", &N); 27 for ( i=0; i<N; i++ ) { 28 scanf("%d", &X); 29 BST = Insert(BST, X); 30 } 31 printf("Preorder:"); PreorderTraversal(BST); printf(" "); 32 MinP = FindMin(BST); 33 MaxP = FindMax(BST); 34 scanf("%d", &N); 35 for( i=0; i<N; i++ ) { 36 scanf("%d", &X); 37 Tmp = Find(BST, X); 38 if (Tmp == NULL) printf("%d is not found ", X); 39 else { 40 printf("%d is found ", Tmp->Data); 41 if (Tmp==MinP) printf("%d is the smallest key ", Tmp->Data); 42 if (Tmp==MaxP) printf("%d is the largest key ", Tmp->Data); 43 } 44 } 45 scanf("%d", &N); 46 for( i=0; i<N; i++ ) { 47 scanf("%d", &X); 48 BST = Delete(BST, X); 49 } 50 printf("Inorder:"); 51 InorderTraversal(BST); 52 printf(" "); 53 return 0; 54 } 55 /* 你的代码将被嵌在这里 */ 56 void PreorderTraversal( BinTree BT ) 57 { 58 if(BT==NULL) return; 59 else{ 60 printf(" %c",BT->Data); 61 PreorderTraversal(BT->Left); 62 PreorderTraversal(BT->Right); 63 } 64 } 65 void InorderTraversal( BinTree BT ) 66 { 67 if(BT==NULL) return; 68 else{ 69 InorderTraversal(BT->Left); 70 printf(" %c",BT->Data); 71 InorderTraversal(BT->Right); 72 } 73 } 74 BinTree Insert( BinTree BST, ElementType X ) 75 { 76 if(!BST)//如果BST为空的话,返回只有一个节点的树 77 { 78 BST=(BinTree)malloc(sizeof(struct TNode)); 79 BST->Data=X; 80 BST->Left=NULL; 81 BST->Right=NULL; 82 } 83 else//如果BST不是为空的话 84 {//开始寻找要插入的位置 85 if(X<BST->Data) 86 BST->Left=Insert(BST->Left,X); 87 else if(X>BST ->Data) 88 BST->Right=Insert(BST->Right,X); 89 } 90 return BST; 91 } 92 BinTree Delete( BinTree BST, ElementType X ) 93 { 94 BinTree Tmp; 95 if(!BST) printf("Not Found "); 96 else{ 97 if(X<BST->Data) 98 BST->Left=Delete(BST->Left,X); 99 else if(X>BST->Data) 100 { 101 BST->Right=Delete(BST->Right,X); 102 } 103 else//考虑如果找到这个位置,并且有左节点或者右节点或者没有节点三种情况 104 { 105 if(BST->Left && BST->Right) { 106 Tmp=FindMin(BST->Right); /* 在右子树中找到最小结点填充删除结点 */ 107 BST->Data = Tmp ->Data; 108 BST->Right=Delete(BST->Right,BST->Data);/* 递归删除要删除结点的右子树中最小元素 */ 109 } 110 else 111 { /* 被删除结点有一个或没有子结点*/ 112 Tmp = BST; 113 if(!BST->Left) BST = BST->Right; /*有右孩子或者没孩子*/ 114 else if(!BST->Right) BST = BST->Left;/*有左孩子,一定要加else,不然BST可能是NULL,会段错误*/ 115 free(Tmp); /*如无左右孩子直接删除*/ 116 } 117 } 118 } 119 return BST; 120 } 121 Position Find( BinTree BST, ElementType X ) 122 { 123 if(!BST) return NULL; 124 if(BST->Data==X) return BST; 125 else if(X<BST->Data) { 126 return Find(BST->Left,X); 127 } 128 else if(X>BST->Data) 129 { 130 return Find(BST->Right,X); 131 } 132 return BST; 133 } 134 Position FindMin( BinTree BST ) 135 { 136 if(BST!=NULL) 137 { 138 while(BST->Left) 139 BST=BST->Left; 140 } 141 return BST; 142 } 143 Position FindMax( BinTree BST ) 144 { 145 if(BST!=NULL) 146 { 147 while(BST->Right) 148 BST=BST->Right; 149 } 150 return BST; 151 }