电子斜技大学 软件技术基础 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 • 顺序存储（一维数组） • 链式存储结构 –二叉链表 –三叉链表 • 记录数组结构