二叉排序树基本操作详解
二叉排序树基本操作详解巧若拙(欢迎转载,但请注明出处:http://blog.)
所谓二叉排序树,指的是一棵空二叉树,或者是一棵具有如下特性的非空二叉树:
1。若它的左子树非空,则左子树上所有结点的值均小于根结点的值;
2。若它的右子树非空,则右子树上所有结点的值均大于根结点的值;
3。左,右子树本身又各是一棵二叉排序树。
二叉排序树的基本操作包括二叉排序树的输出,查找,生成(插入)和删除。
一:二叉排序树的输出:
关于二叉排序树的输出,我总结了以下几种方式:按递增次序(即中序遍历)输出结点,按递减次序输出结点,按层序输出结点,按凹入表表示输出结点和按嵌套括号表示输出结点。代码如下:
程序代码:
/* 函数名称:InOrderPrint 函数功能:按递增次序(即中序遍历)输出结点 输入变量:BiTree p:指向二叉树结点p的指针 输出变量;无 */ void InOrderPrint(BiTree p) { if (p != NULL) { InOrderPrint(p->lchild); //遍历左子树 printf("%c ", p->data);//输出该结点 InOrderPrint(p->rchild); //遍历右子树 } } /* /* 函数名称:DestOrderPrint 函数功能:按递减次序遍历输出结点 先遍历右子树,再输出结点,然后遍历左子树 输入变量:BiTree p:二叉树(或子树)根结点p 输出变量;无 */ void DestOrderPrint(BiTree p) { if (p != NULL) { DestOrderPrint(p->rchild); //遍历右子树 printf("%c ", p->data);//输出该结点 DestOrderPrint(p->lchild); //遍历左子树 } } /* 函数名称:LevelOrderPrint 函数功能:层序遍历输出结点。 使用一个队列,先将二叉树根结点入列。队头结点退列并输出,若它有左孩子,将左孩子入列;若它有右孩子,将右孩子入列。如此直到队列空为止。 输入变量:BiTree BT:二叉树BT的头指针 输出变量;无 */ void LevelOrderPrint(BiTree BT) { BiTree p, queue[MAXSIZE]; int front = 0, rear = 0; if (BT != NULL) { queue[rear++] = BT; while (front < rear) { p = queue[front++]; //队头结点退列并输出 printf("%c ", p->data);//输出该结点 if (p->lchild != NULL) { queue[rear++] = p->lchild; } if (p->rchild != NULL) { queue[rear++] = p->rchild; } } } } 函数名称:DisplayBiTree 函数功能:给定一个二叉树,输出其嵌套括号表示。 首先输出根结点,然后再依次输出它的左子树和右子树,不过在输出左子树之前要打印左括号,在输出右子树之前后要打印右括号;另外,依次输出左,右子树要至少有一个不为空,若都为空则不输出。 输入变量:BiTree BT:二叉树BT的头指针 输出变量;无 */ void DisplayBiTree(BiTree BT) { if (BT != NULL) { printf("%c", BT->data); if (BT->lchild != NULL || BT->rchild != NULL) { printf("("); DisplayBiTree(BT->lchild); if (BT->rchild != NULL) { printf(","); } DisplayBiTree(BT->rchild); printf(")"); } } } /* 函数名称:DisplayBiTree 函数功能:给定一个二叉树,输出其凹入表表示法。 采用先序遍历的非递归函数,除了使用一个栈外,还增加一个场宽数组level[],儿子结点的场宽设置为width,即每下一层缩进width。 输入变量:BiTree BT:二叉树BT的头指针 输出变量;无 */ void DisplayIndent(BiTree BT) { BiTree p, stack[MAXSIZE]; int level[MAXSIZE] = {0}; int i, n, top = -1; const int width = 3; if (BT != NULL)//先判断是否为空树 { stack[++top] = BT; //根结点入栈 while (top >= 0) { p = stack[top]; //栈顶元素出栈并凹入显示该结点值 n = level[top--]; for (i=0; i<n; i++) printf(" "); printf("%c\n", p->data);//输出该结点 if (p->rchild != NULL) //如果该结点有右孩子,将右孩子入栈 { stack[++top] = p->rchild; level[top] = n + width; } if (p->lchild != NULL) //如果该结点有左孩子,将左孩子入栈,按照后入先出原则,左孩子先出栈 { stack[++top] = p->lchild; level[top] = n + width; } } } }
二:二叉排序树的查找:
普通的二叉树查找需要先查找某棵子树,找不到再到另一颗子树中查找,时间复杂度为O(N),而二叉排序树由于是有序的,故可以采用二分查找的方法。比较代码如下:
在普通二叉树b中查找x的过程为:
1。若b是空树,则搜索失败,否则
2。若x等于b的根结点的数据域之值,则查找成功;否则
3。搜索左子树,若查找成功,返回对应结点;否则
4。搜索右子树
程序代码:
/* 函数名称:LocateElment_2 函数功能:在普通二叉树中寻找值为x的结点 输入变量:BiTree b:二叉树(或子树)根结点b, ElemType x:数据x 输出变量;值为x的结点,若找不到则返回NULL */ BiTree LocateElment_2 (BiTree b, ElemType x) { BiTree p; if (b == NULL || b->data == x) return b; else { p = LocateElment_2(b->lchild, x); //到左子树中寻找 if (p != NULL) return p; else return LocateElment(b->rchild, x); //到右子树中寻找 } }
在二叉排序树b中查找x的过程为:
1。若b是空树,则搜索失败,否则
2。若x等于b的根结点的数据域之值,则查找成功;否则
3。若x小于b的根结点的数据域之值,则搜索左子树;否则
4。搜索右子树
程序代码:
/* 函数名称:LocateElment 函数功能:在二叉排序树中寻找值为x的结点 输入变量:BiTree b:二叉树(或子树)根结点b, ElemType x:数据x 输出变量;值为x的结点,若找不到则返回NULL */ BiTree LocateElment(BiTree b, ElemType x) { if (b == NULL || b->data == x) return b; else if (b->data > x) //到左子树中寻找 return LocateElment(b->lchild, x); else //到右子树中寻找 return LocateElment(b->rchild, x); }
这里补充一个有趣的应用:输出值为x的结点的路径。算法是先在二叉树中找到值为x的结点p,然后采用非递归后序遍历二叉树的方法,当后序遍历访问到结点s时,此时栈中的元素均为s所指结点的祖先,依次输出栈中元素即得到路径。代码如下:
程序代码:
/* 函数名称:PathPrint 函数功能:输出值为x的结点的路径 输入变量:BiTree BT:二叉树根结点BT, ElemType x:数据x 输出变量;无 */ void PathPrint(BiTree BT, ElemType x) { BiTree s = LocateElment_2(BT, x); if (s != NULL) Path(BT, s); else printf("\n%c不存在\n", x); } /* 函数名称:Path 函数功能:输出从根结点BT到结点s的路径 采用非递归后序遍历二叉树,当后序遍历访问到结点s时,此时栈中的元素均为s所指结点的祖先,依次输出栈中元素即得到路径。 输入变量:BiTree BT:二叉树根结点BT, BiTree s:二叉树的某个结点s 输出变量;无 */ void Path(BiTree BT, BiTree s) { BiTree p, stack[MAXSIZE];//p表示当前结点,栈stack[]用来存储结点 int tag[MAXSIZE] = {0}; //用来标志栈顶元素的右孩子是否被访问过,0表示未访问,1表示已访问 int i, top = -1; //栈空 if (BT != NULL)//先判断是否为空树 { p = BT; while (p || top >= 0) { if (p != NULL) //不急着输出结点数据,先访问左孩子 { stack[++top] = p; tag[top] = 0; //表明该结点的右子树尚未访问 p = p->lchild; } else { p = stack[top]; //取栈顶元素,但先不出栈 if (p->data == s->data) //找到结点p,输出其路径 { for (i=0; i<top; i++) { printf("%c->", stack[i]->data); } printf("%c\n", p->data); return; } if (tag[top] == 0) //若右子树尚未访问,访问其右孩子 { tag[top] = 1; //表明该结点的右子树已接受访问 p = p->rchild; } else { top--; //退栈,并让p指向NULL,以避免重复访问左孩子 p = NULL; } } } } }
三:二叉排序树的生成(插入)
向二叉排序树b中插入一个结点s的算法:
1。若b是空树,则将s所指结点作为根结点插入,否则
2。若s->data等于b的根结点的数据域之值,则什么也不做,或者在结构中增添一个标记,表示该结点数据出现的次数;否则
3。若s->data小于b的根结点的数据域之值,则把s所指结点插入到左子树中;否则
4。把s所指结点插入到右子树中
生成二杈排序树的过程是先有一个空树b,然后向该空树插入一个个结点实现的,因此,
生成一棵二叉排序树(输入单个字符,以#结束)函数如下:
程序代码:
/* 函数名称:CreateBiTree 函数功能:生成一棵二叉排序树(输入单个字符,以#结束) 输入变量:BiTree *bt:指向二叉树根结点bt的指针 输出变量;无 */ void CreateBiTree(BiTree *bt) { BiTree s; ElemType x; scanf("%c", &x); while (x != '#') { s = NewBiTree(x);//构造一个数据域为x的新结点 Insert(bt, s);//在二叉排序树中插入新结点s scanf("%c", &x); } } /* 函数名称:NewBiTree 函数功能:构造一个数据域为x的新结点 输入变量:ElemType x:数据x 输出变量;新结点s */ BiTree NewBiTree(ElemType x) { BiTree s = (BiTree)malloc(sizeof(BiTreeNode)); if (!s) { printf("Out of space!"); exit (1); } s->data = x; s->lchild = s->rchild = NULL; return s; } /* 函数名称:Insert 函数功能:在二叉排序树中插入新结点s 输入变量:BiTree *b:指向二叉树根结点b的指针 BiTree s:新结点s 输出变量;无 */ void Insert(BiTree *b, BiTree s) { if (*b == NULL) *b = s; else if ((*b)->data == s->data)//不做任何插入操作 return; else if((*b)->data > s->data)//把s所指结点插入到左子树中 Insert(&(*b)->lchild, s); else //把s所指结点插入到右子树中 Insert(&(*b)->rchild, s); }
四:二叉排序树的删除:
对于一般的二叉树来说,删去树中的一个结点是没有意义的,因为它将使以被删除的结点为根的子树变成森林,破坏了整棵树的结构。但是,对于二叉排序树,删去树上的一个结点相当于删去有序序列中的一个记录,只要在删除某个结点后不改变二叉排序树的特性即可。
程序代码:
/* 函数名称:DeleteBST 函数功能:删除二叉排序树中值为x的结点 输入变量:BiTree b:指向二叉树根结点b的指针 ElemType x:数据x 输出变量;新的根结点 */ BiTree DeleteBST(BiTree b, ElemType x) { if (b) { if (b->data == x) b = DelNode_1(b); else if (b->data > x) b->lchild = DeleteBST(b->lchild, x); else b->rchild = DeleteBST(b->rchild, x); } return b; }
在二叉排序树上删除一个结点的算法有两种方法。
第一种过程如下:
1。若p有左子树,用p的左孩子取代它;找到其左子树的最右边的叶子结点r,把p的右子树作为r的右子树。
2。若p没有左子树,直接用p的右孩子取代它。
第二种过程如下:
1。若p有左子树,找到其左子树的最右边的叶子结点r。若p的左孩子有右子树,即r的双亲不是p,则把r的左子树作为r双亲的右子树,把p的左子树作为r的左子树;否则直接把p的左子树作为r的左子树。把p的右子树作为r的右子树。
2。若p没有左子树,直接用p的右孩子取代它。
两种方法各有优劣,第一种操作简单一点,但均衡性不如第二种,因为它将结点p的右子树全部移到左边来了。下面将分别以两种种思路编写代码。
程序代码:
/* 函数名称:DelNode_1 函数功能:删除二叉树的结点p 输入变量:BiTree p:指向二叉树结点p的指针 输出变量;新的根结点 */ BiTree DelNode_1(BiTree p)//删除结点*p { BiTree r; if (p->lchild) //若p有左子树,用p的左孩子取代它 { r = p->lchild; //寻找左子树的最右结点 while (r->rchild) { r = r->rchild; } r->rchild = p->rchild; //被删结点p的右子树作为r的右子树 r = p->lchild; } else //p没有左孩子,则直接返回其右子树 { r = p->rchild; } free(p); return r; } /* 函数名称:DelNode_2 函数功能:删除二叉树的结点p 输入变量:BiTree p:指向二叉树结点p的指针 输出变量;新的根结点 */ BiTree DelNode_2(BiTree p) { BiTree q, r; if (p->lchild) { q = p; r = q->lchild; while (r->rchild) //寻找左子树的最右结点 { q = r; r = r->rchild; } if (p != q)//r的双亲不是p,则把r的左子树作为r双亲的右子树,r的左孩子指向p的左孩子 { q->rchild = r->lchild; r->lchild = p->lchild; } r->rchild = p->rchild; //被删结点p的右子树作为r的右子树 } else //p没有左孩子,则直接返回其右子树 { r = p->rchild; } free(p); return r; }
认真阅读函数DelNode_2,我们发现函数最终返回了新的根结点r,需要修改r的左右孩子指针,很容易出错,其实在这里我们删除的只是p的元素值,而不是它的地址,所以完全没有必要修改指针。
仔细观察,发现我们删除的地址实际上是p的左子树的最右边的叶子结点r的地址,所以我们只要把r的数据填到p中,然后把r删除即可。代码如下:
程序代码:
/* 函数名称:DelNode_3 函数功能:删除二叉树的结点p 输入变量:BiTree p:指向二叉树结点p的指针 输出变量;新的根结点 */ BiTree DelNode_3(BiTree p) { BiTree q, r; if (p->lchild) { q = p; r = q->lchild; while (r->rchild) //寻找左子树的最右结点 { q = r; r = r->rchild; } p->data = r->data; //把结点r的数据赋值给p,这样就可以直接删除结点r了。 if (p != q)//p的左孩子有右子树 { q->rchild = r->lchild; } else { q->lchild = r->lchild; } free(r); return p; } else //p没有左孩子,则直接返回其右子树 { r = p->rchild; free(p); return r; } }
二叉排序树性能分析
每个结点的度为该结点的层次数。最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和logn成正比(O(log2(n)))。最坏情况下,当先后插入的关键字有序时,构成的二叉排序树为一棵斜树,树的深度为n,其平均查找长度为(n + 1) / 2。也就是时间复杂度为O(n),等同于顺序查找。因此,如果希望对一个集合按二叉排序树查找,最好是把它构建成一棵平衡的二叉排序树(平衡二叉树)。