2孩子链表示式 方法:把每一个结点的孩子结点排列起来, 构成一个单链表称为孩子链表。对于一棵 有n个结点的树来说,就有n个孩子链表为 便于查找,n个链表的表头指针可用顺序表示。 特点:根据每一个结点组成的链表,可以直接 读取该结点的孩子结点地址,但查找双亲结点 较困难。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 2.孩子链表示式 方法： 把每一个结点的孩子结点排列起来， 构成一个单链表,称为孩子链表。对于一棵 有n个结点的树来说，就有n个孩子链表,为 便于查找,n个链表的表头指针可用顺序表示。 特点：根据每一个结点组成的链表，可以直接 读取该结点的孩子结点地址，但查找双亲结点 较困难
例:以图5-1所示的三度树为例,其 孩子链存储表示如图5-3所示。 45面8m +8 9 0 root -1 图53图51所示树的孩子链表存储表示 武汉理工人子平发子阢-倍总工性 系
武汉理工大学华夏学院-信息工程 系 1 3 2 3 4 5 6 7 8 9 10 11 a b c d e f g h j k l 2 4 5 6 ∧ 7 8 9 10 11 ∧ ∧ ∧ ∧ root 1 ∧ ∧ ∧ ∧ ∧ ∧ 图5-3 图5-1所示树的孩子链表存储表示 例： 以图5-1所示的三度树为例，其 孩子链存储表示如图5-3所示
3.左孩子右兄弟链表表示 方法:设置一个二叉链表,该链表的每一个 结点都包含两个指针,分别指向该结点的第 个孩子和紧靠该结点右边的一个兄弟结点,所 →以,结点由三个字段构成。 实例:以图5-1所示的三度树为例,该存储 方法的表示如图5-4所示。 特点:根据结点本身可以直接读到该结点的第 一个孩子结点及其最右边一个兄弟结点的地 址,但查找双亲结点地址也较困难。 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 3. 左孩子右兄弟链表表示 方法：设置一个二叉链表，该链表的每一个 结点都包含两个指针，分别指向该结点的第一 个孩子和紧靠该结点右边的一个兄弟结点，所 以，结点由三个字段构成。 实例： 以图5-1所示的三度树为例，该存储 方法的表示如图5-4所示。 特点：根据结点本身可以直接读到该结点的第 一个孩子结点及其最右边一个兄弟结点的地 址，但查找双亲结点地址也较困难
结点形式:「孩子地址隋点数据兄弟地址1 字段值字目 一cA e 國g一h內 k 图54图5-1所示树的左孩子右兄弟链表存储表示 武汉理工大学华夏学院-信息工程 系
武汉理工大学华夏学院-信息工程 系 结点形式: 孩子地址 字段 结点数据 值字段 兄弟地址 字段 root 图5-4 图5-1所示树的左孩子右兄弟链表存储表示 ∧ d e g ∧ h b c ∧ a ∧ ∧ j ∧ f ∧ ∧ d ∧ k ∧ ∧ ∧
52二叉树 二叉树的定义和基本术语 1、定义:二叉树是结点的有限集合,它可以 为空,也可以是由一个根结点和称为根的左右 子树的两棵互不相交的二叉树组成。 2、二叉树的基本形态二叉树共有五种基本 树形,如图5-5所示 1)无左右子树 (2)只有左子树,无 的二叉树 右子树的二叉树 武汉理工大学华夏学院工程 系
武汉理工大学华夏学院-信息工程 系 一、二叉树的定义和基本术语 1、定义： 二叉树是结点的有限集合，它可以 为空，也可以是由一个根结点和称为根的左右 子树的两棵互不相交的二叉树组成。 2、二叉树的基本形态 二叉树共有五种基本 树形，如图5-５所示。 5.2 二 叉 树 （1）无左右子树 的二叉树． （2）只有左子树，无 右子树的二叉树．