【算法导论】第12章二叉查找树

1、问题引入

　　查找树是一种数据结构，它支持多种动态集合操作，包括构造、查找、插入、删除、寻找最小值、寻找最大值等，其中构造过程主要采用不断插入值来完成。

　　二叉查找树中的关键字存储方式满足以下性质：设x为二叉查找树中的一个节点，如果y是x的左子树中的一个节点，则y->data < x->data;如果y是x的右子树中的一个节点，则y->data > x->data。

　　二叉查找树上执行的基本操作的时间与树的高度成正比，对于一棵含n个节点的完全二叉树，这些操作的最坏情况运行时间为o（lgn）。同样的，如果树是含有n个节点的线性链，则这些操作的最坏时间为o（n）。

2、数据结构

　　二叉查找树是按照二叉树结构来组织的，这样的树可以采用数组来表示，也可以采用链表结构来表示，不过数组表示没有链表结构简单明了，这里采用链表结构来表示，每一个节点就表示一个对象，节点中包含data数据部分、left指针（指向左儿子）、right指针（指向右儿子），如果某个节点的儿子节点不存在，则相应的儿子节点为NULL。

　　定义为：typedef struct treenode
　　　　　　{
　　　　　　　　elemType data;
　　　　　　　　struct treenode *left;
　　　　　　　　struct treenode *right;
　　　　　　}tree;

3、基本算法

3.1 构造二叉查找树算法

 1 //构造二叉查找树
 2 tree *makeTree(tree *p)
 3 {
 4     scanf("%d",&k);
 5     while(k!=-1)//以输入-1表示构造结束
 6     {
 7         p=insertTreeNode(p,k);//通过插入节点方式构造
 8         scanf("%d",&k);
 9     }
10     return(p);//得到树p
11 }

3.2 中序遍历算法

1 void printTree(tree *t)
2 {
3     if(t)
4     {
5         printTree(t->left);
6         printf("%d ",t->data);
7         printTree(t->right);
8     }
9 }

3.3 查找一个给定的关键字所在节点算法

1 tree *searchTreeNode(tree *p,elemType k)
2 {
3 if(p==NULL) || k=p->data
4     return p;
5 if(k<p->data)
6     return searchTreeNode(p->left,k);
7 else 
8     return searchTreeNode(p->right,k):
9 }

3.4 查找最大和最小关键字元素

 1 //在二叉查找树中查找最小节点
 2 tree *findMinTreeNode(tree *t)
 3 {
 4     if(t==NULL) //树为空
 5     {
 6         printf("error!!");
 7         return NULL;
 8     }
 9     while(t->left)//二叉查找树中的最小节点在最左边
10         t=t->left;
11     return(t);
12 }
13 //二叉查找树中的最大节点在最右边，算法类似。。。

3.5 在二叉查找树中插入一个节点

 1 //在二叉查找树中插入节点
 2 tree *insertTreeNode(tree *t,elemType e)
 3 {
 4     if(t==NULL)//定位到要插入的节点位置t=null
 5     {
 6         t=(tree *)malloc(sizeof(tree));
 7         if(t==NULL) printf("error!");
 8         t->data=e;
 9         t->left=NULL;
10         t->right=NULL;
11     }
12     else if(e<t->data )//节点值小于t节点值
13         t->left=insertTreeNode(t->left,e);
14     else //节点值不小于t节点值得
15         t->right=insertTreeNode(t->right,e);
16     return(t);//返回结果
17 }

3.6 在二叉查找树中删除一个节点

　　删除节点的操作稍微复杂一些，要分三种情况：

　　　　(a)如果要删除的节点没有子女，则定位到该节点之后直接删除即可。

　　　　(b)如果要删除的节点有一个子女，则定位到该节点之后，让节点的父节点直接指向该节点的子节点，然后删除该节点即可。

　　　　(c)如果要删除的节点有两个子女，则定位到该节点之后，找出其后继结点，用后继结点的data和附加数据替换该节点的数据，然后删除后继结点（递归调用删除算法）。

具体算法：

tree *deleteTreeNode(tree *t,elemType e)
{
    tree *p;
    if(t==NULL)
    {
        printf("error!!!\n");
        return NULL;
    }
    if(e < (t->data))//e小于t中的data值，则从t的左子树中删除e；
        t->left=deleteTreeNode(t->left,e);
    else if(e > (t->data))//e大于t中的data值，则从t的右子树中删除e；
        t->right=deleteTreeNode(t->right,e);
    else if((t->left) && (t->right))//找到节点且该节点的左右子树都存在
    {
        p=findMinTreeNode(t->right);//找到后继结点
        t->data=p->data;//将后继结点的值赋给t节点
        t->right=deleteTreeNode(t->right,t->data);//删除后继结点
    }
    else//找到节点且节点或者只存在一个子节点或者不存在子节点
    {
        p=t;
        if(t->left==NULL)
            t=t->right;
        else if(t->right==NULL)
            t=t->left;
        free(p);
        return(t);
    }
    return(t);
}

4、具体的代码实现：

View Code

  1 #include<stdlib.h>
  2 #include<stdio.h>
  3 typedef int elemType;
  4 typedef struct treenode
  5 {
  6     elemType data;
  7     struct treenode *left;
  8     struct treenode *right;
  9 }tree;
 10 tree *makeTree(tree *p);
 11 void printTree(tree *t);
 12 tree *insertTreeNode(tree *t,elemType e);
 13 tree *deleteTreeNode(tree *t,elemType e);
 14 tree *findMaxTreeNode(tree * t);
 15 tree *findMinTreeNode(tree *t);
 16 tree *findTreeNode(tree *t,elemType e);
 17 //-------------------------------------------------
 18 //构造二叉查找树
 19 tree *makeTree(tree *p)
 20 {
 21     int k;
 22     printf("构造树，请输入节点值(以-1结束)：\n");
 23     scanf("%d",&k);
 24     while(k!=-1)
 25     {
 26         p=insertTreeNode(p,k);
 27         scanf("%d",&k);
 28     }
 29     printf("\n");
 30     return(p);
 31 }
 32 //中序遍历二叉查找树
 33 void printTree(tree *t)
 34 {
 35     if(t)
 36     {
 37         printTree(t->left);
 38         printf("%d ",t->data);
 39         printTree(t->right);
 40     }
 41 }
 42 //在二叉查找树中查找最小节点
 43 tree *findMinTreeNode(tree *t)
 44 {
 45     if(t==NULL) 
 46     {
 47         printf("error!!");
 48         return NULL;
 49     }
 50     while(t->left)
 51         t=t->left;
 52     return(t);
 53 }
 54 //在二叉查找树中查找最大节点
 55 tree *findMaxTreeNode(tree *t)
 56 {
 57     if(t==NULL) 
 58     {
 59         printf("error!!");
 60         return NULL;
 61     }
 62     while(t->right)
 63         t=t->right;
 64     return(t);
 65 }
 66 //在二叉查找树中插入节点
 67 tree *insertTreeNode(tree *t,elemType e)
 68 {
 69     if(t==NULL)
 70     {
 71         t=(tree *)malloc(sizeof(tree));
 72         if(t==NULL) printf("error!");
 73         t->data=e;
 74         t->left=NULL;
 75         t->right=NULL;
 76     }
 77     else if(e<t->data )
 78         t->left=insertTreeNode(t->left,e);
 79     else 
 80         t->right=insertTreeNode(t->right,e);
 81     return(t);
 82 }
 83 //在二叉查找树中删除节点
 84 tree *deleteTreeNode(tree *t,elemType e)
 85 {
 86     tree *p;
 87     if(t==NULL)
 88     {
 89         printf("error!!!\n");
 90         return NULL;
 91     }
 92     if(e < (t->data))//e小于t中的data值，则从t的左子树中删除e；
 93         t->left=deleteTreeNode(t->left,e);
 94     else if(e > (t->data))//e大于t中的data值，则从t的右子树中删除e；
 95         t->right=deleteTreeNode(t->right,e);
 96     else if((t->left) && (t->right))//找到节点且该节点的左右子树都存在
 97     {
 98         p=findMinTreeNode(t->right);//找到后继结点
 99         t->data=p->data;//将后继结点的值赋给t节点
100         t->right=deleteTreeNode(t->right,t->data);//删除后继结点
101     }
102     else//找到节点且节点或者只存在一个子节点或者不存在子节点
103     {
104         p=t;
105         if(t->left==NULL)
106             t=t->right;
107         else if(t->right==NULL)
108             t=t->left;
109         free(p);
110         return(t);
111     }
112     return(t);
113 }        
114 void main()
115 {
116     int d;
117     tree *p;
118     p=NULL;
119     //-----------------------------------------------
120     p=makeTree(p);
121     printf("构造后的树采用中序遍历结果为：\n");
122     printTree(p);
123     //-----------------------------------------------
124     printf("插入节点：\n");
125     printf("请输入要插入的节点值：\n");
126     scanf("%d",&d);
127     p=insertTreeNode(p,d);
128     printf("插入节点后的树采用中序遍历结果为：\n");
129     printTree(p);
130     //-----------------------------------------------
131     printf("删除节点：\n");
132     printf("请输入要删除的节点值：\n");
133     scanf("%d",&d);
134     p=deleteTreeNode(p,d);
135     printf("删除节点后的树采用中序遍历结果为：\n");
136     printTree(p);
137     //------------------------------------------------
138     printf("\n构造树中的最小节点为：\n");
139     p=findMinTreeNode(p);
140     printf("%d  \n",p->data);
141     printf("\n构造树中的最大节点为：\n");
142     p=findMaxTreeNode(p);
143     printf("%d  \n",p->data);
144 }

5、参考资料：

（1）http://kb.cnblogs.com/a/2336968/

（2）算法导论