【教学课件】第6章 树和二叉树.ppt

,第6章 树和二叉树 树是一类重要的非线性数据结构，是以分支关系定义的层次结构 6.1 树的定义 定义：树(tree)是n(n0)个结点的有限集T 其中：有且仅有一个特定的结点，称为树的根(root) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree) 特点： 树中至少有一个结点称为根 树中各子树是互不相交的集合,A,只有一个根结点的树,A为根结点，其余分为三个互不相交的子集 T1=B,E,F,K,L T2=C,G T3=D,H,I,J,M T1,T2,T3都是根结点A的子树，且本身又是一棵树。,根,基本术语 结点(node)：包括一个数据元素及若干指向其子树的分支 结点的度(degree)：结点拥有的子树个数 叶子(leaf)：度为0的结点（或称终端结点） 分支结点（非终端结点）：度不为0的结点 树的度：树内各结点的度的最大值 孩子(child)：结点的子树的根称为该结点的孩子 双亲(parents): (相对孩子)结点的上层结点 兄弟(sibling)：同一双亲的孩子之间互称兄弟 结点的祖先：从根到该结点所经分支上的所有结点 子孙：某结点为根的子树中的任意结点 结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层 深度(depth)：树中结点的最大层次数 森林(forest)：m(m0)棵互不相交的树的集合,ADT Tree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D为空集，则称为空树； 若D仅含一个数据元素，则R为空集，否则RH， H是如下二元关系： (1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2)若Droot，则存在Droot的一个划分 D1，D2，Dm（m0），对任意j k(1j, km) 有Dj Dk = ,且对任意的i(1im)，唯一存在数据元素Xi Di,有root, Xi H; (3) 对应于D-root的划分,H-有唯一的一个划分H1,H2,Hm(m0),对任意jk(1j, km) 有Hj Hk = ,且对任意i(1im)，Hi是 Di上的二元关系，（Di,Hi）是一棵符合本定义的树，称为根root的子树。,基本操作P： InitTree ( ADT Tree,6.2 二叉树 一、定义 二叉树是n(n0)个结点的有限集，它或为空树(n=0)，或由一个根结点和两棵分别称为左子树和右子树的互不相交的二叉树构成 特点 每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒 基本形态,A,ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R： 若D，则R，称BinaryTree为空二叉树； 若D，则RH，H是如下二元关系； (1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； (2) 若D-root,则存在D-rootDl,Dr,且DlDr ； (3) 若Dl ，则Dl中存在唯一的元素Xl,H，且存在Dl上的关系HlH；若Dr，则Dr中存在唯一的元素Xr，H , 且存在Dr上的关系HrH； H,， Hl, Hr ; (4) (Dl, Hl)是一棵符合本定义的二叉树,称为根的左子树 (Dr,Hr)是一棵符合本定义的二叉树,称为根的右子树,基本操作P： InitBiTree ( ADT BinaryTree,二、二叉树的性质,性质1：在二叉树的第i层上至多有2i-1个结点(i1),证明：用归纳法证明 i=1时,只有一个根结点, 2i-1= 20=1 是对的 假设对所有j(1j<i)命题成立，即第j层上至多有 2j-1 个结点 那么，第i-1层至多有2i-2 个结点 又二叉树每个结点的度至多为2 第i层上最大结点数是第i-1层的2倍，即2x2i-2= 2i-1 故命题得证,性质2：深度为k的二叉树至多有2k -1个结点(k1),证明：由性质1知深度为k 的二叉树最大结点数为 k k (第i层上的最大结点数)= 2i-1= 2k 1 i=1 i=1,性质3：对任何一棵二叉树T，如果其终端结点数为n0，度 为2的结点数为n2，则 n0=n2+1,证明：设n1为二叉树T中度为1的结点数 因为：二叉树中所有结点的度均小于或等于2 所以：其结点总数n=n0+n1+n2 又二叉树中，除根结点外，其余结点都只有一个 分支进入 设B为分支总数，则n=B+1 又：分支由度为1和度为2的结点射出，B=n1+2n2 于是，n=B+1=n1+2n2+1=n0+n1+n2 n0=n2+1,两种特殊形式的二叉树,满二叉树,定义：一棵深度为k且有2k-1个结点的二叉树称为满二叉树,特点：每一层上的结点数都是最大结点数,两种特殊形式的二叉树,完全二叉树,定义：深度为k，有n个结点的二叉树当且仅当其每一个结 点都与深度为k的满二叉树中编号从1至n的结点一一 对应时，称为完全二叉树,特点：叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为l，则其左分支下子孙的最大层次必为l 或l+1,性质4：具有n个结点的完全二叉树的深度为log2n +1,证明：设深度为k，根据性质2和完全二叉树的定义有 2k-1 -1 < n 2k-1,或 2k-1 n < 2k,于是 k-1 log2n < k,因为 k是整数 所以 k= log2n +1,性质5：如果对一棵有n个结点的完全二叉树的结点按层序 编号，则对任一结点i(1in)，有： (1) 如果i=1，则结点i是二叉树的根，无双亲；如果i1， 则其双亲是i/2 (2) 如果2in，则结点i无左孩子；如果2in，则其左孩子是2i (3) 如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,三、二叉树的存储结构,1、顺序存储结构 二叉树的顺序存储表示 #define MAX_TREE_SIZE 100 typedef TElemType SqBiTree MAX_TREE_SIZE ; SqBiTree bt ;,顺序存储结构的特点： 结点间关系蕴含在其存储位置中 浪费空间，适于存满二叉树和完全二叉树,2、链式存储结构,二叉树的二叉链表存储表示 typedef struct BiTNode TElemType data; struct BiTNode * lchild , * rchild ; BiTNode , * BiTree ;,特点： 指针直接表示关系，操作简单 增加指针域，浪费空间，特别是存在多个空指针域,6.3 遍历二叉树和线索二叉树 一、遍历二叉树 遍历二叉树(Traversing Binary Tree):按某条搜索路径巡访树的每个结点，且使每个顶点仅被访问一次，从而得到树中所有结点的一个线性排列。,由二叉树的递归定义可知： 二叉树是由三个基本单元组成： 根结点、左子树、右子树,则可得到六种遍历方案： DLR、LDR、LRD、DRL、RDL、RLD,先序遍历(DLR)：先访问根结点,然后分别先序遍历左子树、 右子树 中序遍历(LDR)：先中序遍历左子树，然后访问根结点，最 后中序遍历右子树 后序遍历(LRD)：先后序遍历左、右子树，然后访问根结点,先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点 （2）先序遍历左子树 （3）先序遍历右子树,中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）中序遍历左子树 （2）访问根结点 （3）中序遍历右子树,后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）后序遍历左子树 （2）后序遍历右子树 （3）访问根结点,例：,先序序列：,A,B,D,F,E,G,C,中序序列：,D,B,F,G,E,A,C,后序序列：,D,F,G,B,E,C,A,先序遍历二叉树的递归算法 Status PreOrderTraverse ( BiTree T , Status(* Visit)(TElemType e) ) if（T） if ( Visit ( T-data ) ) if ( PreOrderTraverse ( T-lchild , Visit ) ) if ( PreOrderTraverse ( T-rchild , Visit ) ) return OK ; return ERROR ; else return OK ; ,Status PreOrderTraverse ( BiTree T ) if（T） Visit ( T-data ) ; PreOrderTraverse ( T-lchild ) ; PreOrderTraverse ( T-rchild ) ; ,中序遍历算法 Status InOrderTraverse ( BiTree T ) if（T） InOrderTraverse ( T-lchild ) ; Visit ( T-data ) ; InOrderTraverse ( T-rchild ) ; ,后序遍历算法 Status PostOrderTraverse ( BiTree T ) if（T） PostOrderTraverse ( T-lchild ) ; PostOrderTraverse ( T-rchild ) ; Visit ( T-data ) ; ,遍历过程演示：,先序序列：- * a b c,遍历过程演示：,先序序列：- * a b c,中序序列：a * b - c,遍历过程演示：,先序序列：- * a b c,中序序列：a * b - c,中序序列：a b * c -,中序遍历的非递归算法 Status InOrderTraverse ( BiTree T , Status(* Visit)(TElemType e) ) InitStack ( S ) ; Push ( S , T ) ; while ( ! StackEmpty ( S ) ) while ( GetTop ( S , p ) ,中序遍历的非递归算法 Status InOrderTraverse ( BiTree T , Status(* Visit)(TElemType e) ) InitStack ( S ) ; p = T ; while ( p | ! StackEmpty ( S ) ) if ( p ) Push ( S , p ) ; p = p - lchild ; else Pop ( S , p ) ; if ( ! Visit ( p-data ) ) return ERROR ; p = p - rchild ; return OK; ,按先序次序输入二叉树中结点的值（一个字符），空字符表示空树，构造二叉链表表示的二叉树T Status CreateBiTree ( BiTree ,6.4 树与森林 一、树的存储结构 1、双亲表示法 用结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点: 找双亲容易，找孩子难,0 1 2 3 4 5 6 7 8,data parent,树的双亲表示 #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data ; int parent ; PTNode ; typedef struct PTNode nodes MAX_TREE_SIZE ; int n ; PTree ;,例：求结点ti的长子 Int FirstChild ( Ptree t , int i ) for ( j= i+1 ; j < t.n ; j+ ) if ( t.nodesj.parent = i ) return ( j ) ; return (-1) ; ,2、孩子表示法 多重链表：每个结点有多个指针域，分别指向其子树 的根 结点同构：结点的指针个数相等，为树的度d,浪费空间,操作不便,孩子链表表示：,0 1 2 3 4 5 6 7 8,data firstchild,如何找双亲结点,孩子链表表示：,0 1 2 3 4 5 6 7 8,data parent firstchild,树的孩子链表存储表示 typedef struct CTNode int child; struct CTNode * next ; * ChildPtr ; typedef struct TElemType data ; Childptr firstchild ; CTBox; typedef struct CTBox nodes MAX_TREE_SIZE ; int n, r; /结点数和根的位置 CTree ;,3、孩子兄弟表示法： -二叉链表表示法 用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点 typedef struct CSNode ElemType data; struct CSNode * firstchild , * nextsibling ; CSNode , *CSTree ;,例：,二、森林与二叉树的转换 借助于二叉链表存储结构实现树与二叉树的转换,加线：在兄弟之间加一连线 删线：对每个结点，除了其长子孩子外，去除其与其余 孩子之间的关系 旋转：以树的根结点为轴心，将整树顺时针旋转,树转换成的二叉树其右子树一定为空,将树转换成二叉树,从树与二叉树的转换可知：任何一棵和树对应的二叉树，其右子树必为空，若把森林中第二棵树的根结点看成是第一棵树根结点的兄弟，则可导出森林和二叉树的对应关系。,森林转换成二叉树 如果F T1，T2，Tm是森林，则可按如下规则转换成一棵二叉树B（ root , LB , RB ）。 （1）若F为空，即m0，则B为空树 （2）若F非空，即m0，则B的根root即为森林中第一棵树的根ROOT（T1）；B的左子树LB是从T1中根结点的子树森林F1T11，T12，T1m1转换而成的二叉树；其右子树RB是从森林F=T2，T3，Tm转换而成的二叉树。,二叉树转换成森林 如果B（ root , LB , RB ）是一棵二叉树，则可按如下规则转换成森林FT1，T2，Tm； （1）若B为空，则F为空； （2）若B非空，则F中第一棵树T1的根ROOT（T1）即为二叉树B的根root；T1中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F=T2，T3，Tm是由B的右子树RB转换而成的森林。,将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,森林转换成二叉树,三、树和森林的遍历,1)先根遍历,2)后根遍历,三、树和森林的遍历,先根（序）遍历 若T非空，则： 1、访问根结点R 2、依次先序遍历根的各子树,先根序列：,A,B,D,G,E,H,I,C,F,三、树和森林的遍历,后根（序）遍历 若T非空，则： 1、依次后序遍历根的各子树 2、访问根结点R,先根序列：,A,B,D,G,E,H,I,C,F,后根序列：,D,G,H,E,I,B,F,C,A,先根序列：,A,B,D,G,E,H,I,C,F,后根序列：,D,G,H,E,I,B,F,C,A,先序序列：,A,B,D,G,E,H,I,C,F,中序序列：,D,G,H,E,I,B,F,C,A,后序序列：,I,H,G,D,E,F,C,B,A,按照森林和树的相互递归定义，可推出森林的两种遍历方法,1)先序遍历森林 若森林非空，则 访问森林中第一棵树的根结点 先序遍历第一棵树中根结点的子树森林 先序遍历除去第一棵树之后剩余的树构成的森林,先序序列,A,B,C,E,D,F,G,H,I,J,按照森林和树的相互递归定义，可推出森林的两种遍历方法,2)中序遍历森林 若森林非空，则 中序遍历森林中第一棵树的根结点的子树森林 访问第一棵树的根结点 中序遍历除去第一棵树之后剩余的树构成的森林,先序序列,A,B,C,E,D,F,G,H,I,J,中序序列,B,C,D,F,A,E,H,J,I,G,先序序列,A,B,C,E,D,F,G,H,I,J,中序序列,B,C,D,F,A,E,H,J,I,G,先序序列,A,B,C,E,D,F,G,H,I,J,中序序列,B,C,D,F,A,E,H,J,I,G,后序序列,D,C,B,J,F,I,H,G,E,A,