第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码1数据结构第六章树和二叉树2024年12月23日第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码2ABCDEFGHIJKLM树第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码36.1树的类型定义数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D为空集，则称为空树；否则:（1）在D中存在唯一的称为根的数据元素root,（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。基本操作：查找：Root(T);Value(T,cur_e);Parent(T,cur_e);LeftChild(T,cur_e);TreeEmpty(T);TreeDepth(T);TraverseTree(T,Visit());第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码46.1树的类型定义插入：InitTree(&T);CreateTree(&T,definition);Assign(T,cur_e,value);InsertChild(&T,&p,i,c);删除：ClearTree(&T);DestroyTree(&T);DeleteChild(&T,&p,i);DestroyTree(&T);第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码56.1树的类型定义和线性结构的比较线性结构树结构第一个数据元素(无前驱)；根结点(无前驱)；最后一个数据元素(无后继)；多个叶子结点(无后继)；其它数据元素树中其它结点(一个前驱、一个后继)。(一个前驱、多个后继)。第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码6ABCDEFGHIJKLM树形表示A(B(E(K,L),F),C(G),D(H(M),I,J))嵌套括号表示法树的表示方法：IJFKLGMCCDBEA文氏图凹入表ABFEKLCDHIGMJ第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈夫曼树与哈夫曼编码7基本术语结点:数据元素+若干指向子树的分支。结点的度:分支的个数。树的度:树中所有结点的度的最大值。叶子结点:度为零的结点。分支结点:度大于零的结点；路径和路径长度。孩子结点、双亲结点、兄弟结点、堂兄弟、祖先结点、子孙结点。边：双亲节点x到子结点y的有序对(x，y)。结点的层次:假设根结点的层次为1，第i层的结点的子树根结点的层次为i+1。规定根的层数为0。树的深度：树中叶子结点所在的最大层次。森林：是m（m≥0）棵互不相交的树的集合任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点，F被称为子树森林。第六章第六章6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林6.7哈...
