《《数据结构》教案树和二叉树.doc》由会员分享，可在线阅读，更多相关《《数据结构》教案树和二叉树.doc（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第6章 树和二叉树 本章中主要介绍下列内容： 树的定义和存储结构1 二叉树的定义、性质、存储结构2 二叉树的遍历、线索算法3 树和二叉树的转换4 哈夫曼树及其应用5 课时分配：理论6个学时,上机6个学时 重点、难点：二叉树的遍历、线索算法、哈夫曼树及其应用6.1 树 树的定义和基本运算6.1.1 树的定义树是一种常用的非线性结构。我们可以这样定义：树是n（n0）个结点的有限集合。若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树。由此可以看出，树的定义是递归。结点: 数据元素的内容及其指向其子树
2、根的分支统称为结点。结点的度 结点的分支数。终端结点（叶子） 度为0的结点。非终端结点 度不为0的结点。结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推。树的度 树中所有结点度的最大值。树的深度 树中所有结点层次的最大值。有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树。森林 是m（m0）棵互不相交的树的集合。在树结构中，结点之间的关系又可以用家族关系描述，定义如下：孩子、双亲 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲。 子孙 以某结点为根的子树中的所有结点都被称为是该结点的子孙。祖先 从根结点到该结点路
3、径上的所有结点。兄弟 同一个双亲的孩子之间互为兄弟。堂兄弟 双亲在同一层的结点互为堂兄弟。1树的基本运算 常用操作：（1） 构造一个树 CreateTree (T)（2）清空以T为根的树 ClearTree(T)（3）判断树是否为空 TreeEmpty(T)（4）获取给定结点的第i个孩子 Child(T,linklist,i) （5）获取给定结点的双亲 Parent(T,linklist)（6）遍历树Traverse(T)对树遍历的主要目的是将非线性结构通过遍历过程线性化，即获得一个线性序列。树的遍历顺序有两种，一种是先序遍历，即先访问根结点，然后再依次用同样的方法访问每棵子树；另一种是后序遍
4、历，即先依6.1.2 树的存储结构 类型定义：#define MAX_TREE_LINKLIST_SIZE 100typedef struct TElemtype info;int parent; ParentLinklist;typedef struct ParentLinklist elemMAX_TREE_LINKLIST_SIZE;int n; /树中当前的结点数目ParentTree;这种存储方法的特点是寻找结点的双亲很容易，但寻找结点的孩子比较困难。算法实现举例：int Parent(ParentTree T,int linklist) if (linklist=T.n) retu
5、rn -2;else return T.elemlinklist.parent;在C语言中，这种存储形式定义如下：#define MAX_TREE_LINKLIST_SIZE 10typedef struct ChildLinklistint child; /该孩子结点在一维数组中的下标值struct ChileLinklist *next; /指向下一个孩子结点CLinklist;typedef structElemtype info; /结点信息CLinklist *firstchild; /指向第一个孩子结点的指针TLinklist;typedef struct TLinklist el
6、emMAX_TREE_LINKLIST_SIZE; int n,root; /n为树中当前结点的数目，root为根结点在一维数组中的位置ChildTree;这种存储结构的特点是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的双亲在一维数组中的位置。获取给定结点第i个孩子的操作算法实现： int Child(ChildTree T, int linklist, int i) if (linklist=T.n) return -2； p=T.elemlinklist.fir
7、stchild; j=1;while (p&j!=i) p=p-next; j+;if (!p) return -2;else return p-child; 6.1.3 孩子兄弟表示法孩子兄弟表示法也是一种链式存储结构。它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其结点结构为：在C语言中，这种存储形式定义如下：typedef struct CSLinklistElemtype elem;struct CSLinklist *firstchild,*nextsibling;CSLinklist,*CSTree;void AllChild(CSTree T, CSTree p
8、) /输出树中p指针所指结点的所有孩子信息q=p-fisrtchild;while (q) printf(%c,q-elem); q=q-nextsibling; 6.2 二叉树6.2.1 二叉树的定义和基本运算1定义定义：二叉树是另一种树形结构。它与树形结构的区别是：（1）每个结点最多有两棵子树；（2）子树有左右之分。二叉树也可以用递归的形式定义。即：二叉树是n（n0）个结点的有限集合。当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。二叉树的5种形态2. 二叉树的基本运算(略见教材)
9、（1） 构造一棵二叉树 CreateBTree ( BT)（2）清空以BT为根的二叉树 ClearBTree(BT)（3）判断二叉树是否为空 BTreeEmpty(BT)（4）获取给定结点的左孩子和右孩子 LeftChild(BT,linklist)，RightChild(BT,linklist)（5）获取给定结点的双亲 Parent(BT,linklist)（6）遍历二叉树Traverse(BT)3二叉树的性质二叉树具有下列5个重要的性质。【性质1】 在二叉树的第i层上最多有2i-1个结点（i1）。二叉树的第1层只有一个根结点，所以，i=1时，2i-1=21-1=20=1成立。假设对所有的j
10、，1ji成立，即第j层上最多有2j-1个结点成立。若j=i-1，则第j层上最多有2j-1=2i-2个结点。由于在二叉树中，每个结点的度最大为2，所以可以推导出第i层最多的结点个数就是第i-1层最多结点个数的2倍，即2i-2*2=2i-1。【性质2】 深度为K的二叉树最多有2K-1个结点（K1）。由性质1可以得出，1至K层各层最多的结点个数分别为：20,21,22,23,.,2K-1。这是一个以2为比值的等比数列，前n项之和的计算公式为：【性质3】 对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1。证明：假设度为1的结点个数为n1，结点总数为n，B为二
11、叉树中的分支数。因为在二叉树中，所有结点的度均小于或等于2，所以结点总数为：n=n0+n1+n2 （1）再查看一下分支数。在二叉树中，除根结点之外，每个结点都有一个从上向下的分支指向，所以，总的结点个数n与分支数B之间的关系为：n=B+1。又因为在二叉树中，度为1的结点产生1个分支，度为2的结点产生2个分支，所以分支数B可以表示为：B=n1+2n2。将此式代入上式，得：n=n1+2n2+1 （2）用（1）式减去（2）式，并经过调整后得到：n0=n2+1。满二叉树：如果一个深度为K的二叉树拥有2K-1个结点，则将它称为满二叉树。完全二叉树：有一棵深度为h，具有n个结点的二叉树，若将它与一棵同深度
12、的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1n的结点位置一一对应，则称这棵二叉树为完全二叉树。【性质4】 具有n个结点的完全二叉树的深度为 ?log2n?+1。其中，?log2n? 的结果是不大于log2n的最大整数。证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出：2K-1-1n2K-1将不等式两端加1得到：2K-1n2K将不等式中的三项同取以2为底的对数，并经过化简后得到：K-1log2nn，则结点i没有左孩子；否则其左孩子结点的编号为2i。（3）如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2
13、i+1。下面我们利用数学归纳法证明这个性质。我们首先证明（2）和（3）。当i=1时，若n3，则根的左、右孩子的编号分别是2，3；若n3，则根没有右孩子；若nn，且2(i+1)=n时，结点i+1只有左孩子，而没有右孩子；当2(i+1)n，结点i+1既没有左孩子也没有右孩子。以上证明得到（2）和（3）成立。下面利用上面的结论证明（1）。对于任意一个结点i，若2in，则左孩子的编号为2i，反过来结点2i的双亲就是i，而 ?2i/2?=i；若2i+1n，则右孩子的编号为2i+1，反过来结点2i+1的双亲就是i，而 ?(2i+1)/2? =i，由此可以得出（1）成立。4二叉树的存储结构二叉树也可以采用两
14、种存储方式：顺序存储结构和链式存储结构。6.2.2 顺序存储结构这种存储结构适用于完全二叉树。其存储形式为：用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容。下面是一棵二叉树及其相应的存储结构在C语言中，这种存储形式的类型定义如下所示：#define MAX_TREE_LINKLIST_SIZE 100typedef struct Elemtype elemMAX_TREE_LINKLIST_SIZE; /根存储在下标为1的数组单元中int n; /当前完全二叉树的结点个数QBTree;这种存储结构的特点是空间利用率高、寻找孩子和双亲比较容易。下面我们给出完全二叉树在这种存储
15、形式下的操作算法。（1）构造一棵完全二叉树void CreateBTree(QBTree *BT,Elemtype elem ,int n)if (n=MAX_TREE_LINKLIST_SIZE) n=MAX_TREE_LINKLIST_SIZE-1;for (i=1; ielemi=elemi;BT-n=n;（2）获取给定结点的左孩子 int LeftCHild(QBTree BT,int linklist)if (2*linklistBT.n) return 0;else return 2*linklist;RightChild(BT,linklist)与这个操作类似，读者可试着自行完成
16、。（3）获取给定结点的双亲 int Parent(QBTree BT,int linklist)if (1=linklist&linklistLchild);PreOrder(BT-Rchild); （2）中序遍历递归算法void InOrder(BTree BT)if (BT) InOrder(BT-Lchild);Visit(BT);InOrder(BT-Rchild);（3）后序遍历递归算法void PostOrder(BTree BT)if (BT) PostOrder(BT-Lchild);PostOrder(BT-Rchild);Visit(BT);42 按层次遍历二叉树实现方法为
17、从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。void LevelOreder(QBTree BT)for (i=1;iLchild) Visite(p-Lchild);EnQueue(&Q,p-Lchild); /处理左孩子if (!p-Rchild) Visite(p-Rchild);EnQueue(&Q,p-Rchild); /处理右孩子5 典型二叉树的操作算法51 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉树的位置上填补一个特殊的字符，比如
18、，#。在算法中，需要对每个输入的字符进行判断，如果对应的字符是#，则在相应的位置上构造一棵空二叉树；否则，创建一个新结点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。【算法5-12】BTree Pre_Create_BT( )getch(ch);if (ch=#) return NULL; /构造空树else BT=(BTree)malloc(sizeof(BTLinklist); /构造新结点BT-data=ch;BT-lchild =Pre_Create_BT( ); /构造左子树BT-rchild =Pre_Create_BT( )
19、; /构造右子树return BT;52 计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。【算法5-13】void Leaf(BTree BT,int *count)if (BT) Leaf(BT-child,&count); /计算左子树的叶子结点个数 if (BT-lchild=NULL&BT-rchild=NULL) (*count)+;Leaf(BT-rchild,&count); /计算右子树的叶子结点个数53 交换二叉树的左右子树许多操作可以利用三
20、种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。void change_left_right(BTree BT)if (BT) change_left_right(BT-lchild);change_left_right(BT-rchild);BT-lchildBT-rchild;54 求二叉树的高度这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。int hight(BTree
21、 BT)/h1和h2分别是以BT为根的左右子树的高度if (BT=NULL) return 0;else h1=hight(BT-lchild);h2=hight(BT-right);return maxh1,h2+1;6树、森林与二叉树的转换61 树、森林转换成二叉树将一棵树转换成二叉树的方法：将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。特点：一棵树转换成二叉树后，根结点没有右孩子。将森林转换成二叉树的方法与
22、一棵树转换成二叉树的方法类似，只是把森林中所有树的根结点看作兄弟关系，并对其中的每棵树依依地进行转换。62 二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。第三节 哈夫曼树及其应用1哈夫曼树的定义在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路
23、径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158构造哈夫曼树的过程：（1）将给定的n个权值w1,w2,.,wn作为n个根结点的权值构造一个具有n棵二叉树的森林T1,T2,.,Tn，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构
24、造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。假设有一组权值5,29,7,8,14,23,3,11，下面我们将利用这组权值演示构造哈夫曼树的过程。这就是以上述8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2712判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if (socre60) pri
25、ntf(bad);else if (socre70) printf(pass);else if (score80) printf(general);else if (score90) printf(good);esle printf(very good);在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：3前缀编码在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编
26、码的方式。（1）等长编码这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可
27、以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到5,29,7,8,14,23,3,11；（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。最后得出每个字符的编码为：比如，发送一段编码：0000011011010010，接收方可以准确地通过译码得到：。