6.2二叉树 6.2.1二叉树的定义 二叉树是一种重要的树形结构，但不是前面所 介绍的“树”的特例。 ■二叉树既不是只有两个子树的树： ■ 也不是最多有两个子树的树。 另外树和二叉树操作也有不相同的地方。 -21 145
— 21 — 6.2 二叉树 二叉树是一种重要的树形结构，但不是前面所 介绍的“树”的特例。 二叉树既不是只有两个子树的树； 也不是最多有两个子树的树。 另外树和二叉树操作也有不相同的地方。 6.2.1 二叉树的定义
6.2 二叉树 二叉树或为空树，或是由一个根结点加上两棵分 别称为左子树和右子树的、互不交的二叉树组成。 根结点 右子树 E F G 左子树 22 H K 1945
— 22 — 6.2 二叉树 二叉树或为空树，或是由一个根结点加上两棵分 别称为左子树和右子树的、互不交的二叉树组成。 根结点 左子树 右子树 B C D E F G H K A
6.2二叉树 二叉树：或为空树，或由根及两颗不相交的左子 树、右子树构成，并且左、右子树本身也是二叉树。 当集合为空时，称该二叉树为空二叉树。在二叉 树中，一个元素也称作一个结点。 1)二叉树中每个结点最多有两颗子树（每个结点 度小于等于2)： 2)左、右子树不能颠倒一有序树： 3)二叉树是递归结构，在二叉树的定义中又用到 了二叉树的概念： -23 1945
— 23 — 6.2 二叉树 二叉树：或为空树，或由根及两颗不相交的左子 树、右子树构成，并且左、右子树本身也是二叉树。 当集合为空时，称该二叉树为空二叉树。在二叉 树中，一个元素也称作一个结点。 1）二叉树中每个结点最多有两颗子树(每个结点 度小于等于2); 2）左、右子树不能颠倒——有序树; 3）二叉树是递归结构，在二叉树的定义中又用到 了二叉树的概念;
6.2二叉树 6.2.1二叉树的定义 A A B B D E D E G G (a) (b) ()的左子树有四个结点，(b)的左子树有两个结点 -24 1945
— 24 — 6.2 二叉树 A G D E B C F A G D E C B F (a) (b) 6.2.1 二叉树的定义 (a)的左子树有四个结点，(b)的左子树有两个结点
6.2二叉树 6.2.1二叉树的定义 ■二叉树、树及有序树的区别 从定义上看，二叉树既不是只有两个子树的树， 也不是最多只有两个子树的树。主要差别在于二叉 树的子树有左右之分。 在有序树中，虽然一个结点的孩子之间是有左右 次序的，但若该结点只有一个孩子时，就无须区分 其左右次序。而在二叉树中，即使是一个孩子也有 左右之分。 -25 1945
— 25 — 6.2 二叉树 二叉树、树及有序树的区别 从定义上看，二叉树既不是只有两个子树的树， 也不是最多只有两个子树的树。主要差别在于二叉 树的子树有左右之分。 在有序树中，虽然一个结点的孩子之间是有左右 次序的，但若该结点只有一个孩子时，就无须区分 其左右次序。而在二叉树中，即使是一个孩子也有 左右之分。 6.2.1 二叉树的定义