数据结构 5.2 二叉树 5.3 二叉树.pptxVIP

模块5 树和二叉树356412 树 实例引入 二叉树 哈夫曼树及其应用 应用举例 树、森林和二叉树5.3二叉树---五种基本形态二叉树（Binary Tree）是n（n≥0）个结点的有限集合，满足以下两个条件：（1）它或者为空树（n=0）；（2）或者是由一个根结点和称为根的左、右子树的两棵互不相交的二叉树构成的。5.3二叉树---满二叉树特点： 它的每一层上都是满的； 整棵树也是满的； 树中只有叶子和度为2的结点； 叶子都分布在最后一层上。5.3二叉树—完全二叉树非完全二叉树完全二叉树图例特点： 它的前d-1层是满二叉树； 其最后一层结点是向左充满的； 其叶子只可能出现在最后两层。5.3二叉树----性质性质1：二叉树的第i（i≥1）层上至多有2i-1个结点。性质2：深度为d（d≥1）的二叉树至多有2d-1个结点。性质3：对于任一非空二叉树T，若其叶子数为n0， 度为2的结点数为n2， 则有n0=n2+1。性质4：具有n个结点的完全二叉树的深度为?log2n?+1。性质5：如果对一棵具有n个结点的完全二叉树按层次序给各个结点编号，则对于编号为i（1≤i≤n）的结点有：（1）若i1，则i的双亲的编号为?i/2?；若i=1，则i是根结点。（2）若2i≤n，则i的左孩子编号为2i；否则i无左孩子。（3）若2i+1≤n，则i的右孩子编号为2i+1；否则i无右孩子。二叉树---顺序存储 ①将一般二叉树添上一些 “虚结点”，成为“完全二叉树”；②为了用结点在向量中的相对位置来表示结点之间的逻辑关系， 按完全二叉树的形式给结点编号；③将结点按编号存入向量对应分量，其中“虚结点”用“?”表示。二叉树---链式存储 二叉树结点的结构二叉树二叉树的链式存储—二叉链表 二叉树t二叉树---遍历 按照某种方式遍访树中的每一个结点，使每个结点被访问且仅被访问一次，称为遍历二叉树（Traversing Binary Tree）。一般地，有三种遍历方式：NLR称为先序（根）遍历，LNR称为中序（根）遍历，LRN称为后序（根）遍历。二叉树---先序遍历 1．二叉树的先序（根）遍历定义：若二叉树为空，则遍历结束；否则（1）访问根结点；（2）先序遍历根的左子树；（3）先序遍历根的右子树。二叉树t的先序遍历序列是： A，B，D，E，G，C，F，H，I。二叉树---中序遍历 2．二叉树的中序（根）遍历定义：若二叉树为空，则遍历结束；否则（1）中序遍历根的左子树；（2）访问根结点；（3）中序遍历根的右子树。二叉树t的中序遍历序列是： D，B，G，E，A，C，H，F，I二叉树---后序遍历 3．二叉树的后序（根）遍历定义：若二叉树为空，则遍历结束；否则（1）后序遍历根的左子树；（2）后序遍历根的右子树；（3）访问根结点。二叉树t的后序遍历序列是： D，G，E，B，H，I，F，C，A二叉树---遍历 例：写出右图所示二叉树的先序遍历、中序遍历、后序遍历序列。先序遍历序列：A B D C H J K E C F I M中序遍历序列：G D J H K B E A C F M I后序遍历序列：G J K H D E B M I F C A