第六章特殊二叉樹一

1、第六章 特殊二叉樹 一 . 第六章 二叉樹的應(yīng)用習(xí) 題 六一、填空題1.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為 C 。A O(n) B O(1) C O(log2n) D O(n2)2.向二叉搜索樹中插入一個元素時，其時間復(fù)雜度大致為 B 。A O(1) B O(log2n) C O(n) D O(nlog2n)3.根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為 D 。A O(n) B O(log2n) C O(n2) D O(nlog2n) 4.從堆中刪除一個元素的時間復(fù)雜度為 C 。A O(1) B O(n) C O(log2n) D O(nlog2n)5.向堆中插入一個元

2、素的時間復(fù)雜度為 A 。A O(log2n) B O(n) C O(1) D O(nlog2n)6.權(quán)值分別為3，8，6，2，5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)路徑長度為 D 。A 24 B 48 C 72 D 51二、填空題1.在一棵二叉搜索樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定 小于 該結(jié)點的值，右子樹上所有結(jié)點的值一定 大于 該結(jié)點的值。2.對一棵二叉搜索樹進行中序遍歷時，得到結(jié)點序列是一個 有序序列 。3.從一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點的值，則表明 查找成功 ，若元素的值小于根結(jié)點的值，則繼續(xù)向 左子樹 查找，若元素的值大于根結(jié)點的值，則繼續(xù)向 右子樹

3、 查找。4.在一個堆的順序存儲中，若一個元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)為 2i+1 ，右孩子元素的下標(biāo)為 2i+2 。5.在一個小根堆中，堆頂結(jié)點的值是所有結(jié)點中的 最小值 ，在一個大根堆中，堆頂結(jié)點的值是所有結(jié)點中的 最大值 。6.當(dāng)向一個小根堆插入一個具有最小值的元素時，該元素需要逐層 向上 調(diào)整，直到被調(diào)整到 堆頂 位置為止。7.當(dāng)從一個小根堆中刪除一個元素時，需要把 堆尾 元素填補到 堆頂 位置，然后再按條件把它逐層 向下 調(diào)整。8.在哈夫曼編碼中，若編碼長度只允許小于等于4，則除了已對兩個字符編碼為0和10外，還可以最多對 4 個字符編碼。三、普通題1.已知一組元素(46,2

4、5,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉樹。解：略2.已知一棵二叉排序樹如圖6-11所示，若從中依次刪除72,12,49,28結(jié)點，試分別畫出每刪除一個結(jié)點后得到的二叉排序樹。解：略28/ 12 49 / 16 34 72/ /30 633.設(shè)在一棵二叉排序樹的每個結(jié)點中，含有關(guān)鍵字key域和統(tǒng)計相同關(guān)鍵字結(jié)點個數(shù)的count域，當(dāng)向該樹插入一個元素時，若樹中已存在與該元素的關(guān)鍵字相同的結(jié)點，則就使該結(jié)點的co unt域增1，否則就由該元素生成一個新結(jié)點而插入到樹中，并使其count域置為1，試按照這種插入要求編寫一個算法。解：void Insert(BT

5、reeNode*&BST,ElemType& item)/向二叉排序樹中插入一個不重復(fù)元素item，若樹中存在該元素，則將一配結(jié)點值域中的/count域的值加1即可/從二叉排序樹中查找關(guān)鍵字為item.key的結(jié)點，若查找成功則指針t指向該點結(jié)點，否則/指針s指向待插入新結(jié)點的雙親結(jié)點BTreeNode *t=BST,*S=NULL;while(t!=NULL)s=t;if(item.key=t->data.key)break;else if(item.key<t->data.key)t=t->left;e

6、lset=t->right;/元素已存在，則將其值域中的count域的值增1，否則建立新結(jié)點并插入到合適位置if(t!=NULL)t->data.count+;elseBTreeNode* p=new BTreeNode;p->data=item;p->data.count=1;p->left=p->right=NULL;if(s=NULL)BST=p;elseif(item.key<s->data.key)s->left=p;elses->right=p

7、;4.編寫一個非遞歸算法求出二叉排序樹中的關(guān)鍵字最大的元素。解：ElemType FindMax(BTreeNode* BST)/從二叉排序樹中返回關(guān)鍵字最大的元素if(BST=NULL)cerr<<"不能在空樹上查找最大值!"<<end1;exit(1);BTreeNode* t=BST;while(t->right!=NULL)t=t->right;return t->data;5.假定一棵二叉排序樹被存儲在具有ABTList數(shù)組類型的一個對象BST中，試編

8、寫出以下算法。1.初始化對象BST。解：void InitBTree(ABTList BST)/將樹置空BST0.left=0;/建立空閑鏈接表BST0.right=1;for(int i=1;i<BTreeMaxSize-1;i+)BSTi.right=i+1;BSTBTreeMaxSize-1.right=0;2.向二叉樹排序樹中插入一個元素。解：void Insert(ANTList BST,int&t,const ElemType& item)/向數(shù)組中的二叉排序樹插入一個元素item的遞歸算法，變參t初始指向樹根結(jié)點if(t=0)/進行插

9、入操作/取出一個空閑結(jié)點int p=BST0.right;if(p=0)cerr<<"數(shù)組空間用完!"<<end1;exit(1);/修改空閑鏈表的表頭指針，使之指向下一個空閑結(jié)點BST0.right=BSTp.right;/生成新結(jié)點BSTp.data=item;BSTp.left=BSTp.right=0;/把新結(jié)點插入到確定的位置t=p;else if(item.key<BSTt.data.key) Insert(BST,BSTt.left,item);/向左子樹中插入元素elseI

10、nsert(BST,BSTt.right,item);/向右子樹中插入元素void Insert(ABTList BST,const ElemType& item)/向數(shù)組中的二叉排序樹插入一個元素item的非遞歸算法/為新元素尋找插入位置int t=BST0.left,parent=0;while(t!=0)parent=t;if(item.key<BSTt.data.key)t=BSTt.left;elset=BSTt.right;/由item生成新結(jié)點并修改空閑鏈表的表頭指針int p=BST0.right;if(p=0)cerr<&l

11、t;"數(shù)組空間用完!"<<end1;exit(1);BST0.right=BSTp.right;BSTp.data=item;BSTp.left=BSTp.right=0;/將新結(jié)點插入到二叉排序樹中的確定位置上if(parent=0)BSTo.left=p;else if(item.key<BSTparent.data.key)BSTparent.left=p;elseBSTparent.right=p;3.根據(jù)數(shù)組a中的n個元素建立二叉排序樹。解：void CreateBSTree(ABTList BST,Ele

12、mType a,int n)/利用數(shù)組中的元素建立二叉排序樹的算法for(int i=0;i<n;i+)Insert(BST,BST0.left,ai);4.中序遍歷二叉排序樹。解：void Inorder(ABTList BST,int t)/對數(shù)組中的二叉樹進行中序遍歷的遞歸算法if(t!=0)Inorder(BST,BSTt.left);cout<<BSTt.data.key<<''Inorder(BST,BSTt.right);void Inorder(ABTList BST)/對數(shù)組

13、中的二叉樹進行中序遍歷的非遞歸算法int s10;/定義用于存儲結(jié)點指針的棧int top=-1; /定義棧頂指針并賦初值使s棧為空int p=BST0.left;/定義指針p并使樹根指針為它的初值while(top=-1|p!=0)/當(dāng)棧非空或p指針非0時執(zhí)行循環(huán)while(p!=0)top+;stop=p;p=BSTp.left;if(top!=-1)p=stop;top-;cout<<BSTp.data.key<<''p=BSTp.right;5.寫出一個完整程序調(diào)用上述算法。解：#include&a

14、mp;lt;iostream.h>#include<stdlib.h>const int BTreeMaxSize=50;struct studentint key;int rest;typedef student ElemType;/定義二叉排序樹中元素的類型為student記錄型struct ABTreeNode/定義二叉排序樹的結(jié)點類型ElemType data;int left,right;typedef ABTreeNode ABTListBTreeMaxSize;/定義保存二叉排序樹的數(shù)組類型，各算法同上，在 此省略void main()student a8=36,54,25,30,43,18,50,28;/為簡單起見在每個元素中只給出關(guān)鍵字ABTList bst;I