二叉树操作
二叉树操作
实验目的
实现如下二叉树操作，Input：1-n的数组
(1)通过插入操作建立二叉树
(2)实现查找、最大/小关键字查询
(3)从1到n的依次删除
实验原理
二叉搜索树上的基本操作所花费的时间与这棵树的高度成正比。二叉搜索树可以使用一个链表数据结构来表示，其中每个结点都是一个对象。每个结点包含属性key，left，right，p，它们分别指向结点的关键字，左孩子，右孩子和双亲。如果某个孩子结点和父亲结点不存在，则相应属性值为NIL。
二叉搜索树中关键字满足二叉搜索树性质：设x是二叉搜索树中的一个结点，如果y是x左子树中的一个结点，那么y.key <= x.key；如果y是x右子树中的一个结点，那么y.key >= x.key。
实验过程
（一）插入法建立二叉树
要将一个新值v插入到一棵二叉搜索数T中，需要调用过程TREE-INSERT。该过程以结点z作为输入，其中z.key = v, z.left = NIL, z.right = NIL。
TREE-INSERT(T, z)
1 y = NIL
2 x = T.root
3 while x != NIL
4 y = x
5 if z.key < x.key
6 x = x.left
7 else x = x.right
8 z.p = y
9 if y == NIL
10 T.root = z
11 elseif z.key < y.key
12 y.left = z
13 else y.right = z
（二）实现查找、最大/小关键字查询
查找：输入一个指向树根的指针和一个关键字k，如果这个结点存在，TREE-SEARCH返回一个指向关键字k的节点的指针；否则返回NIL。
TREE-SEARCH(x, k)
1 if x == NIL or k == x.key
2 return x
3 if k < x.key
4 return TREE-SEARCH(x.left, k)
5 else return TREE-SEARCH(x.right, k)
最大关键字元素和最小关键字元素：通过从树根开始沿着left孩子指针直到遇到一个NIL，返回一个指向在以给定结点x为根的子树中的最小元素的指针；通过从树根开始沿着right孩子指针直到遇到一个NIL，返回一个指向在以给定结点x为根的子树中的最小元素的指针。
TREE-MINIMUM(x)
1 while x.left != NIL
2 x = x.left
3 return x
TREE-MAXIMUM(x)
1 while x.right != NIL
2 x = x.right
3 return x
（三）实现删除
从一棵二叉搜索树T中删除一个结点z的整个策略分为三种基本情况：
1）如果z没有孩子结点，那么只是简单地将它删除，并修改它的父结点，孩子结点指向NIL；
2）如果z只有一个孩子，那么将这个孩子提升到树中z的位置上，用z的孩子来替换z；
3）如果z有两个孩子，那么先找到z的后继结点y，如果y是z的右孩子，那么用y替换z，并仅留下y的右孩子；如果，y位于z的右子树中但并不是z的右孩子，先用y的右孩子替换y，然后再用y替换z；
定义一个过程TRANSPLANT，它是用另一棵子树替换一棵子树并成为其双亲的孩子结点：
TRANSPLANT(T, u, v)
1 if u.p == NIL
2 T.root = v
3 elseif u == u.p.left
4 u.p.left = v
5 else u.p.right = v
6 if v != NIL
7 v.p = u.p
TREE-DELETE(T, z)
1 if z.left == NIL
2 TRANSPLANT(T, z, z.right)
3 elseif z.right == NIL
4 TRANSPLANT(T, z, z.left)
5 else y = TREE-MINIMUM(z.right)
6 if y.p != z
7 TRANSPLANT(T, y, y.right)
8 y.right = z.right
9 y.right.p = y
10 TRANSPLANT(T, z, y)
11 y.left = z.left
12 y.left.p = y
实验总结
（一）二叉搜索树优点在于，在树上的基本操作与这棵树的高度成正比：对于一棵有n个结点的完全二叉树，在树上操作的最坏运行时间是Θ(lgn)。然而，如果树是一条n个结点组成的线性链，那么同样的操作就要花费Θ(n)的最坏运行时间。
（二）针对在构建树的过程中，出现最坏情况导致线性链的发生，可采取几种处理方式：可通过随机构建二叉搜索树；还可以设计二叉树的变体，即红黑树，红黑树的树高为O(lgn)；还可以使用B树。
（三）二叉搜索树是学习树的基础，为了充分利用二叉搜索树的优点，避免二叉树的最坏情况，从而研究出来了红黑树和B树。
附录（代码）
#include <stdio.h>
#include <stdlib.h>
typedef struct node *tree_pointer;
typedef struct node{
int key;
tree_pointerp;
tree_pointerleft;
tree_pointerright;
} *tree_pointer;
void tree_insert(tree_pointer z);
void print_tree(tree_pointer T_root, int n);
void transplant(tree_pointer T_root, tree_pointer u,tree_pointer v);
void tree_delete(tree_pointer T_root, tree_pointer z);
struct node * creat_node(int key);
struct node * tree_search(tree_pointer T_root, intkey);
struct node * tree_minimum(tree_pointer T_root);
struct node * tree_maximum(tree_pointer T_root);
int get_tree_height(tree_pointer T_root);
tree_pointer T_Root = NULL;
int main(){
inti,key,node_number,tree_height,search_key,delete_key;
tree_pointernew=NULL;
tree_pointersearch_result;
tree_pointerminimum;
tree_pointermaximum;
tree_pointerdelete;
printf("pleaseinput the number of nodes:");
scanf("%d",&node_number);
for(i = 0; i< node_number; i++ ){
printf("inputthe key:");
scanf("%d",&key);
new =creat_node(key);
tree_insert(new);
tree_height= get_tree_height(T_Root);
print_tree(T_Root,tree_height);
}
printf("thefinal tree:\n");
tree_height =get_tree_height(T_Root);
print_tree(T_Root,tree_height);
printf("\n");
minimum =tree_minimum(T_Root);
maximum =tree_maximum(T_Root);
printf("Inthis tree, the minimum number is:");
printf("%d\n",minimum->key);
printf("Inthis tree, the maximum number is:");
printf("%d\n",maximum->key);
printf("\n");
printf("whichkey do you want to search?\nplease input it:");
scanf("%d",&search_key);
printf("thesearching result: ");
search_result= tree_search(T_Root, search_key);
printf("(%p)and this (%p) refers to %d\n",search_result,search_result,search_result->key);
printf("\n");
printf("pleaseinput the node that you want to delete:");
scanf("%d",&delete_key);
printf("delete_key= %d\n",delete_key);
delete =tree_search(T_Root, delete_key);
printf("wewill delete:(%p) and it refers to %d\n", delete,delete->key);
printf("deletethe node and print the tree:\n");
tree_delete(T_Root,delete);
tree_height =get_tree_height(T_Root);
print_tree(T_Root,tree_height);
return 0;
}
void tree_insert(tree_pointer z){
tree_pointerx;
tree_pointery = NULL;
x = T_Root;
while(x !=NULL){
y = x;
if(z->key< x->key)
x =x->left;
else
x =x->right;
}
z->p = y;
if(y == NULL)
T_Root = z;
elseif(z->key < y->key)
y->left = z;
else
y->right= z;
}
void print_tree(tree_pointer T_root, int n){
int i;
if(T_root ==NULL)
return;
print_tree(T_root->right,n-1);
for(i = 0; i< n-1; i++)
printf(" ");
if(n > 0){
printf("---");
printf("%d\n",T_root->key);
}
print_tree(T_root->left,n-1);
}
struct node * creat_node(int key){
tree_pointernew;
new = (structnode *)malloc(sizeof(struct node));
new->key = key;
return new;
}
int get_tree_height(tree_pointer T_root){
if(!T_root)
return 0;
intleft_height,right_height;
left_height = get_tree_height(T_root->left);
right_height= get_tree_height(T_root->right);
return(left_height < right_height)?(right_height+1):(left_height+1);
}
struct node * tree_search(tree_pointer T_root, intkey){
while((T_root!= NULL) && (key != T_root->key)){
if(key< T_root->key)
T_root= T_root->left;
else
T_root= T_root->right;
}
returnT_root;
}
struct node * tree_minimum(tree_pointer T_root){
while(T_root->left!= NULL)
T_root =T_root->left;
returnT_root;
}
struct node * tree_maximum(tree_pointer T_root){
while(T_root->right!= NULL)
T_root =T_root->right;
returnT_root;
}
void transplant(tree_pointer T_root, tree_pointer u,tree_pointer v){
if(u->p ==NULL)
T_root =v;
else if(u ==u->p->left)
u->p->left = v;
else
u->p->right= v;
if(v != NULL)
v->p =u->p;
}
void tree_delete(tree_pointer T_root, tree_pointer z){
tree_pointery=NULL;
if(z->left== NULL)
transplant(T_root,z , z->right);
elseif(z->right == NULL)
transplant(T_root,z , z->left);
else{
y =tree_minimum(z->right);
if(y->p!= z){
transplant(T_root,y , y->right);
y->right = z->right;
y->right->p= y;
}
transplant(T_root, z , y);
y->left = z->left;
y->left->p= y;
}
}