第六章树和二叉树 基本概念 二叉树 二叉树的遍历和线索树 树 赫夫曼树 只有根结点的树 一般树 数据结构 层次 C 树和二叉树 G( 4(K)(L
1 第六章 树和二叉树 基本概念 二叉树 二叉树的遍历和线索树 树 赫夫曼树 数 据 结 构 之 树 和 二 叉 树 2 只有根结点的树 一般树 层次 1 2 3 4 A B C D E F G K L H I J M A
61树的基本概念 树的基本概念 结 1.树:是n(n>=0)个结点的有限集 n=0称空树。 在任一非空树(n>0)中 (1)有且仅有一个称为根的结点; 树 (2)其余结点可分为m(m>=0)个互不相交的 和有限集T1,T2,…,Tm,其中,每个集 合本身又是一棵树,并且称为根的子树 树2.结点的度:树的结点所拥有的子树数; 3.树的度:是树内各结点的度的最大值 4度为0的结点称为叶结点或终端结点 5.孩子结点、双亲结点、兄弟结点、堂兄弟 数 据 结点、祖先结点、子孙结点 物6结点的层次从根开始,根为第一层,根的 孩子为第二层;若某结点在第L层,则其 子树的根就在第L+1层。 7.树的深度或高度:树中结点的最大层次 树8有序树:如果将树中结点的各子树看成是 从左至右有次序的;反之,则是无序树 树9.森林:是m棵互不相交的树的集合
2 数 据 结 构 之 树 和 二 叉 树 3 6.1 树的基本概念 ¾ 树的基本概念 1. 树：是n(n>=0)个结点的有限集。 n=0 称空树。 在任一非空树(n>0)中: (1) 有且仅有一个称为根的结点； (2) 其余结点可分为m(m>=0)个互不相交的 有限集T1，T2，……，Tm，其中，每个集 合本身又是一棵树，并且称为根的子树。 2. 结点的度：树的结点所拥有的子树数； 3. 树的度：是树内各结点的度的最大值； 4. 度为0的结点称为叶结点或终端结点 数 据 结 构 之 树 和 二 叉 树 4 5. 孩子结点、双亲结点、兄弟结点、堂兄弟 结点、祖先结点、子孙结点…… 6. 结点的层次从根开始，根为第一层，根的 孩子为第二层；若某结点在第L层，则其 子树的根就在第L+1层。 7. 树的深度或高度：树中结点的最大层次。 8. 有序树：如果将树中结点的各子树看成是 从左至右有次序的；反之，则是无序树。 9. 森林：是m棵互不相交的树的集合
数据结构 例:9个根结点的树:A是根,其他结点为三 个互不相交的有限集,T1={B,E,F,G,I} T2={C},T3={D,H},T13都是根A的子树,而本 身又都是一棵树 树和二叉树 ⑥D 树的表示法 数据结构 分支图表示法 嵌套集合表示法 树和二叉树 广义表表示法 (A(B(D).C)
3 数 据 结 构 之 树 和 二 叉 树 5 例：9个根结点的树：A是根，其他结点为三 个互不相交的有限集，T1= {B, E, F, G, I}, T2 ={C},T3 ={D,H},T1-3都是根A的子树，而本 身又都是一棵树。 A B C D E F G H I 数 据 结 构 之 树 和 二 叉 树 6 ¾ 树的表示法 ¾ 分支图表示法 ¾ 嵌套集合表示法 ¾ 广义表表示法 (A(B(D),C)) A B C D A B C D
树的基本操作 初始化操作 INITIATE(T):创建一棵空树。 据结构 求根函数R00T(T):求树T的根;R0OT(X:求 结点x所在树的根。 求双亲函数 PARENT(T,x):在树T中求x的双亲 求第个孩子函数 CHILD(T,x,i):在树T中求 树和二叉树 结点x的第i个孩子。 求兄弟函数: > LSIBLING(T,x):在T中求x的左兄弟 RSIBLING(T,x):在树T中求x的右兄弟 数据结构 建树函数 CRT-TREE(x,F):建立以结点x为 根,森林F为子树的树。 插入子树操作INS- CHILD(y,i,x):将x作为 y的第i棵子树 删除子树操作 DEL-CHILD(x,i):删除x的第 i棵子树。 树和二叉树 遍历树操作 TRAVERSE(T):按顺序访问树T 中各个结点 >置空树操作 CLEAR(T):将树T置为空树
4 数 据 结 构 之 树 和 二 叉 树 7 ¾ 树的基本操作 ¾ 初始化操作INITIATE(T)：创建一棵空树。 ¾ 求根函数ROOT(T)：求树T的根；ROOT(X)：求 结点x所在树的根。 ¾ 求双亲函数PARENT(T,x)：在树T中求x的双亲。 ¾ 求第i个孩子函数CHILD(T,x,i)：在树T中求 结点x的第i个孩子。 ¾ 求兄弟函数： ¾LSIBLING(T,x):在T中求x的左兄弟 ¾RSIBLING(T,x):在树T中求x的右兄弟 数 据 结 构 之 树 和 二 叉 树 8 ¾ 建树函数CRT-TREE(x,F)：建立以结点x为 根，森林F为子树的树。 ¾ 插入子树操作INS-CHILD(y,i,x)：将x作为 y的第i棵子树。 ¾ 删除子树操作DEL-CHILD(x,i)：删除x的第 i棵子树。 ¾ 遍历树操作TRAVERSE(T)：按顺序访问树T 中各个结点。 ¾ 置空树操作CLEAR(T)：将树T置为空树
6.2二叉树 数>二叉树的概念 1、特点:每个结点至多只有两棵子树,左右子树次 构序不能改变。 2、满二叉树:一个深度为k,且有21个结点的二 叉树。特点:树中没有度为1的结点。 3、完全二叉树:当树中每个结点都与相同深度的满 树二叉树中编号从1至n的结点一一对应。 和二叉树 自060606 据例:有5种类型的二叉树如下 构 只有左子树 只一个根结点 树和二叉树 只有右子树 左右子树都有 10
5 数 据 结 构 之 树 和 二 叉 树 9 6. 2 二叉树 ¾ 二叉树的概念 1、特点：每个结点至多只有两棵子树，左右子树次 序不能改变。 2、满二叉树：一个深度为k，且有2 -1个结点的二 叉树。特点：树中没有度为1的结点。 3、完全二叉树：当树中每个结点都与相同深度的满 二叉树中编号从1至n的结点一一对应。 一 般 二 叉 树 满 二 叉 树 完 全 二 叉 树 k 数 据 结 构 之 树 和 二 叉 树 10 例：有5种类型的二叉树如下 A A B A B A B C 空 只一个根结点 只有左子树 只有右子树 左右子树都有