数据结构-树(1)-严蔚敏版

数据结构-树(1)-严蔚敏版

第五章 树树是一类重要的非线性数据结构，是以分支关 系定义的层次结构

§5.1 树的定义定义定义：树(tree)是n(n>0)个结点的有限集T,其中：有且仅有一个特定的结点，称为树的根(root) 当n>1时，其余结点可分为m(m>0)个互不相交的有限集 T1,T2,……Tm,其中每一个集合本身又是一棵树，称为根的 子树(subtree)

特点：树中至少有一个结点——根 树中各子树是互不相交的集合

数据结构-树(1)-严蔚敏版

只有根结点的树

A

有子树的树

A C F G H M

根

B E K L

D I J

子树

数据结构-树(1)-严蔚敏版

基本术语结点(node)——表示树中的元素，包括数据项及若干 指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 (sibling)—— 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层， 它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m≥0)棵互不相交的树的集合

数据结构-树(1)-严蔚敏版

结点A的度：3 结点B的度：2 结点M的度：0 结点A的孩子：B,C,D 结点B的孩子：E,F 树的度：3 E K 结点A的层次：1 结点M的层次：4 L B F A C G H M

叶子：K,L,F,G,M,I,J 结点I的双亲：D 结点L的双亲：E 结点B,C,D为兄弟 结点K,L为兄弟 J 树的深度：4

D I

结点F,G为堂兄弟 结点A是结点F,G的祖先

数据结构-树(1)-严蔚敏版

§5.2 二叉树定义定义：二叉树是n(n≥0)个结点的有限集，它或为空树 (n=0),或由一个根结点和两棵分别称为左子树和右子 树的互不相交的二叉树构成 特点每个结点至多有二棵子树(即不存在度大于2的结点) 二叉树的子树有左、右之分，且其次序不能任意颠倒

基本形态

Φ

A B

A

A B

A

B 左子树为空

C 左、右子树 均非空

空二叉树

只有根结点 的二叉树

右子树为空

数据结构-树(1)-严蔚敏版

二叉树性质在二叉树的第i层上至多有2 i 1 个结点(i ≥ 1) 性质1:证明：用归纳法证明之 i=1时，只有一个根结点，i 1 = 2 0 = 1 是对的 2 假设对所有j(1≤j<i)命题成立，即第j层上至多有 2 j 1个结点 那么，第i-1层至多有 2 i 2 个结点 又二叉树每个结点的度至多为2 ∴ 第i层上最大结点数是第i-1层的2倍，即 2 2 i 2 = 2 i 1 故命题得证

性质2:深度为k的二叉树至多有2 k 1 个结点(k≥1)证明：由性质1,可得深度为k 的二叉树最大结点数是

(第i层的最大结点数 ) = ∑ 2 i 1 = 2 k 1 ∑i =1 i =1

k

k

数据结构-树(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

数据结构-树(1)-严蔚敏版

几种特殊形式的二叉树满二叉树定义： 一棵深度为 k且有2 k

1个结点的二叉树称为 ~

特点：每一层上的结点数都是最大结点数

完全二叉树定义：深度为k,有n个结点的二叉树当且仅当其每一个结点 都与深度为k的满二叉树中编号从1至n的结点一一对应时， 称为~ 特点 叶子结点只可能在层次最大的两层上出现 对任一结点，若其右分支下子孙的最大层次为l,则其左 分支下子孙的最大层次必为l 或l+1 性质 性质4: 具有n个结点的完全二叉树的深度为 log n + 12

数据结构-树(1)-严蔚敏版

1 2 4 8 9 10 5 11 12 6 13 14 3 7 15 4 6 2

1 3 5 7

1 2 4 8 9 10 5 11 12 6 3 7 4 2 5 1 3 6

数据结构-树(1)-严蔚敏版

性质5:如果对一棵有n个结点的完全二叉树的结点按层序编号， 则对任一结点i(1≤i≤n),有： (1) 如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其 双亲是 i/2 (2) 如果2i>n,则结点i无左孩子；如果2i≤n,则其左孩子是2i (3) 如果2i+1>n,则结点i无右孩子；如果2i+1≤n,则其右孩子 是2i+1

数据结构-树(1)-严蔚敏版

§5.3 树的存储结构树的存储结构双亲表示法实现：定义结构数组存放树的结点，每个结点含两个域： 数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置 特点：找双亲容易，找孩子难

typedef struct node { datatype data; int parent; }JD; JD t[M];

数据结构-树(1)-严蔚敏版

a data b d g e h i c f 0 1 2 3 4 5 6 7 8 如何找孩子结点 9 0 a b c d e f g h i parent 9 0 1 1 2 2 3 5 5 5

0号单元不用或 存结点个数

数据结构-树(1)-严蔚敏版

孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根 结点同构：结点的指针个数相等，为树的度D 结点不同构：结点指针个数不等，为该结点的度d data child1 child2 ………. childD data degree child1 child2 ………. childd 孩子链表：每个结点的孩子结点用单链表存储，再用含n个 元素的结构数组指向每个孩子链表 孩子结点：typedef struc …… 此处隐藏：1215字，全部文档内容请下载后查看。喜欢就下载吧 ……