第六章二叉树和树6.1树的基本概念6.2二叉树6.3二叉树遍历和线索二叉树6.4树和森林6.5*树的等价问题/树的应用6.6霍夫曼树及其应用中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 1 中国科学技术大学 第六章 二叉树和树 6.1树的基本概念 6.2二叉树 6.3二叉树遍历和线索二叉树 6.4树和森林 6.5 *树的等价问题/树的应用 6.6霍夫曼树及其应用
6.1树的基本概念ySCFH例的珠度：树中叫丁结点的取人层人数中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 2 中国科学技术大学 树的定义 （无序树） n(n>=0)个数据元素（结点）的有限集D，若D为空集， 则为空树。否则： 在D中存在唯一的称为根的数据元素 当n>1时，其余结点可分为m（m>0）个互不相交的 有限子集T1，T2，.，Tm，其中每个子集本身又 是一颗树，并称为根的子树 结点间关系: 孩子，双亲，兄弟，堂兄弟，祖先，子 孙 结点的度：子树(孩子)的个数 叶子结点：度为0结点；（终端结点、分支结点） 层次：根的层次为1，层次为k的结点其孩子层次为 k+1 树的深度：树中叶子结点的最大层次数 6.1树的基本概念
ADT Tree数据对象D:D是具有相同特性的数据元素的集合。数据关系：若D为空或一个元素时，R为空集。否则R=(H)，H是如下二元关系：1）在D中存在唯一元素称根root，它在关系H下无前驱：2）若D-{root)Φ,则存在D-{root)的一个划分Di,D2....Dm(m>0),对任意j≠k（1j,k≤m）有D,nDk=d,且对任意i(1≤i≤m),存在唯一元素x,ED,有<root,x>EH;3)对应于D-{root)的一个划分，H-{<root,x>,.,<root,xm>}有唯一的一个划分Hj,H2,...Hm(m>0),对任意j+k（1j,k≤m)有H,nH=d,且对任意i(1≤i<m),H,是Di上的二元关系,(Di,(Hi)）是一个符合本定义的树，称根root的子树。基本操作：3中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 3 中国科学技术大学 ADT Tree{ 数据对象D: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）有Dj∩Dk=ɸ,且对任意i(1 ≤ i ≤ m),存在唯一元素xi∈Di ,有<root,xi>∈H; 3)对应于D-{root}的一个划分，H-{<root,x1>,.,<root,xm>}有唯 一的一个划分H1 ,H2 ,.Hm(m>0),对任意j≠ k（1≤j,k ≤ m） 有Hj∩Hk=ɸ,且对任意i(1 ≤ i ≤m),Hi是Di上的二元关系， （Di,{Hi}）是一个符合本定义的树，称根root的子树。 基本操作：
6Assign(&T,cur e,val):InitTree(&T):Parent(T,cur_e);DestroyTree(&T);FirstChild(T,cur e);CreateTree(&T,definition):RightSibling(T,cur e):ClearTree(&T):InsertChild(&T,p,i,c);TreeEmpty(T);DeleteChild(&T,p,i);TreeDepth(T);TraverseTree(T);Root(T);Value(T,cur_e);//ADT Treeypb@ustc.edu.cn中国科学技术大学
ypb@ustc.edu.cn 4 中国科学技术大学 InitTree(&T); DestroyTree(&T); CreateTree(&T,definition); ClearTree(&T); TreeEmpty(T); TreeDepth(T); Root(T); Value(T,cur_e); }//ADT Tree Assign(&T,cur_e,val); Parent(T,cur_e); FirstChild(T,cur_e); RightSibling(T,cur_e); InsertChild(&T,p,i,c); DeleteChild(&T,p,i); TraverseTree(T);
6.2二叉树6.2.1二叉树定义（binaryTree)一n个元素的有限集，或为空集，或含有唯一的根元素其余元素分成两个互不相交的子集，每个子集本身也是一颗二叉树。分别称为根的左子树、右子树，集合为空的二叉树称空树一二叉树的元素又称结点一左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙一结点的度：非空子树的个数一叶子结点：左右子树均空的结点；度为零一层次：根的层次为1，层次为k的结点其孩子层次为k+1一二叉树的深度：二叉树中叶子结点的最大层次数5中国科学技术大学ypb@ustc.edu.cn
ypb@ustc.edu.cn 5 中国科学技术大学 6.2.1二叉树定义（binary Tree） – n个元素的有限集，或为空集，或含有唯一的根元素， 其余元素分成两个互不相交的子集，每个子集本身也 是一颗二叉树。分别称为根的左子树、右子树，集合 为空的二叉树称空树 – 二叉树的元素又称结点 – 左孩子，右孩子，父亲，兄弟，堂兄弟，祖先，子孙 – 结点的度：非空子树的个数 – 叶子结点：左右子树均空的结点；度为零 – 层次：根的层次为1，层次为k的结点其孩子层次为k+1 – 二叉树的深度：二叉树中叶子结点的最大层次数 6.2二叉树