第6章-树与二叉树1数据结构

第六章树和二叉树一种典型的非线性数据结构本章重点： 二叉树的存储结构及其基本操作 树和森林与二叉树的转换关系6.1树的定义和基本术语树：n个结点的有限集；在非空树中：有且仅有一个根结点（Root）;当n>1时，其余结点可以分为m个(m>0)互不相交的有限集T1,T2,···,Tm,其中Ti为根的子树ABCDEFGHIJKLM树的抽象数据类型

ADTTree{

数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则为空树； 若D仅含一个数据元素，则R为空集，否则R={H},H是如下二元关系：

(1)在D中存在唯一点称为根结点的数据元素root，它在关系H下无前驱；

(2)若D-{root}≠Ø，则存在D-{root}的一个划分D1,D2,···Dm(m>0),对任意j≠k(1≤j,k≤m)有Dj∩Dk＝Ø,且对任意的i(1≤i≤m),唯一存在数据元素xi∈Di,有<root,xi>∈H; (3)对应于D-{root}的划分，H-{<root,x1>,···,<root,xm>}有唯一点一个划分H1,H2,···Hm(m>0),对任意j≠k(1≤j,k≤m),有Dj∩Dk＝Ø,且对任意的i(1≤i≤m),Hi是Di上的二元关系，(Di,{Hi})是一棵符合本定义的树，称为根root的子树。 基本操作P：

InitTree(&T);CreatTree(&T);ClearTree(&T);TreeEmpty(T);

DestoryTree(&T); ······ }//ADTTree树的其它三种表示方法：BACDFKLGIJHM(A(B(E(K,L),F),C(G),D(H(M),I,J)))EABCDGEFHIJMLK树结构中的基本术语结点：一个数据元素及指向其子树的分支结点的度：结点拥有的子树数叶子结点：度为0的结点分支结点：度不为0的结点树的度：树内各结点的度的最大值孩子：结点的子树的根父亲(双亲)：兄弟：同一父亲的孩子祖先：从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中的任一结点层次：根为第一层，根的孩子为第二层···堂兄弟：双亲在同一层的结点互为堂兄弟深度：树中结点的最大层次有序树：将树的结点的各个子树都看成是有序的，则无序树森林ABCDEFGHIJKLM例：已知一棵树边的集合如下，请画出这颗树，并回答问题{<I,M>,<I,N>,<E,I>,<B,E>,<B,D>,<A,B>,<G,J>,<G,K>,<C,G>,<C,F>,<H,L>,<C,H>,<A,C>}(1)根结点是？(2)叶子结点有？(3)G的双亲是？(4)G的祖先有？(5)G的孩子？(6)E的子孙(7)E的兄弟，F的兄弟(8)B和N地层次号(9)树的深度ABCEDGHIJMNKFL6.2二叉树二叉树的定义每个结点至多有两棵子树(即度<=2),子树有左右之分。抽象数据类型ADTBinaryTree{

数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则为空二叉树； 若D不为空集，则R={H},H是如下二元关系：

(1)在D中存在唯一点根结点root，它在关系H下无前驱；

(2)若D-{root}≠Ø，则存在D-{root}＝{Dl,Dr},且Dl∩Dr＝Ø (3)若Dl≠Ø,则Dl中存在唯一的元素xl,<root,xl>∈H,且存在Dl上的关系Hl;若Dr≠Ø,则Dr中存在唯一的元素xr,<root,xr>∈H,且存在Dr上的关系Hr. (4)(Dl,{Hl})是一棵符合本定义的二叉树，为根的左子树； (Dr,{Hr})是一棵符合本定义的二叉树，为根右子树

基本操作二叉树的五种基本形态空二叉树仅有根结点的二叉树右子树为空的二叉树左、右子树都不空的二叉树左子树为空的二叉树二叉树的性质性质1在二叉树的第i层上至多有2i-1个结点（i≥1）证明：归纳法i=1时，命题显然成立，2i-1=20=1假设所有的1≤j<i都成立，那么证明当j=i时命题也成立： 由假设知，第i-1层上的结点个数为2i-2,而在二叉树中第i层上结点的个数最多是上一层结点数的2倍，即为

2×2i-2=2i-1性质2深度为k的二叉树至多有2k-1个结点，（k≥1）证明：利用性质1的结论性质3对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1证明：设n1=度为1的结点数，n为结点总数，则n=n0+n1+n2

分析二叉树种的分叉数B：n=B+1B=n1+2n2所以有n=n1+2n2+1故：n0=n2+1满二叉树：一棵深度为k且有2k-1个结点的二叉树完全二叉树：深度为k有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，成为完全二叉树。性质4具有n个结点的完全二叉树的深度为log2n＋1123576123456712111098123456712111098141315123564满二叉树完全二叉树非完全二叉树性质5如果对一棵有n个结点的完全二叉树（其深度为层，每层从左到右），则对任一结点i(1≤i≤n),有：

(1)如果i＝1，则结点i是二叉树的根，无双亲；若i>1,则其双亲parent(i)是结点

(2)如果2i>n,则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i. (3)如果2i+1>n,则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i+1. log2n＋1i/2i/2ii+12i+12i+32i2i+2二叉树的存储结构顺序存储结构#defineMAX_TREE_SIZE100;Typedef

TElemTypeSqBiTree[MAX_TREE_SIZE]；SqBiTreebt;将完全二叉树上编号为i的结点元素存储在一维数组的下标为i-1的分量中。链式存储结构链式存储结构DataLCHILDRCHILDPARENTlchildrchilddatalchildrchilddataparent在含有n个结点的二叉链表中有n+1个空链域二叉链表的定义Typedef

struct

BiTNode{

TElemTypedata;

struct

BiTNode*lchild,*rchild;}BiTNode,*BiTree;

基本操作：CreatBiTree(BiTree&T);//按先序顺序构造一棵二叉树PreOrderTraverse(BiTreeT)；//先序遍历二叉树InOrderTraverse(BiTreeT)；//中序遍历二叉树PostOrderTraverse(BiTreeT)；//后序遍历二叉树LevelOrderTraverse(BiTreeT)；//层次遍历二叉树6.3遍历二叉树和线索二叉树6.3.1遍历二叉树先序（根）遍历中序（根）遍历后序（根）遍历（1）访问根结点（2）先序遍历左子树（3）先序遍历右子树（1）后序遍历左子树（2）后序遍历右子树（3）访问根结点（1）中序遍历左子树（2）访问根结点（3）中序遍历右子树例:表达式(a+b*(c-d)-e/f)的二叉树－＋/a×febc－d先序遍历二叉树：-+a*b-cd/ef中序遍历二叉树：a+b*c-d-e/f后序遍历二叉树：abcd-×＋ef/-StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){if(T){ Visit(T->data)

PreOrderTraverse(T->lchild,Visit))

PreOrderTraverse(T->rchild,Visit); }elsereturnOK;}//PreOrderTraverseStatusPrintElement(TElemtypee){

printf(e);returnOK;}先序遍历二叉树的递归算法1StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){if(T){ if(Visit(T->data)) if(PreOrderTraverse(T->lchild,Visit)) if(PreOrderTraverse(T->rchild,Visit))returnOK; returnERROR; }elsereturnOK;}//PreOrderTraverseStatusPrintElement(TElemtypee){

printf(e);returnOK;}先序遍历二叉树的递归算法2－＋/ab－＋/ab－＋ab/－＋a＋b－+/ba三种遍历二叉树的过程－＋/abp中序遍历二叉树T－＋a－＋－b－输出序列：a+b-/－中序遍历二叉树的算法(算法6.3)

StatusInOrderTraverse(BiTree,Status(*Visit)(TElemTypee)){ //中序遍历二叉链表，每个元素调用Visit

InitStack(S);P=T; while(p||!StackEmpty(S)){ if(p){push(S,p);p=p->lchild;}//根结点入栈，遍历左子树 else{ //根结点出栈，访问根结点，遍历右子树 pop(S,p);Visit(p->data); p=p->rchild; }//else }//while returnOK; }//InOrderTraverse课堂练习：二叉树的先序遍历非递归算法－＋/ab－＋a＋b分析：先序遍历二叉树的算法

StatusPreOrderTraverse(BiTree,Status(*Visit)(TElemTypee)){ //先序遍历二叉链表，每个元素调用Visit

InitStack(S);P=T; while(p||St