第6章特殊二叉树

《第6章特殊二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第6章特殊二叉树2021/7/17DS主要内容二叉搜索树1堆2哈夫曼树3线索二叉树4平衡二叉树52021/7/17DS6.1二叉搜索树6.1.1二叉搜索树的定义6.1.2二叉搜索树的抽象数据类型6.1.3二叉搜索树的运算2021/7/17DS6.1.1二叉搜索树的定义定义：又称做二叉排序树(BinarySortingTree)，它或者是一棵空树，或者是一棵具有如下特性的非空二叉树。(1)若它的左子树非空，则左子树上所有结点的关键字均小于树根结点的关键字；(2)若它的右子树非空，则右子树上所有结点的关键字均大于树根结点的关键字；(3)左、右子树本身又各是一棵二叉搜索树。二叉搜索树的定义是递

2、归的，所以。对它进行的各种运算的算法通常也是递归的。2021/7/17DS在一棵非空的二叉搜索树中，其结点的关键字是按照左子树、根和右子树有序的，所以对它进行中序遍历得到的结点序列必然是一个有序序列。右图所示就是一棵二叉搜索树。对此树进行中序遍历得到的结点序列为：12，15，18，23，26，30，52，63，74可见此序列是一个有序序列。6.1.1二叉搜索树的定义2021/7/17DS6.1.2二叉搜索树的抽象数据类型二叉搜索树的抽象数据类型包括数据和操作两个部分。数据部分为一棵二叉搜索树，它可以具有同一般二叉树一样的任何存储结构。操作部分除了已经讨论过的对一般二叉树的操作外，还具有对

3、二叉搜索树的一些常用操作，即查找、更新、插入和删除元素的操作。2021/7/17DS6.1.2二叉搜索树的抽象数据类型对二叉搜索树BST的查找、更新、插入和删除元素的操作声明如下：boolFind(BTreeNode*BST,ElemType&item);boolUpdate(BTreeNode*&BST,constElemType&item);voidInsert(BTreeNode*&BST,constElemType&item);boolDelete(BTreeNode*&BST,constElemType&item);2021/7/17DS6.1.3二叉搜索树的运算1.查找若二叉

4、搜索树为空，则表明查找失败，应返回假若item等于当前树根结点的值，则表明查找成功，应由引用参数item带回根结点的完整值并返回真若item小于当前树根结点的值，则继续在它的左子树上查找若item大于当前树根结点的值，则继续它的右子树上查找2021/7/17DS1.查找--递归算法boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败返回假else{if(item==BST->data){//若查找成功则带回元素值并返回真item=BST->data;returntrue;}elseif(item

5、->data)//向左子树继续查找returnFind(BST->left,item);else//向右子树继续查找returnFind(BST->right,item);}}2021/7/17DS1.查找--非递归算法boolFind1(BTreeNode*BST,ElemType&item)//二叉搜索树查找的非递归算法{while(BST!=NULL){if(item==BST->data){item=BST->data;returntrue;}elseif(itemdata)BST=BST->left;elseBST=BST->right;}returnfalse;}

6、2021/7/17DS6.1.3二叉搜索树的运算①查找23②查找482021/7/17DS6.1.3二叉搜索树的运算2.更新：更新算法与查找算法基本相同，区别仅有两点：一是在更新算法中当查找到待更新的元素时，应将item的值赋给该元素，而在查找算法中是将该元素的值赋给item带回；二是在更新算法中参数item可以为变参(即引用参数)，也可以为值参，而在查找算法中item参数只能为变参，因为需要它带回结点的完整值。2021/7/17DS6.1.3二叉搜索树的运算3.插入若当前二叉树为空，则由item元素生成的新结点将作为树根结点插入若item小于当前树根结点的值，则将新结点插入到它的左子树

7、上若item大于当前树根结点的值，则将新结点插入到它的右子树上2021/7/17DS3.插入voidInsert(BTreeNode*&BST,constElemType&item){if(BST==NULL){//把值为item的新结点链接到已找到的插入位置BTreeNode*p=newBTreeNode;p->data=item;p->left=p->right=NULL;BST=p;}elseif(itemdata