电子斜技大学 软件技术基础 3.5.2二叉树的基本概念 主讲教师：刘民岷 航空航天学院 a■ 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
3、二叉树基本概念 二叉树的定义：二叉树是n个结点的有限集合(n≥0)；这个集合可以 是空（即n=0),此时称为空二叉树；或者由一个根结点和两棵互不相 交的被称为根的左子树和右子树组成。左子树和右子树分别又是一棵 二叉树。 二叉树的五种基本形态 (a)空树 (b)一个 (C)左子树 (d右子树 (e)完整二 根的树 非空的树 非空的树 叉树 一天 般树与二叉树在概念上不同之处在于：树至少应有一个节点，而二 叉树可以是空；其次，二叉树的节点的子树要分为左子树与右子树， 即使某结点只有一棵子树的情况下也要指明该子树是左还是右。 电子科技大学刘民岷 树和二叉树 2
电子科技大学 刘民岷 树和二叉树 2 • 二叉树的定义：二叉树是n个结点的有限集合(n≥0)；这个集合可以 是空(即n＝0)，此时称为空二叉树；或者由一个根结点和两棵互不相 交的被称为根的左子树和右子树组成。左子树和右子树分别又是一棵 二叉树。 • 二叉树的五种基本形态 • 一般树与二叉树在概念上不同之处在于：树至少应有一个节点，而二 叉树可以是空；其次，二叉树的节点的子树要分为左子树与右子树， 即使某结点只有一棵子树的情况下也要指明该子树是左还是右。 (a)空树 (b)一个 根的树 (C) 左子树 非空的树 (d)右子树 非空的树 (e)完整二 叉树
3、二叉树基本概念（续） 满二叉树 在一棵二叉树中，如果所有 B 分支结点都存在左子树和右子树， 并且所有叶子结点都在同一层上， 这样的一棵二叉树称为满二叉树。 8 9 10 11 12 1314 15 。 完全二叉树 若一棵二叉树至多只有最下面 的两层上结点的度数可以小于2，并 B 且最下一层上的结点都集中在该层 最左边的若干位置上，则此二叉树称 G 为完全二叉树。 电子科技大学刘民岷 树和二叉树 3
电子科技大学 刘民岷 树和二叉树 3 • 满二叉树 在一棵二叉树中，如果所有 分支结点都存在左子树和右子树， 并且所有叶子结点都在同一层上， 这样的一棵二叉树称为满二叉树。 • 完全二叉树 若一棵二叉树至多只有最下面 的两层上结点的度数可以小于2，并 且最下一层上的结点都集中在该层 最左边的若干位置上，则此二叉树称 为完全二叉树。 A B C D E F G H I J K L M N O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 A B C D E F G H I J K L
3、二叉树基本概念（续） 二叉排序树 左子树上所有结点的关键字都小于根的关键字；右子树上所有结点的 关键字都大于等于根结点的关键字。左右子树本身又各是一棵二叉排 序树。 8 4 10 4 9 17 6 12 电子科技大学刘民岷 树和二叉树 4
电子科技大学 刘民岷 树和二叉树 4 • 二叉排序树 左子树上所有结点的关键字都小于根的关键字；右子树上所有结点的 关键字都大于等于根结点的关键字。左右子树本身又各是一棵二叉排 序树。 8 4 10 1 4 9 17 6 12
4、二叉树的物理存储结构 顺序存储（一维数组) 。 链式存储结构 -二叉链表 -三叉链表 ·记录数组结构 电子科技大学刘民岷 树和二叉树 5
电子科技大学 刘民岷 树和二叉树 5 • 顺序存储（一维数组） • 链式存储结构 –二叉链表 –三叉链表 • 记录数组结构
4.1二叉树的顺序存储结构 •对于满二叉树和完全二叉树，其节点的逻 辑关系符合如下特征： 对于有个结点的满二叉树和完全二叉树，如 果从上至下和从左到右的顺序对二叉树中的所 有结点从1开始顺序编号，则对于任意序号i的 结点有： (1)如果i>1,则序号为的结点的父结点的 序号为/2（取整)； 如果i=1,则结点是根结点，无父结点。 (2)如果2i长n,则序号为的结点的左子结点 6 的序号为2i。 (3)如果2i+1≤n,则序号为i的结点的右子 结点的序号为2i+1。 101112 9 1314 15 电子科技大学刘民岷 树和二叉树 6
电子科技大学 刘民岷 树和二叉树 6 •对于满二叉树和完全二叉树，其节点的逻 辑关系符合如下特征： 对于有n个结点的满二叉树和完全二叉树，如 果从上至下和从左到右的顺序对二叉树中的所 有结点从1开始顺序编号，则对于任意序号i的 结点有： （1）如果i＞1，则序号为i的结点的父结点的 序号为i/2（取整）； 如果i＝1，则结点是根结点，无父结点。 （2）如果2i≤n，则序号为i的结点的左子结点 的序号为2i。 （3）如果2i＋1≤n，则序号为i的结点的右子 结点的序号为2i＋1。 A B C D E F G H I J K L M N O 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4.1二叉树的顺序存储结构（续） B C E F G H J K L 完全二叉树 A B C D E F G H J K L 数组下标012345678 91011 电子科技大学刘民岷 树和二叉树 7
电子科技大学 刘民岷 树和二叉树 7 数组下标 0 1 2 3 4 5 6 7 8 9 10 11 A B C D E F G H I J K L 完全二叉树
4.2二叉树的二叉链表存储结构 A leftp data rightp 左指针数据 右指针 B C D B E F G 特点： 找子易，找父难 电子科技大学刘民岷 树和二叉树 8
电子科技大学 刘民岷 树和二叉树 8 特点: 找子易, 找父难. leftp data rightp 左指针 数据 右指针 A B C D E F G A B C D E F G ^ ^ ^ ^ ^ ^ ^ ^
4.3二叉树的三叉链表存储结构 leftp data parent rightp 左指针数据 父结点右指针 B B E F F 特点： G G 找子、找父都易。 电子科技大学刘民岷 树和二叉树 9
电子科技大学 刘民岷 树和二叉树 9 特点: 找子、找父都易。 data parent rightp 左指针 数据 父结点 右指针 A B C D E F G C ^ ^ ^ ^ ^ ^ A ^ ^ leftp B D E G ^ F