树的性质·性质l:n个结点，每个结点度d,则：n=d,+1i=l·性质2:度为k的树第i层的结点个数最多k(i-1)kh -1性质3：深度为h的k叉树，最多结点数为k-1性质4:具有n个结点的k叉树深度最小为logk(n(k -1)+1)6中国科学技术大学ypb@ustc.edu.cn
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）
满二叉树（fullbinarytree）：所有分支结点度为2，叶子结点在同一层次一完全二叉树（completebinarytree）：深度h，h-1为满二叉树，h层的结点都集中在左侧9101112138X1415101112(a）满二叉树(b）完全二叉树8中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 8 中国科学技术大学 – 满二叉树（full binary tree）：所有分支结点度为2， 叶子结点在同一层次 – 完全二叉树（complete binary tree）：深度h，h-1为 满二叉树，h层的结点都集中在左侧
二叉树ADT描述ADT BinaryTree:数据对象D：D是同类型数据元素的集合。数据关系R：若D=①，则称BinaryTree为空二叉树：否则R是满足下列条件的二元关系：(1)在D中存在唯一的称为根的元素root，它在R下无直接前驱；(2)若D-{root)=①，则R=① ;否则存在D-{(root)={Dl ,Dr) 且DInDr=O ;(3)若DI+①，则DI中存在唯一的元素xl，<root,xl>ER，且存在DI上的关系RlcR；若Dr+①，则Dr中存在唯一的元素xr，<root,xr>ER，且存在Dr上的关系RrcR ；R=[<root,xl>,<root,xr>,Rl ,Rr} ;(4)(DI，RI)是一棵符合本定义的二叉树，称为根的左子树;(Dr，Rr)是一棵符合本定义的二叉树，称为根的右子树。9中国科学技术大学ypb@ustc.edu.cn
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)是一棵符合本定义的二叉树，称为根的右子树
基本操作P：·RightChild(T,e)·InitBiTree(&T).LeftSibling(T,e)·DestroyBiTree(&T)·RightSibling(T,e)·CreateBiTree(&T,definition)·BiTreeEmpty(T).InsertChild(&T,p,LR,C)·BiTreeDepth(T).DeleteChild(&T,p,LR)·Traverse(T)·Parent(T,e)·LeftChild(T,e) //EndADT BinaryTree10中国科学技术大学ypb@ustc.edu.cn
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