数据结构 第6章 树和二叉树.pptVIP

第六章 树和二叉树 （一）教学目的： 掌握树和二叉树的定义及存储结构；二叉树的基本操作；树和二叉树的应用。 （二）教学重点： 1、树的定义及相关术语。 2、二叉树的定义、存储结构和基本运算的实现。 3、二叉树的遍历，二叉树与树和森林的相互转换。 4、哈夫曼树及应用数组的定义及其存储 （三）教学难点： 1、二叉树的定义、存储结构和基本运算的实现 2、哈夫曼树及应用。 基本内容： 6.1树的概念和基本术语 6.2二叉树 6.3遍历二叉树和线索二叉树 6.4树与森林 6.6哈夫曼树 二、树的表示 1、树型表示法 2、集合表示法 3、括号表示法 （1（2（4，5），37））） 4、凹入表示法 三、树的基本术语 结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支 结点的度(degree)——结点拥有的子树数 叶子(leaf)——度为0的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的~ 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 森林(forest)——m(m?0)棵互不相交的树的集合 性质2 深度为 k 的二叉树至多有 2 k-1个结点(k ? 1)。 证明：由性质1可见，深度为k的二叉树的最大结点数为 三、二叉树的存储结构 1、顺序表示 （1）完全二叉树的存储，采取一维数组就可以存储出来，将每个元素按照从上而下，从左到右的顺序依次存储在数组中，则元素之间关系利用元素的存储下标可以实现。 （2）非完全二叉树的存储，需先补齐0使之成为完全二叉树，然后按照完全二叉树的存储形式。 2、链式存储结构-------二叉链表 6.3 二叉树的遍历 4、由二叉树的先序（或后序）序列和中序序列可唯一地确定一棵二叉树。 例, 先序序列 { ABHFDECKG } 和中序序列 { HBDFAEKCG }, 构造二叉树过程如下： 2、遍历二叉树的非递归算法 先序遍历：算法1，将右子树根结点 入栈，(栈所需最大容量为n/2+1)；算法2将根结点入栈 中序遍历：在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出，访问，再遍历右子树 后序遍历： 1）设定一个指针，指向 最近访问过的结点。在退栈取出根结点时，需判断：若根结点的右子树为空，或它的右子树非空，但已遍历完毕，即它的右子树根结点恰好是最近一次访问过的结点时，应该遍历该根结点。反之，该根结点应重新入栈，先遍历它的右子树。 2）还可同时设定一个标记，指示该根结点是第一次还是第二次入栈 需用到栈，顺序栈的定义如下： typedef BiTNode* SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; 五、二叉树遍历应用 2、二叉树的显示输出 void PrintBiTree(BiTree T,int n) { int i; char ch= ; if (T) { PrintBiTree(T-rchild,n+1); for (i=1;i=n;++i) {printf(%5c,ch);} printf(%c\n, T-data); PrintBiTree(T-lchild,n+1); } } 3.计算二叉树结点个数(递归算法) 6.3.2 线索二叉树 三、线索二叉树的建立过程：例1：画出以下二叉树对应的中序线索二叉树。 四、线索二叉树的生成算法 五、线索二叉树的遍历 6.4树与森林 2、孩子表示法 3、用孩子兄弟表示法来存储 例如： 二叉树怎样还原为树？ 森林转二叉树举例： 二叉树如何还原为森林？ 当树非空时 访问根结点 依次先根遍历根的各棵子树 树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现 2、树的后根次序遍历: 当树非空时 依次后根遍历根的各棵子树 访问根结点 树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现 6.6哈夫曼树 (Huffman Tree) 3