樹和二叉树.pptVIP

数据结构第六章 树和二叉树;本章内容 6.1 树的概念与基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树与森林 6.6 赫夫曼树;6-* ;6-* ;6-* ;6-* ;6-* ;1) 树的定义 定义：树是由n (n ≥ 0) 个结点组成的有限集合。 其中当n 0时 n=0时，为空树。 特点： ;6-* ;6-* ;6-* ; 结点(node):表示树中的元素及若干指向其子树的分支 结点的度(degree)：一个结点拥有子树的个数 树的度(degree)：一棵树中所有结点的最大度数 叶子(leaf)结点：度为0的结点 分支(branch)结点：度不为0的结点 孩子/子女(child)结点：某结点子树的根 双亲(parent)结点:某结点是其子树根的双亲 ;兄弟(sibling)结点：具有同一双亲的所有结点 祖先(ancestor)结点：从根到该结点所经分支上的所有结点 子孙(descendant)结点：以某个结点为根的子树中的任一结点 结点的层数(level)：规定根结点层数为1，其余结点层数等于其双亲结点层数加1 树的高度/深度(depth)：树中叶子结点所在的最大层次 有序树：树中每个结点的各个子树从左到右是有次序的（不能互换） 无序树：子树的次序可以互换 路径：若树中存在一个结点序列k1,k2…kj,使得ki是ki+1(1≤i≤j)的双亲，则称该序列是k1到kj的路径 森林：是m(m ? 0)棵互不相交的树的集合。;结点A的度：3 结点B的度：2 结点M的度：0;6.1 树的抽象数据类型;6.1 树的抽象数据类型;6.1 树的抽象数据类型;6.1 树的抽象数据类型;线性结构和树型结构的比较;6.2 二叉树;6.2 二叉树;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;判断下列树是否为完全二叉树;6-* ;6-* ;6.2 二叉树的存储结构;6-* ;6-* ;6.2 二叉树的存储结构;6-* ;6-* ;6-* ;6-* ;6-* ;6.3 遍历二叉树;;1） 先序遍历（DLR）;6-* ;6.3 遍历二叉树;6.3 遍历二叉树;6.3 遍历二叉树;6-* ;6.3 遍历二叉树;6.3 遍历二叉树;6.3 遍历二叉树;6-* ;6.3 遍历二叉树;6.3 遍历二叉树;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6-* ;6.6 赫夫曼树及其应用;6-* ;6.6 赫夫曼树及其应用;6.6 赫夫曼树及其应用;6.6 赫夫曼树及其应用;6-* ;6-* ;Huffman解码;总结