树与二叉树C课件

第6章树与二叉树(三树与二叉树C（精品）第6章树与二叉树(三本章的基本内容是61树及其抽象数据类型62二叉树及其抽象数据类型63二叉树的表示和实现64线索化二叉树6.5树、森林与二叉树的转换6.6哈夫曼编码与哈夫曼树构造二叉树建立一棵二查树必须明确以下两点(1)结点与父母结点以及孩子结点之间的层次关系(2)兄弟结点间的左右子树的次序关系能够唯一确定一棵二查树的表示(1)先根和中根序列表示(2)标明空子树的先根序列表示第6章树与二叉树C（精品）第6章1本章的基本内容是61树及其抽象数据类型62二叉树及其抽象数据类型63二叉树的表示和实现64线索化二叉树6.5树、森林与二叉树的转换6.6哈夫曼编码与哈夫曼树本章的基本内容是2构造二叉树建立一棵二查树必须明确以下两点(1)结点与父母结点以及孩子结点之间的层次关系(2)兄弟结点间的左右子树的次序关系能够唯一确定一棵二查树的表示(1)先根和中根序列表示(2)标明空子树的先根序列表示构造二叉树31)先根和中根序列表示ii+先根序列BIDIGCEIFIHpreorder左子树右子树根左子树右子树n-1中根序列|DGB|A左子树根右子树(a)先根与中根次序遍历序列(b)确定根、左子树、右子树1)先根和中根序列表示4在BinaryTree类中增加以下构造方法publicBinaryTree(Tlprelist,Tlinlist)Ithisroot=create(prelist,inlist,0,0,prelistlength);privateBinaryNodecreate(TDprelist,T[inlist,intpreStart,intinStart,intnif(n<=0)returnnul;Telem=prelist[preStart];BinaryNode<T>p=newBinaryNode<T>(elem);inti=Owhile(i<n&&!elem.equals(inlist[inStart+))1++pleft=create(prelist,inlist,preStart+1,instart,i)pright=create(prelist,inlist,preStart+i+1,instart+i+1,n-1-1)returnp在BinaryTree类中增加以下构造方法5(2)标明空子树的先根序列表示(a)AB(b)AB(c)AB..c(d)ABd.g.ce.FH(2)标明空子树的先根序列表示6在BinaryTree类中增加以下构造方法publicBinaryTree(T[prelist)Ithisroot=creatprelist);1privateinti=OprivateBinarynode<T>create(TIprelist)(BinaryNode<T>p=null;(i<prelistlength[Telem=prelist[]+if(elem!=nullip=newBinaryNode<t>(elem);pleft=create(prelistpright=create(prelist)returnp在BinaryTree类中增加以下构造方法7如何获得结点在一种遍历序列中的前驱或后继?leftdataright∧H人(a)一棵二叉树(b)二叉链表如何获得结点在一种遍历序列中的前驱或864线索化二叉树(ThreadedBinarytree)用二叉链表法(Child,rchild)存储包含n个结点的二叉树,结点的指针区域中会有多少个空指针?分析:用二叉链表存储包含n个结点的二叉树,结点必有2n个链域除根结点外,二又树中每一个结点有且仅有一个双亲(直接前驱),所以只会有n-1个结点的链域存放指针,指向非空子女结点所以,空指针数目=2n-(n-1)=n+1个64线索化二叉树(ThreadedBinarytree9②二叉链表空间效率这么低,能否利用这些空闲区存放有用的信息或线索?可以用它来存放当前结点的直接前驱和后继等线索,以加快查找速度问题的提出:普通二叉树只能找到结点的左右孩子信息,而该结点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来,则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树可能是根、或最左(右)叶子②二叉链表空间效率这么低,能否利用这些空闲区10树与二叉树C课件11树与二叉树C课件12树与二叉树C课件13树与二叉树C课件14树与二叉树C课件15树与二叉树C课件16树与二叉树C课件17树与二叉树C课件18树与二叉树C课件19树与二叉树C课件20树与二叉树C课件21树与二叉树C课件22树与二叉树C课件23树与二叉树C课件24树与二叉树C课件25树与二叉树C课件26树与二叉树C课件27树与二叉树C课件28树与二叉树C课件29树与二叉树C课件30树与二叉树C课件31树与二叉树C课件32树与二叉树C课件33树与二叉树C课件34树与二叉树C课件35树与二叉树C课件36树与二叉树C课件37树与二叉树C课件38树与二叉树C课件39树与二叉树C课件40树与二叉树C课件41树与二叉树C课件42树与二叉树C课件43树与二叉树C课件44树与二叉树C课件45树与二叉树C课件46树与二叉树C课件47树与二叉树C课件48树与二叉树C课件49树与二叉树C课件50树与二叉树C课件51树与二叉树C课件52第6章树与二叉树(三树与二叉树C（精品）第6章树与二叉树(三本章的基本内容是61树及其抽象数据类型62二叉树及其抽象数据类型63二叉树的表示和实现64线索化二叉树6.5树、森林与二叉树的转换6.6哈夫曼编码与哈夫曼树构造二叉树建立一棵二查树必须明确以下两点(1)结点与父母结点以及孩子结点之间的层次关系(2)兄弟结点间的左右子树的次序关系能够唯一确定一棵二查树的表示(1)先根和中根序列表示(2)标明空子树的先根序列表示第6章树与二叉树C（精品）第6章53本章的基本内容是61树及其抽象数据类型62二叉树及其抽象数据类型63二叉树的表示和实现64线索化二叉树6.5树、森林与二叉树的转换6.6哈夫曼编码与哈夫曼树本章的基本内容是54构造二叉树建立一棵二查树必须明确以下两点(1)结点与父母结点以及孩子结点之间的层次关系(2)兄弟结点间的左右子树的次序关系能够唯一确定一棵二查树的表示(1)先根和中根序列表示(2)标明空子树的先根序列表示构造二叉树551)先根和中根序列表示ii+先根序列BIDIGCEIFIHpreorder左子树右子树根左子树右子树n-1中根序列|DGB|A左子树根右子树(a)先根与中根次序遍历序列(b)确定根、左子树、右子树1)先根和中根序列表示56在BinaryTree类中增加以下构造方法publicBinaryTree(Tlprelist,Tlinlist)Ithisroot=create(prelist,inlist,0,0,prelistlength);privateBinaryNodecreate(TDprelist,T[inlist,intpreStart,intinStart,intnif(n<=0)returnnul;Telem=prelist[preStart];BinaryNode<T>p=newBinaryNode<T>(elem);inti=Owhile(i<n&&!elem.equals(inlist[inStart+))1++pleft=create(prelist,inlist,preStart+1,instart,i)pright=create(prelist,inlist,preStart+i+1,instart+i+1,n-1-1)returnp在BinaryTree类中增加以下构造方法57(2)标明空子树的先根序列表示(a)AB(b)AB(c)AB..c(d)ABd.g.ce.FH(2)标明空子树的先根序列表示58在BinaryTree类中增加以下构造方法publicBinaryTree(T[prelist)Ithisroot=creatprelist);1privateinti=OprivateBinarynode<T>create(TIprelist)(BinaryNode<T>p=null;(i<prelistlength[Telem=prelist[]+if(elem!=nullip=newBinaryNode<t>(elem);pleft=create(prelistpright=create(prelist)returnp在BinaryTree类中增加以下构造方法59如何获得结点在一种遍历序列中的前驱或后继?leftdataright∧H人(a)一棵二叉树(b)二叉链表如何获得结点在一种遍历序列中的前驱或6064线索化二叉树(ThreadedBinarytree)用二叉链表法(Child,rchild)存储包含n个结点的二叉树,结点的指针区域中会有多少个空指针?分析:用二叉链表存储包含n个结点的二叉树,结点必有2n个链域除根结点外,二又树中每一个结点有且仅有一个双亲(直接前驱),所以只会有n-1个结点的链域存放指针,指向非空子女结点所以,空指针数目=2n-(n-1)=n+1个64线索化二叉树(ThreadedBinarytree61②二叉链表空间效率这么低,能否利用这些空闲区存放有用的信息或线索?可以用它来存放当前结点的直接前驱和后继等线索,以加快查找速度问题的提出:普通二叉树只能找到结点的左右孩子信息,而该结点的直接前驱和直接后继只能在遍历过程中获得若将遍历后对应的有关前驱和后继预存起来,则从第一个结点开始就能很快“顺藤摸瓜”而遍历整个树可能是根、或最左(右)叶子②二叉链表空间效率这么低,能否利用这些空闲区62树与二叉树C课件63树与二叉树C课件64树与二叉树C课件65树与二叉树C课件66树与二叉树C课件67树与二叉树C课件68树与二叉树C课件69树与二叉树C课件70树与二叉树C课件71树与二叉树C课件72树与二叉树C课件73树与二叉树C课件74树与二叉树C课件75树与二叉树C课件76树与二叉树C课件77树与二叉树C课件78树与二叉树C课件79树与二叉树C课件80树与二叉树C课件81树与二叉树C课件82树与二叉树C课件83树与二叉