树与二叉树的关系

《树与二叉树的关系》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.4.1树的存储结构6.4.2树、森林与二叉树的相互转换6.4.3树与森林的转换6.4树、森林和二叉树的关系6.4.1树的存储结构树的主要存储方法有：一、双亲表示法二、孩子表示法三、孩子兄弟表示法一、双亲表示法：用一组连续的空间来存储树中的结点，每个结点附设一个指示器指示其双亲结点在表中的位置，其结点的结构如下：数据双亲DataParent1245637树的双亲表示法如下图：1615140302-11ParentData543210结点序号672双亲表示法的优点：利用了树中每个结点（根结点除外

2、）只有一个双亲结点的性质，使得查找某个结点的双亲结点非常容易。双亲表示法的缺点：求某个结点的孩子时，需要遍历整个表。#defineMAX100typedefstructTNode{DataTypedata;intparent;}TNode;一棵树可以定义为：typedefstruct{TNodetree[MAX];intnodenum;/*结点数*/}ParentTree;双亲表示法的结点结构定义：二、孩子表示法：通常是把每个结点的孩子结点排列起来，构成一个单链表，称为孩子链表。n个结点共有n个

3、孩子链表（叶结点的孩子链表为空表）。n个结点的数据和n个孩子链表的头指针又组成一个顺序表。树的孩子链表表示法见p175的图6.26孩子表示法示意图:ABCDEFG1A2B3C4D5E6F7Groot=1num=7datafch7562340111335par带双亲的孩子表示法:孩子表示法的结构定义：typedefstructChildNode/*孩子链表结点的定义*/{intChild;structChildNode*next;}ChildNode;typedefstruct/*树的定义*/{D

4、ataNodenodes[MAX];/*顺序表*/introot,num;/*根结点指示及结点个数*/}ChildTree;typedefstruct/*顺序表结点的结构定义*/{DataTypedata;ChildNode*FirstChild;}DataNode;三、孩子兄弟表示法孩子兄弟表示法又称二叉链表表示法，表中每个结点设有两个链域，分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）结点。fchdatansib第一孩子下一兄弟结点结构:孩子兄弟表示法的结点结构定义：typedefst

5、ructCSNode{DataTypedata;StructCSNode*FCh,*Nsib;}CSNode,*CSTree;孩子兄弟表示法示意图：ABCDEFGrootABCEDFG优点：便于实现树的各种操作；可实现树(森林)与二叉树的相互转换。ABCDEFGABCDEFG无兄弟无右孩子森林中兄弟树将转为右子树对应的关系：树二叉树根根第一孩子左孩子下一兄弟右孩子一、树转换为二叉树约定树中每一个结点的孩子结点按从左到右的次序顺序编号，即把树看作为有序树。6.4.2树、森林与二叉树的相互转换将一棵

6、树转换为二叉树的方法：⑴树中所有相邻兄弟之间加一条连线。⑵对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。⑶以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。树转换为二叉树示意图ABECDFGHABECDFGHABECDFGHABECDFGH森林转换为二叉树的方法为：（1）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的

7、二叉树就是由森林转换得到的二叉树。二、森林转换为二叉树森林转换为二叉树示意图BECHDIFJGBCDEFGHIJ森林转换为二叉树的实例另见p179的图6.31递归方法描述森林转换为二叉树:将森林F看作树的有序集F={T1，T2，…,TN}，它对应的二叉树为B（F）：（1）若N＝0，则B（F）为空。（2）若N>0，则：二叉树B（F）的根为森林中第一棵树T1的根；B（F）的左子树为B（{T11，…，T1m}），其中{T11，…，T1m}是T1的子树森林；B（F）的右子树是B（{T2，…，TN}）。二

8、叉树转换为树或森林的方法为：（1）若某结点是其双亲的左孩子，则把该结点的右孩子、右孩子的右孩子、……都与该结点的双亲结点用线连起来。（2）删掉原二叉树中所有双亲结点与右孩子结点的连线。（3）整理由（1）、（2）两步所得到的树或森林，使之结构层次分明。三、二叉树转换为树或森林二叉树转换为森林的示意图DABCEFGHIJDABCEFGHIJHIJGDABCEF若B是一棵二叉树，T是B的根结点，L是B的左子树，R为B的右子树，设B对应的森林F（B）中含有的n棵树为T1,T2,…,Tn，则有：（1）B为