《数据结构--树》由会员分享，可在线阅读，更多相关《数据结构--树（45页珍藏版）》请在金锄头文库上搜索。
1、3.1 基本术语 3.2 二元树 3.3 树 3.4 森林与二元树间的转换 3.5 树的应用,第三章 树（Tree）,线性表元素之间的线性关系 树元素之间的层次关系,3.1 基本术语,定义一,1、一个结点x组成的集x是一株树，这个结点x也是这株树的根。 2、假设x是一个结点，T1，T2，Tk是k株互不相交的树，我们可以构造一株新树：令x为根，并有k条边由x指向树T1，T2，Tk。这些边也叫做分支，T1，T2，Tk称作根x的树之子树（SubTree）。,树是n（0）个结点的有限集。在任意一棵非空树中：1、有且仅有特定的称为根（Root）的结点；2、当n1时，其余结点可分为m（0）个互不相交的有限
2、集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树（ SubTree ）。,定义二,3.1 基本术语,定义 三,T = （ D，R ） 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）有DjDk=，且对任意的 i（1 i m），唯一存在数据元素 x i Di，有 H; 3、对应
3、于 D - root 的划分，H - , ,有唯一的一个划分H1，H2，Hm（m0）,对任意jk（1j，km）有HjHk,且对任意的i（1 i m），Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根root的子树。,3.1 基本术语,常用术语：,分支 路长,父亲 双亲 儿子 兄弟 子孙 祖先,层 结点的高 树的高（深度）,有序树 & 无序树,3.1 基本术语,森林forest：是 n 0 株互不相交的树的集合。,3.2 二元树( binary tree ),定义一 二元树是有限个结点的集合，这个集合或者是空集， 或者是由一个根结点和两株互不相交的二元树组成，其中一 株叫根的做
4、左子树，另一棵叫做根的右子树。,3.2.1 二元树的定义和基本性质,3.2.1 二元树的定义和基本性质,定义二 Binary Tree = ( D , R ) D：指数据对象，是由相同类型的数据元素组成的集合。 R：为数据元素间的关系：若D，则R= ，称Binary tree 为空树；若D；则R=H，H是如下二元关系： 在D中存在唯一的称为根的数据元素 root，它在关系H下无前驱； 若D- root ，则存在D-root=Dl，Dr，且DlDr=； 若Dl ，则Dl中存在唯一的元素xl，H，且存在Dl上的关系HlH；若Dr ，则Dr中存在唯一的元素xr，H，且存在Dr上的关系HrH；H=，
5、，Hl，Hr； （Dl，Hl）是符合本定义的二元树，称为根的左子树；（Dr，Hr）是符合本定义的二元树，称为根的右子树；,3.2.1 二元树的定义和基本性质,二元树的性质：,性质1：在二元树中第 i 层的结点数最多为2i-1（i 1）。,性质2：高度为k的二元树其结点总数最多为2k1（ k 1）,性质3：对任意的非空二元树 T ，如果叶结点的个数为 n0，而其度为 2 的结点数为 n2，则：n0 = n2 + 1,定义 深度为k且有2k 1个结点的二元树称为满二元树。,层序编号：对满二元树的结点进行连续编号。从根结点开始，从上而下，自左至右。,定义 深度为 k 的，由n个结点的二元树，当且仅当
6、其每个结点都与深度为 k 的满二元树中编号从 1 至 n 的结点一一对应，称之为完全二元树。,3.2.1 二元树的定义和基本性质,二元树的性质(续)：,3.2.1 二元树的定义和基本性质,二元树的遍历,遍历：根据原则，按照一定的顺序访问二元树中的每一个结点，使每个结点只能被访问一次。,根（D）、左孩子（L）和右孩子（R）三个结点可能出现 的顺序有： DLR DRL LDR LRD RLD RDL,原则：左孩子结点一定要在右孩子结点之前访问。,要讨论的三种操作分别为：,先根顺序DLR， 中根顺序LDR， 后根顺序LRD,二元树的遍历,先根顺序遍历二元树：若二元树非空则： 访问根结点；先根顺序遍历
7、左子树；先根顺序遍历右子树； ；,中根顺序遍历二元树：若二元树非空则： 中根顺序遍历左子树；访问根结点；中根顺序遍历右子树； ；,后根顺序遍历二元树：若二元树非空则： 后根顺序遍历左子树；后根顺序遍历右子树；访问根结点； ；,3.2.2 抽象数据型二元树,操作：, EMPTY ( BT ) ; ISEMPTY ( BT ) ; CREATEBT ( V, LT , RT ) ; LCHILD ( BT ) ; RCHILD ( BT ) ; DATA ( BT ) ;,例1-1：写一个递归函数，按先根顺序列出二元树中每个结点的DATA域之值。,Void PREORDER ( BT ) BTRE
8、E BT ; if ( ! ISEMPTY ( BT ) ) visit ( DATA ( BT ) ) ;PREORDER ( LCHILD ( BT ) ) ;PREORDER ( RCHILD ( BT ) ) ; ,例1-2：写一个递归函数，按中根顺序列出二元树中每个结点的DATA域之值。,Void INORDER ( BT ) BTREE BT ; if ( ! ISEMPTY ( BT ) ) INORDER ( LCHILD ( BT ) ) ;visit ( DATA ( BT ) ) ;INORDER ( RCHILD ( BT ) ) ; ,例1-3：写一个递归函数，按后根
9、顺序列出二元树中每个结点的DATA域之值。,Void POSTORDER ( BT ) BTREE BT ; if ( ! ISEMPTY ( BT ) ) POSTORDER ( LCHILD ( BT ) ) ;POSTORDER ( RCHILD ( BT ) ) ;visit ( DATA ( BT ) ) ; ,例,二元树的遍历的非递归过程,先序： A B D J H E C F I G K L M 中序： J DH B E A F I C G L K M 后序： J H D E B I F L M K G C A,Void INORDER ( BT ) BTREE BT ; if
10、( ! ISEMPTY ( BT ) ) INORDER ( LCHILD ( BT ) ) ;visit ( DATA ( BT ) ) ;INORDER ( RCHILD ( BT ) ) ; ,算法: Loop: if (BT 非空) 进栈;左一步;else 退栈;右一步; ;,数据结构:设栈S:用以保留当前结点;,二元树的遍历的 非递归过程,Void NINORDER( BT ) BTREE BT; STACK S ; BTREE T ;MAKENULL( S ) ;T = BT ;while ( !ISEMPTY( T ) | EMPTY ( S ) )if ( !ISEMPTY (
11、 T ) ) PUSH( T ,S );T = T LCHILD ( T ) ; else T = TOP ( S ) ; POP ( S ) ;visit( DATA( T ) ) ; T = T RCHILD ( T ) ; ,进栈; 左走一步,退栈; 右走一步,3.2.3 二元树的表示,1、顺序存储a、完全（或满）二元树,根据性质5，如已知某结点的层序编号i,则可求得该结点的 双亲结点、左孩子结点和右孩子结点。,采用一维数组，按层序顺序依次存储二元树 的每一个结点。如下图所示：,b、一般二元树,根据性质5，如已知某结点的层序编号i,则可求得该结点的 双亲结点、左孩子结点和右孩子结点，然后
12、检测其值是否 为虚设的特殊结点$。,通过虚设部分结点，使其变成相应的完全二元树。,Struct node Struct node *lchild ;Struct node *rchild ;datatype data ; ; Typedef struct node * BTREE ;,2、二元树的左右链表示,例: ( P102 ) BTREE CREATEBT(v , ltree , rtree ) datatype v ; BTREE ltree , rtree ; BTREE root ;root = new node ;root data = v ; root lchild = ltre
13、e ; root rchild = rtree ;return root ; ,2、二元树的左右链表示,证明：n 个结点的二元树中，共有 n+1 个空链接域。,证：设其空链域数为 x分支数 B入 = n 1B出=2 n x B入 = B出 n 1 = 2n x 得出 x = n 1,结点总数：13 空链域的个数：14,例: 按先序序列建立二元树的左右链结构. 如由图所示二元树,输入:ABDH#I#E#CF#J#G# 其中:#表示空,Status CreateBtree( BTREE ,线索二元树,问题的提出：,1、在n个结点的二元树左右链表示中，有n+1个空链域。如何利用n+1个空链域，使二元
14、树的操作更加方便。 2、在二元树左右链表示中，为求某个结点的（中序）前驱 $P 或（中序）后继 p$，每次都要从树根开始进行查找，很不方便。,定义：,若结点p有左孩子，则p-lchild指向其左孩子结点， 否则令其指向其（中序）前驱。 若结点p有右孩子，则p-rchild指向其右孩子结点， 否则令其指向其（中序）后继。,结点类型 Node,Struct LNode Elementtype data ; Struct LNode *lchild , *rchild ;int lchild , rchild ; ,讨论：为方便操作利用了 n+1 个结点，但为实现操作却多用了 2n 个标志位。,Ty
15、pdef Struct LNode * THTREE;,THTREE INNEXT( THTREE p) THTREE p ; THTREE Q ;Q=p-rchild ;if (p-rtag = = 1 )while(Q-ltag = = 1)Q = Q-lchild ;return ( Q ) ; ,例一：求p$（中序后继）：,分析：(1) 当p-rtag = 0时，p-rchild 既为所求（线索）。(2) 当p-rtag = 1时，p$为p的右子树的最左结点。,THTREE INPRE( THTREE p) THTREE p ; THTREE Q ;Q=p-lchild ;if (p-ltag = = 1 )while(Q-rtag = = 1)Q = Q-rchild ;return ( Q ) ; ,
