树的性质 性质1n个结点，每个结点度d,则：n=∑d,+1 性质2：度为k的树第层的结点个数最多k() ·性质3：深度为h的k叉树，最多结点数为 k-1 k-1 ·性质4：具有n个结点的k叉树深度最小为 1ogk(n(k-1)+1)] ypb@ustc.edu.cn 6 中国科学技术大学
ypb@ustc.edu.cn 6 中国科学技术大学 树的性质 • 性质1:n个结点，每个结点度di ,则： • 性质2:度为k的树第i层的结点个数最多 k (i-1) • 性质3:深度为h的k叉树，最多结点数为 • 性质4:具有n个结点的k叉树深度最小为 • 1 1 = + = n i n di 1 1 − − k k h logk (n(k −1) +1)
5.2二叉树(binary Tree) 二叉树的定义和基本术语 是n(n≥0)个元素的有限集，或为空集(n=0),或含有唯 一的根元素，其余元素分成两个互不相交的子集，每 个子集本身也是一颗二叉树。分别称为根的左子树、 右子树。 -空树集合为空的二叉树 一结点的度：非空子树的个数 一左孩子，右孩子 -叶子结点：左右子树均空的结点；度为零 二叉树的深度：二叉树中叶子结点的最大层次数 ypb@ustc.edu.cn 中国科学技术大学
ypb@ustc.edu.cn 7 中国科学技术大学 ➢ 二叉树的定义和基本术语 – 是n(n0)个元素的有限集，或为空集(n=0) ，或含有唯 一的根元素，其余元素分成两个互不相交的子集，每 个子集本身也是一颗二叉树。分别称为根的左子树、 右子树。 – 空树:集合为空的二叉树 – 结点的度：非空子树的个数 – 左孩子，右孩子 – 叶子结点：左右子树均空的结点；度为零 – 二叉树的深度：二叉树中叶子结点的最大层次数 5.2二叉树（binary Tree）
满二叉树(full binary tree):所有分支结点度为2， 叶子结点在同一层次 -完全二叉树(complete binary tree):深度h,h-l为 满二叉树，h层的结点都集中在左侧 o品o品品品o品%。 (a)满二又树 (b)完全二叉树 ypb@ustc.edu.cn 8 中国科学技术大学
ypb@ustc.edu.cn 8 中国科学技术大学 – 满二叉树（full binary tree）：所有分支结点度为2， 叶子结点在同一层次 – 完全二叉树（complete binary tree）：深度h，h-1为 满二叉树，h层的结点都集中在左侧
二叉树ADT描述 ADT BinaryTreef 数据对象D:D是同类型数据元素的集合。 数据关系R:若D=O,则称BinaryTree:为空二叉树； 否则R是满足下列条件的二元关系： (1)在D中存在唯一的称为根的元素root,它在R下无直接前驱； (2)若D-{root}=☑，则R=O;否则存在D-{root}={DI,Dr}, 且DInDr=-O; (3)若Dl≠O,则DI中存在唯一的元素xl,<root,x>∈R,且存在 DI上的关系RlcR;若Dr≠☑，则Dr中存在唯一的元素xr, <rOot,Xr>∈R,且存在Dr上的关系RrCR;R={<root,X>, <root,xr>,Rl,Rr}i (4)D1,)是一棵符合本定义的二叉树，称为根的左子树； (Dr,R)是一棵符合本定义的二叉树，称为根的右子树。 ypb@ustc.edu.cn 9 中国科学技术大学
ypb@ustc.edu.cn 9 中国科学技术大学 二叉树ADT描述 ADT BinaryTree{ 数据对象D：D是同类型数据元素的集合。 数据关系R：若D=，则称BinaryTree为空二叉树； 否则R是满足下列条件的二元关系： (1)在D中存在唯一的称为根的元素root，它在R下无直接前驱； (2)若D-{root}=，则R=；否则存在D-{root}={Dl，Dr}， 且Dl∩Dr=； (3)若Dl≠，则Dl中存在唯一的元素xl，<root,xl>∈R，且存在 Dl上的关系RlR；若Dr≠，则Dr中存在唯一的元素xr， <root,xr>∈R，且存在Dr上的关系RrR；R={<root,xl>， <root,xr>，Rl，Rr}； (4)(Dl，Rl)是一棵符合本定义的二叉树，称为根的左子树； (Dr，Rr)是一棵符合本定义的二叉树，称为根的右子树
S 基本操作P: .InitBiTree(&T) .RightChild(T,e) .DestroyBiTree(&T) .LeftSibling(T,e) .CreateBiTree(&T,definition) RightSibling(T,e) .BiTreeEmpty(T) .InsertChild(&T,p,LR,C) .BiTreeDepth(T) DeleteChild(&T,p,LR) .Parent(T,e) .Traverse(T) .LeftChild(T,e) }//End ADT BinaryTree ypb@ustc.edu.cn 10 中国科学技术大学
ypb@ustc.edu.cn 10 中国科学技术大学 •InitBiTree(&T) •DestroyBiTree(&T) •CreateBiTree(&T,definition) •BiTreeEmpty(T) •BiTreeDepth(T) •Parent(T,e) •LeftChild(T,e) •RightChild(T,e) •LeftSibling(T,e) •RightSibling(T,e) •InsertChild(&T,p,LR,C) •DeleteChild(&T,p,LR) •Traverse(T) 基本操作P： ｝//End ADT BinaryTree