9.2.5二叉树.ppt

课程简介 课程简介 * * 第九章 程序设计基础 9.2.4 二叉树 9.3 查找和排序 9.2.5 二叉树 * * * * 9.2.5 二叉树 树形（或图形）：非线性结构。如：人类社会的家族族谱、各种社会组织机构以及城市交通、通讯等，这些事物之间的联系都是非线性的。 二叉树是应用最广泛、最有代表性的树型结构。 9.2.5 二叉树 树结构 （除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有零个或多个直接后继。 在树图形表示中，用直线连接起来的两端结点中，上端结点是前趋，下端结点是后继。没有后继的结点称为叶子结点。 * * 9.2.5 二叉树 树型结构应用：有层次关系的数据都可用树结构描述 血缘关系 组织层次关系 信息的组织 图像处理 数据查找 排序 * * * * 9.2.5 二叉树 二叉树定义： 二叉树（Binary Tree）是有限个元素的集合。该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素称作一个结点。 主要事项：二叉树是有序的，若将其左、右子树颠倒，就成为另一棵不同的二叉树。即使某个结点只有一棵子树，也要区分它是左子树还是右子树。 * * 9.2.5 二叉树 二叉树五种基本形态 及特点： 左子树 右子树 左子树 右子树 (a) (b) (c) (d) (e) Ф 二叉树二个特点： ①非空二叉树只有一个根结点； ②每一个结点最多有两棵子树，且分别称为结点的左子树与右子树。 9.2.5 二叉树 二叉树中相关术语： 度：结点所拥有的子树的个数； 叶结点：度为0的结点； 分支结点：度不为0的结点； 孩子：树中一个结点的子树的根结点； 双亲：有兄弟关系的孩子结点的前驱； 兄弟：有同一个双亲的孩子结点之间的关系； * * 9.2.5 二叉树 二叉树中相关术语： 路径：一棵树的一串结点n1, n2, …, nk有如下关系：结点ni是ni+1的父结点（1≤ik），n1, n2, …, nk称为一条由n1至nk的路径，路径长度是k-1。 树的深度：树中所有结点的最大层数。规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1 树的度：树中各结点度的最大值 * * 9.2.5 二叉树 满二叉树定义： 在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样二叉树称作满二叉树 。 * * 9.2.5 二叉树 满二叉树结点总数： * * 9.2.5 二叉树 满二叉树特点： 每一层结点数都达到最大值； 结点度数要么为0,要么为2，不存在度数为1的结点； 表示顺序从根开始,层间从上到下,层内从左到右,逐层进行编号(1,2,…,n). * * 9.2.5 二叉树 完全二叉树定义: 一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。 * * 9.2.5 二叉树 完全二叉树的特点： 叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。 * * 9.2.5 二叉树 完全二叉树的判定： 一棵给定的二叉树是否为完全二叉树，一般利用定义进行判定，也有其他的判定方法。 * * 9.2.5 二叉树 满二叉树和完全二叉树之间的关系： 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。图1、图2分别为深度为3的满二叉树和完全二叉树。图3为一棵非完全二叉树。 * * 9.2.5 二叉树 二叉树的主要性质： 性质1 一棵非空二叉树的第i层上最多有2i-1个结点（i≥1）。参见满二叉树 性质2 一棵深度为k的二叉树中，最多具有2k－1个结点。 参见满二叉树 性质3 对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有n0＝n2＋1。 * * 9.2.5 二叉树 二叉树的存储： 二叉树通常采用链式存储结构，也可以采用顺序存储及其他存储结构。 存储结点由两部分组成：数据域与两个指针域(一个指向该结点的左子树的存储地址，称为左指针域；另一个指向该结点的右子树的存储地址，称为右指针域)。 * * lchild data rchild 9.2.5 二叉树 二叉树存储示意图： * * 9.2.5 二叉树 二叉树的遍历： 定义：遍历指顺着某一条有哪些信誉好的足球投注网站路径不重复不遗漏地巡访二叉树中的所有结点，使