第五章 树状结构

第五章ffi^^W5-1基本赧念榭状结横可以用来描述有分支的结横，由一1固或一1固以上的筋黑所鲍成的有限集合，其特^如下：存在一固特殊的筋黑，稠舄榭根root），其绘的筋黑分舄〃0固互斥集合，包括T、t、T…T，每固集合稠舄子榭。如下圈：123几ACBDGEFA舄根筋黑占、ACBDGEFA舄根筋黑占、B、C及D均舄A的子筋黑占⑴Root:照父筋黑的筋黑稠舄根筋黑，如A（2）Parent（父筋黑）：每一筋黑的上屑筋黑舄父筋黑，如B的父筋黑瞌A。⑶children（子筋黑占）：每一筋黑占的下屑筋黑占舄子筋黑占，如B的子筋黑占有E及F。⑷siblings（兄弟筋黑）:有共同父筋黑的筋黑稠舄兄弟筋黑，如B、C、D之父筋黑舄A,因此彼此舄兄弟筋黑。（5）degree（分支度）：子榭的［固敷稠舄^筋黑占之分支度，如A的分支度舄3,B的分支度舄2。（6）terminalnode然端筋黑占或榭篥筋黑占）:照子筋黑占的筋黑占，如E、F、C、G。⑺non-terminalnode（非^端筋黑占）：榭篥以外的筋黑占均舄非^端筋黑，如B、D、A。（8）level仆皆屑或F皆度）：A舄F皆屑1,B、C、D舄F皆屑2,E、F、G舄皆屑3。⑼height（高度）：榭的最大皆度，例如此榭皆度舄3。（10）forest:（11）ancestor和decendent考题1：播就明上述事有名朋I之涵蓑舆解禅5-2二元榭(Binarytree)表示法若取n［固^结】固敷舄最大固定畏度，而每［固筋黑占资料结横如下dataLink1Link2.linkn此椒n元榭十分浪«^^空冏，假言殳此n元榭有m固筋黑，那此榭共使用n*m固^结榄位，同日寺除敷根外，每一固非空^结都指向—固筋黑，得知空^结固敷舄nxm~（m-1）=mx（n-1）+1,而n元榭^结浪费率舄mx（n-1）+1，因此可推得各元榭浪费率。mxn其中二元榭浪费率最少3勺1/2，因此一般探用二元榭。考题2：舄何榭状^橘偷存於资料庸畤探用二元W^tt.W^明舆推虱（1）二元梅定羡二元榭最多只有雨固子筋黑，也就是^分支度小於或等於2。同日寺二元榭必殖考虑次序^保。氧例：深度舄k的二元榭^筋黑敷最多是2k-1（完满榭Fullybinarytree），菁式^明之。特殊二元B^WFullybinarytree完满二元榭Completebinarytree完整二元榭望寸於完整二元榭而言，此二元榭陪屑舄：取整敷log2N)+1考题3:m*出深度4的所有二元榭。SkewedbinarytreeStrictlybinarytree探用阵列^rn^存二元b将二元榭想像成一1固完满二元棱f,业使用一^障列建立二元榭表示方式及索引值的配置如下圈：

1随彳麦配置索引值如下：Index1234567contentABCDE同日寺依撮下列规则小於父筋黑占的值放在左子筋黑占，大於父筋黑占的值放在右子筋黑占，建立下列二元榭程式氧例/*［名W］：ch05_01.cpp［示®］:建立二元榭*//*[名W]：ch05_01.cpp[示氧]:建立二元榭*/#include<iostream>usingnamespacestd;intmain()(inti,level;intdata[]={6,3,5,9,7,8,4,2};//原始障列intbtree[15]={0};〃存放二元敷障列cout<<"原始障列内容："<<endl;for(i=0;i<8;i++)cout<<"["<<data[i]<<"]";cout<<endl;for(i=0;i<8;i++)〃把原始障列中的值逐一比望寸

for(level=1;btree[level]!=0;)〃比段榭根及障列内的值//cout<<"btree["<<level<<"]="<<btree[level]<<endl;//if(data[i]>btree[level])〃如果障列内的值大於榭根，则elselevel=level*2+1;〃如果障列内的值小於或等於榭根，则往左子榭比段level=level*2;//如果子榭筋黑占的值不舄0if(data[i]>btree[level])〃如果障列内的值大於榭根，则elselevel=level*2+1;〃如果障列内的值小於或等於榭根，则往左子榭比段level=level*2;//如果子榭筋黑占的值不舄0,则再舆障列内的值比段一次btree[level]=data[i];〃把障列值放入二元榭cout<<"二元榭内容："<<endl;for(i=1;i<16;i++)cout<<"["<<btree[i]<<"]";cout<<endl;return0;考题4:言青撰舄一程式，能将障列资料儒存於二元榭中。青冏富有障列资料敷舄N日寺，将其以二元榭方式儒存日寺，JS^要宣告多大的障列。Ans:其资料陪屑舄k>log2N+1,其完满二元榭(Fullybinarytree通量舄2k-1，因此至少要有2k-1^«料簟敷，也就是障列要有2k-1大小才行。探用鲤结串列佛存二元榭二元榭之^结串列筋黑占宣告如下：LChildDataRChild指向左子榭筋黑值指向右子榭筋黑宣告如下：structtree(intdata;tree*left;tree*right;｝；5-3二元榭走^(BinaryTreeTraversal)所^走^就是「拜^榭中所有的筋黔各一次」，在走^废瘠榭中资料!•换舄^性^保。按照二元榭由左向右的特性，下列二元榭有三椒走⑴BAC中序走^(Inorder)榭根在中冏上例走^次序舄：DBEACF探用遁迪演算法舄voidInorder(btreeptr)(if(ptr!=NULL)(Inorder(ptr->left);//printleftcout<<“["<<setw(2)<<ptr->data<<“]”;//printrootInorder(ptr->right);//printright}}⑵ABC前序走^(Preorder)榭根在前面上例走^次序舄：ABDECF探用遁迪演算法舄voidPreorder(btreeptr)(if(ptr!=NULL)(cout<<“["<<setw(2)<<ptr->data<<“]”;//printrootPreorder(ptr->left);//printleftPreorder(ptr->right);//printright}}⑶BCA废序走^(Postorder)榭根在彳麦面上例走^次序舄：DEBFCA探用遁迪演算法舄voidPostorder(btreeptr)(if(ptr!=NULL)(Postorder(ptr->left);//printleftPostorder(ptr->right);//printrightcout<<“["<<setw(2)<<ptr->data<<“]”;//printroot考题5:W^明前序、中序及废序走^之避迪演算法？氧例篇青冏以下二元榭的中序、前序及彳麦序表示法舄何?中序FDBEHGIAC前序ABDFEGHIC彳麦序FDHIGEBCA考题6:需出中序、废序及前序演算法之走^次序(4)将敷列胃成二元椅氧例：一榭被表成A(B(CD)E(F(G)H(I(JK)L(MN)))),*出二元^^W及前、中及彳麦序走^结果二元榭筑例程式氧例程式：建立一程式，指定二元榭内容，业再列印二元榭彳麦把榭的前、中、彳麦序列印出来。程式码氧例#include<iostream>usingstd::cout;usingstd::endl;usingstd::cin;#include<iomanip>usingstd::setw;structtree(intdata;tree*left;tree*right;};tree*create_tree(tree*,int);voidpreorder(tree*);voidinorder(tree*);voidpostorder(tree*);intmain()(intarray[]={3,2,4,1,5,6,7,8,9,10,11};tree*ptr=NULL;//宣告棒蚌艮cout<<"Theoriginalmatrixcontentis"<<endl;//Printouttheoriginaldatafor(inti=0;i<11;i++){ptr=create_tree(ptr,array[i]);cout<<setw(3)<<array[i];}cout<<endl;cout<<"Thecontentofbinarytree."<<endl;cout<<"Sortingbypre-orderis"<<endl;preorder(ptr);cout<<endl;cout<<"Sortingbyinorderis"<<endl;inorder(ptr);cout<<endl;cout<<"Sortingbypostorderis"<<endl;postorder(ptr);cout<<endl;return0;}tree*create_tree(tree*root,intval)(tree*newnode;//declareanewnodetree*current;//declareacurrentnodetree*backup;//declareabackupnodenewnode=newtree;//createaspacetosavedatanewnode->data=val;newnode->left=NULL;newnode->right=NULL;if(root==NULL)//Firstpointistheroot(root=newnode;returnroot;}else(for(current=root;current!=NULL;)(backup=current;//reservetherootnodeif(current->data>val)elsecurrent=current->right;}if(backup->data>val)backup->left=newnode;elsebackup->right=newnode;}returnroot;}voidpreorder(tree*ptr)(if(ptr!=NULL)(cout<<"["<<setw(3)<<ptr->data<<"]";preorder(ptr->left);preorder(ptr->right);}}voidinorder(tree*ptr)(if(ptr!=NULL)(inorder(ptr->left);cout<<"["<<setw(3)<<ptr->data<<"]";inorder(ptr->right);voidpostorder(tree*ptr)if(ptr!=NULL)postorder(ptr->left);postorder(ptr->right);cout<<"["<<setw(3)<<ptr->data<<"]";考题7：^-^ft»,S出二元榭，再以中序、废序及前序演算法做二元^算W(BinaryExpressionTree)定羲：瘠算循式辑换成二元^算榭(A)考虑算循中遑算子(operator)的结合性(associativity)舆僵先罹(priority)，再遹富的加上括号虎。(B)由最内屑括号虎逐步向外，利用5S算子富榭根，左遑5S算元富左子榭，右遑^算元富右子榭，其中僵先罹最低的^算子做舄此二元^算榭的榭根。氧例1：A-B*(-C+(-3.5))Stepl.加括号虎(A-(B*((-C)+(-3.5))))Step2.做出二元^算榭Step3.各椒表示法前序表示法-A*B+-C-3.5中序表示法A-B*-C+-3.5彳麦序表示法ABC-3.5-+*-氧例：言青将A/B**C+D*E-A*C化舄二元榭：Stepl.加括号虎(((A/(B**C)+(D*E))-(A*C))考题8:^-ffi＞算式，然废查出二元榭，业以走^方式^出前序、中序及废序走^^果。1.4二元WB%研究(1)二元榭排序二元榭舄一椒很好的排序模式，因舄建立二元榭同日寺资料已经经遏初步比段判»,＞依照二元榭建立规则存放资料，其规则如下：第一［固翰入^料舄此二元榭之榭根«料以遁迪方式舆榭根逵行比段，小於榭根置於左子榭，大於榭根置於右子榭。因舄左子榭的内容一定小於榭根，右子榭之值一定大於榭根，因此只要用中序走^方式就可以得到由小至大排序好的资料。-＞因此如果想求由大到小排列资料，可将最彳麦结果置於堆叠内再POP出魁考题9:播就明探用何规刖建立二元榭，再探用何椒走^方式可以得氧例：利用中序走^逵行排序#include<iostream>usingstd::endl;usingstd::cout;usingstd::cin;#include<iomanip>usingstd::setw;structtree(intdata;tree*left;tree*right;};tree*create_tree(tree*,int);voidin(tree*);intmain()(intdata;tree*ptr=NULL;cout<<"Pleaseinputdata,endwith-1:"<<endl;cin>>data;while(data!=-1)(ptr=create_tree(ptr,data);cin>>data;}cout<<"\nAftersorting,thedatais"<<endl;in(ptr);return0;}tree*create_tree(tree*root,intval)(tree*newnode;//declareanewnodetree*current;//declareacurrentnodetree*backup;//declareabackupnodenewnode=newtree;//createaspacetosavedatanewnode->data=val;newnode->left=NULL;newnode->right=NULL;if(root==NULL)//Firstpointistheroot(root=newnode;returnroot;}else(for(current=root;current!=NULL;)(backup=current;//reservetherootnodeif(current->data>val)current=current->left;elsecurrent=current->right;}if(backup->data>val)backup->left=newnode;elsebackup->right=newnode;}returnroot;}voidin(tree*ptr)(if(ptr!=NULL)(in(ptr->left);cout<<setw(3)<<ptr->data;in(ptr->right);}}考S：W^明如何输入一鲍数值资料建立一侗二元榭，播瘠程式碉富出来?(2)二元搜尊榭(BinarySearchTree)二分榭：一［固二元榭符合「^»»料大於左子筋黔榭且小於右子筋黔^jW之。因舄二分榭便於用来搜尊及排序，又W^二元排序数或二元搜辱榭二元搜葬榭之特黑占：可以是空集合，但若不是空集合则筋黑上一定要有一固^值。每一固榭根的值殖大於左榭根每一固榭根的值殖小於右榭根左右榭根也是二元搜葬榭榭的每侗筋黑占值不同。^例：建立一侗二元搜母榭，业输入要辱找的值，如果筋黑中有相等的值，伽眼示出搜辱的次敷，如果找不到此值，也伽眼示飘息。#include<iostream>usingstd::endl;usingstd::cout;usingstd::cin;#include<iomanip>usingstd::setw;structtree(intdata;tree*left;tree*right;};tree*create_tree(tree*,int);tree*Pre(tree*,int);intmain()(intdata;tree*ptr=NULL;cout<<"Pleaseinputdata,endwith-1:"<<endl;cin>>data;while(data!=-1)(ptr=create_tree(ptr,data);cin>>data;}cout<<"\nPleaseinputthesearchingvalue,endwith0"<<endl;cin>>data;while(data!=0)(if((Pre(ptr,data))!=NULL)//searchingbinarytreecout<<"Thevalue"<<data<<"hasbeenfound!"<<endl;elsecout<<"Youcannotfindthevalue!"<<endl;cout<<"\nPleaseinputthesearchingvalue