资源描述：
《数据结构--树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第六章树和二叉树6.1树的类型定义和基本术语6.2二叉树的类型定义及性质6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码6.1树的类型定义和基本术语树的定义定义：树(Tree)是n(n≥0)个结点的有限集T，其中：当n≥1时，有且仅有一个特定的结点，称为树的根(Root)，当n1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,……Tm，其中每一个集合本身又是一棵树，称为根的子树(SubTree)。特点：树中各子树是互不相交的集合。树是一类重要的非线性数据结构，是以分支关系定义的层次结构。A只有根结点的树ABCDEFG
2、HIJKLM有子树的树根子树ABCDEFGHIJMKLA()T1T3T2树根B(E,F(K,L)),C(G),D(H,I,J(M))数据对象D：D是具有相同特性的数据元素的集合。(1)在D中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵树,称为根root的子树。数据关系R：ADTTree{若D为空集，则称为空树；否则:}ADTTree基本操作P：基本操作：查找类插入类删除类Root(T)//求树的根结点查找类：Value(T,cur_e)//求当前结点的元素值Parent(T,
3、cur_e)//求当前结点的双亲结点LeftChild(T,cur_e)//求当前结点的最左孩子RightSibling(T,cur_e)//求当前结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历树中结点的最大层次InitTree(&T)//初始化构造空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,cur_e,value)//给当前结点赋值InsertChild(&T,&p,i,c)//将以c为根的树插入为结点p的第i棵子树Cle
4、arTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树结构DeleteChild(&T,&p,i)//删除T中结点p的第i棵子树树的四种表示法：一、树形表示法二、凹入表示法三、嵌套集合表示法四、广义表表示法一、树形表示法二、凹入表示法三、嵌套集合表示法四、广义表表示法ABCDFEGHIJMKLABEKLFCGDHMIJGFKLIJMHABDCE(A(B(E(K,L),F),C(G),D(H(M),I,J)))(树根(子树1，子树2，…，子树n))一、树形表示法二、凹入表示法三、嵌套集合表示法四、广义表表示法ABCDFEGHJMKLABEKGLCFDH
5、MJ(A(B(E(K,G,L),C,F),D(H(M),J)))FKLJMHABDEGC练习基本术语结点:结点的度:树的度:叶子结点:分支结点:一个数据元素+若干指向子树的分支。分支的个数。(结点拥有子树数目)树中所有结点的度的最大值。度为零的结点。度大于零的结点。DHIJM（终端结点）（非终端结点）(从根到结点的)路径：结点的层次:树的深度：由从根到该结点所经分支和结点构成。ABCDEFGHIJMKL定义根结点的层次为1,第t层结点子树的根结点的层次为t+1。树中叶子结点所在的最大层次。孩子结点：某结点子树的根结点称为该结点的孩子结点。双亲结点：孩子结点的上层结点叫该结点的
6、双亲结点。兄弟结点：同一双亲的孩子结点。祖先结点：从根结点到该结点所经分支上的所有结点。子孙结点：以某结点为根的子树中的任一结点称为此结点~。任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林。森林：是m（m≥0）棵互不相交的树的集合。ArootBEFKLCGDHIJMF子树之间不存在确定的次序关系（能互换）。子树之间存在确定的次序关系（不能互换）。有序树：(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：无序树：DHIJMDIHJM=双亲在同一层的结点ABCDEFGHIJKLM结点A的度：结点B的度：结点M的度：叶子：
7、结点A的孩子：结点B的孩子：结点I的双亲：结点L的双亲：结点B，C，D为兄弟结点K，L为兄弟树的度：结点A的层次：结点M的层次：树的深度：结点F，G为堂兄弟结点A是结点F，G的祖先结点B的子孙：320B，C，DE，F3K，L，F，G，M，I，JDE14例E，K，L，F4对比树形结构和线性结构的结构特点~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~线性结构树形结构第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据
