第6章特殊二叉树CPP.ppt

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

1、第六章特殊二叉树9/10/202106.1.1定义与概念二叉搜索树(BinarySearchingTree)(又称二叉排序树(BinarySortingTree))或者是一棵空树；或者是一棵具有如下特性的非空二叉树：若左子树非空，则左子树上所有结点的关键字均小于根结点的关键字；若右子树非空，则右子树上所有结点的关键字均大于根结点的关键字。(3)左右子树也都是二叉搜索树。特点：中序遍历序列有序。6.1二叉搜索树9/10/202116.1.2二叉搜索树的二叉链表的存储结构与一般二叉树存储结构相同：structBTreeNode{ElemTypedat

2、a;BTreeNode*left;BTreeNode*right;};9/10/20212φ(a)(c)(d)(b)6.1.3二叉搜索树的运算1．构造一棵二叉搜索树—插入(6.1.3-3.)【例】关键字序列为(38,26,62,94,35,50,28,55),构造一棵二叉搜索树的过程如下：构造的过程就是不断插入的过程；新结点总是作为终端结点插入的。图6-29/10/20213(f)(h)(e)(38,26,62,94,35,50,28,55)图6-2(g)9/10/20214插入算法的思路：设待插入结点的值(或关键字)为item。从根结点起将it

3、em与当前结点作比较：如果item比当前结点小，则将当前结点的左孩子作为当前结点；否则将右孩子作为当前结点；重复上述过程，直到当前结点为空。此时当前结点的双亲结点是插入点。如果item比该双亲结点小，则将item作为其左孩子；否则作为其右孩子。二叉搜索树的非递归插入算法(PP215-216.doc);在插入算法基础上的二叉搜索树生成算法(PP216.doc)9/10/202152.建立二叉搜索树(利用插入算法)形参：BST-指向二叉搜索树的指针a-数据源数组；n—数据数voidCreateBSTree(BTreeNode*&BST,ElemTyp

4、ea[],intn){BST=NULL;for(inti=0;i

5、树中删除一个结点的算法思想(6.1.3-4.)从二叉搜索树中删除一个结点之后，使其仍能保持二叉搜索树的特性。设待删结点为p(p为指向待删结点的指针)，其双亲结点为f，以下分三种情况进行讨论。图6-39/10/20218p结点为叶子结点直接删除pp9/10/20219(2)p结点只有左子树pL或只有右子树pR直接用左子树或右子树替代ppp9/10/202110(3)p结点既有左子树pL又有右子树pR1)用p的右子树替代p；2)把p的左子树置于p的右子树的中序序列之前。p9/10/2021111)用p的右子树替代p；2)把p的左子树置于p的右子树的中

6、序序列之前。p9/10/2021126.2堆6.2.1堆的定义堆分为小根堆和大根堆两种，小根堆是有如下特性的一棵完全二叉树：(1)若树根结点有左孩子，则根结点的值小于等于左孩子结点的值；(2)若树根结点有右孩子，则根结点的值小于等于右孩子结点的值；(3)以左、右孩子为根的子树又各是一个(小根)堆。图6-4(a)小根堆9/10/202113大根堆的定义与上类似，只要把“小于等于”改为“大于等于”即可。堆所对应的完全二叉树的特点是：所有分支结点的值均不小于(或不大于)其子女的值，即每棵子树根结点的值是最大(或最小)的。即堆顶元素是整个序列中最大(或最

7、小)的元素。堆来源于优先队列。图6-4(b)大根堆9/10/2021146.2.2堆的抽象数据类型6.2.3堆的存储结构由于堆是完全二叉树，所以适合用顺序存储。为此按层对各结点依次编号(从0开始)。【注意】如果从0开始编号，则：如果i>0，则序号为i的结点的双亲结点的序号为(i-1)/2如果编号为i的结点有左孩子，则其左孩子结点的序号为2i+1；如果有右孩子，则其右孩子结点的序号为2i＋2。图6-4(a)小根堆图6-5(a)9/10/202115【注意】如果从0开始编号，则：如果i>0，则序号为i的结点的双亲结点的序号为(i-1)/2如果

8、编号为i的结点有左孩子，则其左孩子结点的序号为2i+1；如果有右孩子，则其右孩子结点的序号为2i＋2。图6-4(b)大根堆图6-5(b)