chapter06_树和二叉树.ppt

树和二叉树;6.1 树的定义与基本术语;②其余n-1个结点可以划分成m(m=0)个互不相干的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，称为根root的子树。 每棵子树的根结点有且仅有一个直接前驱，可有零个或多个直接后继。;树的图解表示法;树的图解表示法;树的相关术语;树的相关术语;树的相关术语;树的相关术语;树的基本操作;树的基本操作;树的基本操作;6.2 二叉树;位于左边的孩子叫做左孩子位于右边的孩子叫做右孩子;例题：请分别画出三个结点的树和二叉树，试分析共有多少种不同画法？;二叉树的基本操作;二叉树的基本操作;二叉树的性质;满二叉树和完全二叉树;二叉树的基本性质;二叉树的存储结构;二叉树顺序存储的类型定义;二叉树的顺序存储结构;每个结点设计三个域：数据域、左孩子域和右孩子域。;练习：请画出下面这棵二叉树的链式存储结构图。;二叉链表结点结构的定义;二叉树的链式存储结构;练习：请画出下面这棵二叉树的链式存储结构图（要求使用三叉链表结构）。;课堂练习;6.3 二叉树的遍历和线索化;二叉树的遍历;根结点;先序遍历（DLR）操作过程;中序遍历（LDR）操作过程;后序遍历（LRD）操作过程;练习：请写出二叉树的遍历结果。;由遍历序列确定二叉树;二叉树的遍历算法;二叉树的遍历算法;遍历算法应用; 以某种方式遍历二叉树，依次输出遍历得到的结点即可。; 以某种方式遍历二叉树，对遍历得到的结点进行判断，如果是叶子结点，即输出，直到整个二叉树遍历完成。;方法一： 以某种方式遍历二叉树，判断访问到的结点是否为叶子结点，若是，计数器加1。;方法二： 采用递归算法。 空树，返回0；只有一个结点，返回1； 否则为左、右子树的叶子结点之和。;void CreateTree(BiTree *bt){ char ch=getchar(); if(ch==“.”) *bt=NULL; else{ *bt=(BiTree)malloc(sizeof(BiNode)); (*bt)-data=ch; CreateTree(((*bt)-Lchild)); CreateTree(((*bt)-Rchild)); } } 注意：这里必须使用扩展遍历的方式。;求二叉树的高度;二叉树中序遍历的非递归算法;二叉树中序遍历的非递归算法;线索二叉树的基本概念;线索二叉树的结点结构;线索二叉树的类型定义;练习???请画出二叉树的线索二叉树;先序线索二叉树： ABDGHCEJF;6.4 树、森林和二叉树的关系;树的存储结构;双亲表示法;双亲表示法;树的存储结构;typedef struct tree{ DataNode nodes [MAX]; int root; int num; }ChildTree;;树的存储结构;孩子兄弟表示法;树、森林与二叉树的相互转换;树、森林与二叉树的相互转换;二叉树还原为树或森林;二叉树还原为树或森林;二叉树还原为树或森林;树与森林的遍历;树和森林的遍历;;哈夫曼树的基本概念;例：请求出下列三棵二叉树的WPL，已知树中四个叶子结点所带的权值分别是2、4、8、9。;哈夫曼树的构造;哈夫曼编码