数据结构（Python Java）（微课版） 课件 5.2 二叉树

数据结构与算法设计二叉树的概念二叉树的性质二叉树的存储二叉树的遍历5.2二叉树定义二叉树是节点的有限集合或者是空树或者由一个根节点和两棵二叉子树构成左子树，右子树子树不相交特点每个节点至多有二棵子树不存在度大于2的节点子树有左、右之分，次序不能任意颠倒二叉树二叉树的五种形态空二叉树右子树为空的二叉树左子树非空的二叉树仅有根节点的二叉树左右子树均非空的二叉树深度为k的满二叉树，有2k-1个节点2k-1是深度为K的二叉树所具有的最大节点个数满二叉树123114589121367101415特点每层上的节点数都达到最大值只有度为0的节点和度为2的节点每个节点均有两棵高度相同的子树叶子节点都在树的最下面一层上叶子节点只出现在最低两层上对任意节点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次为L或L+1除最低层外，每一层上的节点数均达到最大值；在最低层上只缺少右边的若干节点(也可不缺)。完全二叉树123114589121367101415满二叉树完全二叉树123114589126710性质1：在二叉树第i层上至多有2i-1

个节点(i≥1)证明：当i=1时，只有一个根节点。显然，2i-1

＝20

＝１是对的假设对所有的j(1≤j﹤i)，命题成立即第j层上至多有2j-1

个节点那么可以证明j=i时命题成立归纳假设：第i-1层上至多有2i-2

个节点。由于二叉树的每个节点的度至多为2，故在第i层上的最大节点数为第i-1层上的最大节点数的2倍即2*2i-2＝2i-1。二叉树的性质123114589121367101415性质2：深度为k的二叉树至多有2k-１个节点(k≥1)证明：

由性质１可见，深度为k的二叉树的最大节点数为：二叉树的性质123114589121367101415性质3：对任意二叉树T，如果其终端节点数为n0

，度为2的节点数为n2,则n0=n2+1。证明：二叉树中节点总数为：

n=n0+n1+n2 (5-1)二叉树的分支数为：

n1+2*n2 (5-2)因此，节点总数为：

n=n1+2*n2+1由(5-1)、(5-2)两式可得：

n0=n2+1二叉树的性质1234567性质4：具有n个节点的完全二叉树的深度为

log2

n

+1证明：假设深度为k，则根据性质2和完全二叉树的定义有于是因为k是整数,所以二叉树的性质性质5：对一棵有n个节点的完全二叉树的节点按层序号编号(从第1层到

log2n

+1层，每层从左到右)，则对任一节点i(1≤i≤n)，有：如果i=1，则节点i是根节点，无双亲，否则，其双亲节点为：

i/2

如果2i>n，则节点i无左孩子(节点i为叶子节点);否则其左孩子是节点2i如果2i+1>n，则节点i无右孩子;否则其右孩子是节点2i+1二叉树的性质123114589126710顺序存储将任意二叉树“修补”成完全二叉树利用顺序表对数据元素进行存储原二叉树中空缺的节点在数组中相应单元置空二叉树的存储123φ5φ7φφ10链式存储:二叉链表节点包含3个域：数据域和指向左、右子树的指针域二叉树的存储LChildDataRChild遍历（taversal）按一定的规则和次序走遍二叉树的所有节点使每个节点都被访问一次，且只被访问一次访问对节点进行各种操作遍历二叉树的目的遍历是对数据进行操作的基础得到二叉树中各节点的一种线性顺序使非线性的二叉树线性化，简化有关的运算和处理二叉树的遍历若二叉树为空，则返回；否则依次执行以下操作：访问根节点；按先序遍历左子树；按先序遍历右子树；返回。先序遍历先序遍历序列：ABDECACBDEACBDE若二叉树为空，则返回；否则依次执行以下操作：按中序遍历左子树；访问根节点；按中序遍历右子树；返回。中序遍历中序遍历序列：DBEACACBDEACBDE若二叉树为空，则返回；否则依次执行以下操作：按后序遍历左子树；