完全二叉树的性质: 「性质1]一棵具有n个结点的完全二叉树的深 度为Llog2n+1 「性质2]若一棵完全二叉树中共有n个结点, 对于其中编号为i(1≤K≤n)的结点,有: 1)若i1,则i结点的双亲结点为Li2」;若 i=-1,则其为根结点,无双亲。 2)若2还m,则结点的左孩子为2;若2>n, 则i结点无左孩子。 3)若2i+1<n,则i结点的右孩子为2计+1;若 2计+1>n,则结点无右孩子
计 算 机 软 件 基 础 ❖完全二叉树的性质： [性质1] 一棵具有n个结点的完全二叉树的深 度为log2n +1。 [性质2] 若一棵完全二叉树中共有n个结点， 对于其中编号为i（1≤i≤n）的结点，有： 1）若i≠1，则i结点的双亲结点为i/2 ；若 i=1，则其为根结点，无双亲。 2）若2i≤n，则i结点的左孩子为2i；若2i>n， 则i结点无左孩子。 3）若2i+1≤n，则i结点的右孩子为2i+1；若 2i+1>n，则i结点无右孩子。
(3)平衡二叉树 若一棵二叉树中每个结点的左、右 子树的深度之差(平衡因子)均不大于1, 则称该二叉树为平衡二叉树。 A B 平衡二叉树示例 E F
计 算 机 软 件 基 础 若一棵二叉树中每个结点的左、右 子树的深度之差（平衡因子）均不大于1， 则称该二叉树为平衡二叉树。 （3）平衡二叉树 B C D E A F 平衡二叉树示例
令三种特殊二叉树之间的关系 满二叉树 完全二叉树 平衡二叉树
计 算 机 软 件 基 础 ❖ 三种特殊二叉树之间的关系 满二叉树 完全二叉树 平衡二叉树
4.二叉树的存储 (1)顺序存储结构 实现方法:二叉树的顺序存储结构是用一组 地址连续的存储单元依次(从上到下,从左 到右)存放二叉树中的各个结点的数据信息, 借助于各个结点在存储结构中存放的相对位 置来反映其逻辑关系 国为什么
计 算 机 软 件 基 础 4. 二叉树的存储 （1）顺序存储结构 实现方法：二叉树的顺序存储结构是用一组 地址连续的存储单元依次（从上到下，从左 到右）存放二叉树中的各个结点的数据信息， 借助于各个结点在存储结构中存放的相对位 置来反映其逻辑关系。 适用范围：只适合 完全二叉树 。
例:对如下完全二叉树进行顺序存储 B EF A BCDEFGHIJ 12345678910
计 算 机 软 件 基 础 B C D E F G A H I J 例：对如下完全二叉树进行顺序存储。 A B C D E F G H I J 1 2 3 4 5 6 7 8 9 10