数据结构 课件 二叉树

《数据结构 课件 二叉树》由会员分享，可在线阅读，更多相关《数据结构 课件 二叉树（125页珍藏版）》请在金锄头文库上搜索。

1、树与二叉树,软件学院 王建文,树的用处举例,线性表适合表示一个顺序序列 (e0, e1, e2, , en-1) Days of week. Months in a year. Students in this class. 树适合表示具有层次结构的数据 族谱(课本176页), 公司组织结构等,Example Tree,搜索树,中文输入法的实现原理是字符编码与字符或词组之间的映射形成一张码表，如： zhang，张; wang,王; zhao，赵; li，李; laoshi，老师; 线性表存储，顺序地查找，时间复杂度O（n） 广义表存储,逐层地查找，时间复杂度O（h） 树存储, 逐层地查找，时间

2、复杂度O（h），大约为O(log n),第五章 树,树和森林的概念 二叉树 (Binary Tree) 二叉树的表示 二叉树遍历 (Binary Tree Traversal) 线索化二叉树 (Threaded Binary Tree) 堆 ( Heap ) 树与森林 (Tree & Forest) 二叉树的计数 霍夫曼树 (Huffman Tree),树和森林的概念,树的定义 树是由n (n 0)个结点组成的有限集合。如果n = 0，称为空树；如果n 0，则 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱； 除根以外的其它结点划分为m (m 0)个互不相交的有限集合T

3、0, T1, , Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。,根,子树,结点(node) 结点的度(degree) 分支(branch)结点 叶(leaf)结点 子女(child)结点 双亲(parent)结点,兄弟(sibling)结点 祖先(ancestor)结点 子孙(descendant)结点 结点所处层次(level) 树的高度(depth) 树的度(degree),有序树无序树森林,1,2,3,4,4,树的术语,基本术语 结点(node)表示树中的元素，包括数据项及若干指向其子树的分支结点的

4、度(degree)结点拥有的子树数叶子(leaf)度为0的结点孩子(child)结点子树的根称为该结点的孩子双亲(parents)孩子结点的上层结点叫该结点的,基本术语,兄弟(sibling)同一双亲的孩子 树的度一棵树中最大的结点度数 结点的层次(level)从根结点算起，根为第一层，它的孩子为第二层 深度(depth)树中结点的最大层次数 森林(forest)m(m0)棵互不相交的树的集合,结点A的度：3 结点B的度：2 结点M的度：0,叶子：K，L，F，G，M，I，J,结点A的孩子：B，C，D 结点B的孩子：E，F,结点I的双亲：D 结点L的双亲：E,结点B，C，D为兄弟 结点K，L为兄

5、弟,树的度：3,结点A的层次：1 结点M的层次：4,树的深度：4,结点F，G为堂兄弟 结点A是结点F，G的祖先,树的表示方法,见课本178-179,二叉树的五种不同形态,L,L,R,R,二叉树 (Binary Tree),二叉树的定义一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。,二叉树的性质,性质1 若二叉树结点的层次从 1 开始, 则在二叉树的第 i 层最多有 2i-1 个结点。( i1)证明用数学归纳法性质2 深度为 k 的二叉树最少有 k 个结点，最多有 2k-1个结点。( k1 )因为每一层最少要有1个结点，

6、因此，最少结点数为 k。最多结点个数借助性质1：用求等比级数前k项和的公式20 +21 +22 + +2k-1 = 2k-1,性质3 对任何一棵二叉树，如果其叶结点有 n0 个, 度为 2 的非叶结点有 n2 个, 则有n0n21若设度为 1 的结点有 n1 个，总结点数为n，总边数为e，则根据二叉树的定义，n = n0+n1+n2 e = 2n2+n1 = n-1因此，有 2n2+n1 = n0+n1+n2-1n2 = n0-1 n0 = n2+1,例：已知叶子数为20，10个结点有一个左孩子，15个结点有一个右孩子，求该二叉树的总结点数。 解：n0 = 20 n1 = 10 + 15 =

7、25由于 n0 = n2 + 1 则：n2 = n0 1= 19 n = n0 + n1 + n2 = 20 + 25 + 19 = 64,满二叉树 定义：满二叉树是满足如下条件的二叉树： 任一非叶子结点均有两个孩子； 对于二叉树的任一层，若该层上有一个结点有孩子，则该层上所有结点均有孩子。 特点：满二叉树的每层都有最大结点数。,两种特殊的二叉树,完全二叉树定义：在满二叉树的最下层从右到左连续地删除若干个结点所得到的二叉树。特点： 叶子结点只可能在层次最大的两层上出现； 满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。,例：满二叉树和完全二叉树,性质4 具有 n (n0) 个结点的完全

8、二叉树的深度为 log2(n+1) 设完全二叉树的深度为k，则有2k-1-1 n 2k-1变形 2k-1 n+12k 取对数 k-1 1, 则 i 的双亲为i2 若2*i = n, 则 i 的左子女为 2*i，若2*i+1 = n, 则 i 的右子女为2*i+1 若 i 为奇数, 且i != 1, 则其左兄弟为i-1, 若 若 i 为偶数, 且i != n, 则其右兄弟为i+1,思考题：有100个结点的完全二叉树有多少个叶子结点？ 解：第100个结点的编号为100，其父结点的编号为50，且其父结点的右兄弟（编号为51）没有孩子，即为叶子；所以，叶子结点的编号从51至100，叶子结点有50个。,

9、二叉树存储结构,顺序存储 链式存储,顺序存储将一棵二叉树中的结点，按它们在完全二叉树中的编号顺序，依次存储在一维数组中；即编号为 i 的结点存储在数组中下标为 i 的元素中。这样，根据性质5可知编号为 i 的结点，其左孩子下标为2i ，其右孩子下标为2i +1，其父结点的下标为i/2。,例：如下二叉树的顺序存储。,先对二叉树中结点进行编号;将二叉树存储在数组tree中。,二叉树顺序存储的特点： 结点间关系蕴含在其存储位置中，无需附加任何信息就能在这种顺序存储结构里找到每个结点的双亲和孩子。 浪费空间，适于存储满二叉树和完全二叉树。,顺序存储结构用一组地址连续的存储单元， 按一定次序保存二叉树中

10、数据元 素，以结点间存储地址上的联系， 体现结点间双亲与孩子的关系。,完全二叉树-数组元素连续,顺序存储结构一般用于保存完全 二叉树或满二叉树。若用于存储一般 二叉树，则存储空间浪费较大。,右单支树-最浪费空间,二叉树结点定义：每个结点有3个数据成员，data域存储结点数据，leftChild和rightChild分别存放指向左子女和右子女的指针。,二叉链表,二叉树的链表表示（二叉链表）,三叉链表,二叉树的链表表示（三叉链表）,每个结点增加一个指向双亲的指针parent，使得查找双亲也很方便。,二叉树链表表示的示例,二叉树 二叉链表 三叉链表,在n个结点的二叉链表中，有n+1个空指针域，三叉链

11、表中有n+2个空指针域,The Struct binaryTreeNode,template class Tree; /前置声明 template class TreeNode T data;TreeNode *leftChild, *rightChild; TreeNode() leftChild = rightChild = NULL;/ other constructors come here ;,template class Tree private:TreeNode *root;void inorder(TreeNode *);void preorder(TreeNode *);vo

12、id postorder(TreeNode *);TreeNode* copy(TreeNode *); public:void setup();void inorder();void preorder();void postorder();Tree(const Tree,二叉树遍历(Binary Tree Traversal),所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L遍历根的右子树记作 R则可能的遍历次序有前序 VLR 镜像 VRL中序 LVR 镜像 RVL后序 LRV 镜像 RLV,二叉树的先序遍历方法 访问根

13、结点； 先序遍历左子树； 先序遍历右子树。,A,B,D,遍历序列：,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,F,A,B,D,遍历序列：,D,E,H,E,G,G,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,F,A,B,D,遍历序列：,D,E,E,G,G,H,H,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,F,A,B,D,遍历序列：,D,E,E,G,G,H,H,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根

14、结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,F,A,B,D,遍历序列：,D,E,E,G,G,H,H,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,A,B,D,遍历序列：,D,E,E,G,G,H,H,C,F,F,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,A,B,D,遍历序列：,D,E,E,G,G,H,H,C,F,F,二叉树的先序遍历方法,二叉树的先序遍历方法 访问根结点； 先序遍历左子树； 先序遍历右子树。,B,A,C,A,B,D,遍历序列：,D,E,E,G,G,H,H,C,F,F,二叉树的先序遍历方法,二叉树的中序遍历方法 中序遍历左子树； 访问根结点； 中序遍历右子树。,D,遍历序列：,二叉树的中序遍历方法,二叉树的中序遍历方法 中序遍历左子树； 访问根结点； 中序遍历右子树。,D,B,G,遍历序列：,二叉树的中序遍历方法,二叉树的中序遍历方法 中序遍历左子树； 访问根结点； 中序遍历右子树。,D,B,G,遍历序列：,E,H,二叉树的中序遍历方法,二叉树的中序遍历方法 中序遍历左子树； 访问根结点； 中序遍历右子树。,D,B,G,遍历序列：,E,H,二叉树的中序遍历方法,二叉树的中序遍历方法 中序遍历左子树； 访问根结点； 中序遍历右子树。,