数据结构之树和二叉树的应用

《数据结构之树和二叉树的应用》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第六章树和二叉树的应用6.1二叉排序树和平衡二叉树在实际应用中，常常需要在一组记录中检索一个记录，向其中插入一个记录或者把找到的记录删除。如果记录无序，查找起来将会很慢。如果记录有序，查找将会很快。但是遇到动态增减变化时，需要移动大量的元素。即使使用链表结构，查找起来也相当麻烦。非常需要一中插入、删除、和检索记录效率都很高的数据组织方法。二叉排序（查找、搜索）树就是这样一种高效的数据结构。5842987090634555836710图6.1二叉排序树6.1.1二叉排序树的基本概念二叉排序树也称二叉查找树或二叉搜索树。它或者是一棵空树；或者有性

2、质：（1）若其左子树不空，则左子树上所有结点的值均小于根结点的值。（2）若其右子树不空，则右子树上所有结点的值均大于根结点的值。（3）左右子树也为二叉排序树。图5.21就是一棵二叉排序树。二叉排序树通常采用二叉链存储结构。二叉链存储结构的结点类型定义：typedefstructtnode{KeyTypekey;//关键字域ElemTypedata;//其他数据域structtnode*lchild,*rchild;//指针}BSTNode;中序遍历二叉排序树可以得到有序序列。6.1.2二叉排序树的基本运算二叉排序树的基本运算如下：1.BSTS

3、earch(bt,k)在二叉排序树bt中，查找值为k的结点。2.BSTInsert(bt,k)在二叉排序树bt中，插入值为k的结点。3.CreateBST(bt,str,n)创建二叉排序树4.输出二叉排序树DispBST(bt)5.删除结点BSTDelete(bt,k)1.查找结点BSTSearch(bt,k)方法：将给定值k与查找树的根结点关键码比较。若相等，查找成功，结束查找过程。否则，a．当给k小于根结点关键码，查找将在以左子女为根的子树上继续进行；b．当给k大于根结点关键码，查找将在以右子女为根的子树上继续进行；c．若K等于当前结点的

4、关键字，则返回；如此反复，直至找到或子树为空，查找失败时20为止。例如，查找图5.21中关键字等于45的结点。从根结点开始比较。45<63，在左子树中查找；45<55，在左子树中查找；45>42，在右子树中查找；45=45，查找成功，返回。再如，查找图5.21中关键字等于73的结点。从根结点开始比较。73>63，在右子树中查找；73<90，在左子树中查找；73>70，在右子树中查找；73<83，在左子树中查找；5.83的左子树为空，查找失败。所以稽核中不含关键字等于73的结点。查找二叉排序树的算法BSTNode*BSTSearch(BSTNo

5、de*bt,KeyTypek){BSTNode*p=bt;while(p!=NULL&&p->key!=k){if(kkey)p=p->lchild;/*沿左子树查找*/elsep=p->rchild;/*沿右子树查找*/}If(p!=NULL)return(p);elseprintf(“找不到”);}2.二叉排序树的插入BSTInsert(bt,k)向二叉排序树中插入一个结点的过程：设待插入结点的关键码为kx，为将其插入，先要在二叉排序树中进行查找，若查找成功，按二叉排序树定义，待插入结点已存在，不用插入；查找不成功时，则插入之。因

6、此，新插入结点一定是作为叶子结点添加上去的。例如：记录的关键码序列为：63，90，70，55，67，42，98，83，10，45，58，则构造一棵二叉排序树的过程如图5.22所示：70906355674298709063556742709063556770906355709063639063φ5842987090634555836710429870906345558367107090635567839810427090635567839842图6.2构造二叉排序树插入算法：intBSTInsert(BSTNode*&bt,KeyTypek){

7、BSTNode*f,*p=bt;while(p!=NULL){if(p->key==k)return(0);f=p;/*f指向*p结点的双亲结点*/20if(p->key>k)p=p->lchild;/*k小，在左子树查找*/elsep=p->rchild;/*否则在右子树找*/}p=(BSTNode*)malloc(sizeof(BSTNode));p->key=k;p->lchild=p->rchild=NULL;if(bt==NULL)bt=p;elseif(kkey)f->lchild=p;elsef->rchild=p;re

8、turn(1);}3.二叉排序树的构造CreateBST(bt,str,n)上例说明，构造一棵二叉排序树则是从空树出发逐个插入结点的过程。创建算法：voidCrea