下图(a)给出一棵二又树的二叉链表示。二又链表也可 以带头结点的方式存放,如图(b)所示。 头指针bt 头结点描针bt BA AD AE∧ ALFAAD ∧EAAF∧ AGA ∧GA (a)不带头结点的二叉链表 (b)带头结点的二叉链表 2021年1月21日 数据结构讲义 21
2021年1月21日 数据结构讲义 21 • 下图(a)给出一棵二叉树的二叉链表示。二叉链表也可 以带头结点的方式存放，如图(b)所示
(2)三叉链表存储 每个结点由四个域组成,具体结构为 child data rchild parent 其中,data、 Child以及 rchild三个域的意义同二叉链表结 构; parent域为指向该结点双亲结点的指针。这种存储结构 既便于查找孩子结点,又便于查找双亲结点;但是,相对于 二叉链表存储结构而言,它增加了空间开销。 2021年1月21日 数据结构讲义 22
2021年1月21日 数据结构讲义 22 （2）三叉链表存储 每个结点由四个域组成，具体结构为： 其中，data、lchild以及rchild三个域的意义同二叉链表结 构；parent域为指向该结点双亲结点的指针。这种存储结构 既便于查找孩子结点，又便于查找双亲结点；但是，相对于 二叉链表存储结构而言，它增加了空间开销
下图给出一棵二叉树的三叉链表示。 啁A人 BA ∧|D ∧|E|∧ ∧|F|A AG人 一棵二叉树的三叉链表表示示意图 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 23 • 下图给出一棵二叉树的三叉链表示
尽管在二叉链表中无法由结点直接找到其双亲,但由于 二叉链表结构灵活,操作方便,对于一般情况的二叉树, 甚至比顺序存储结构还节省空间。因此,二叉链表是最常 用的二叉树存储方式。本书后面所涉及到的二叉树的链式 存储结构不加特别说明的都是指二叉链表结构 二叉树的二叉链表存储表示可描述为: typedef struct BiNOde( elemtype data struct Binode* child;* rchild;/*左右孩子指针* ) BiTNode, *BiTree 即将 Litre定义为指向二叉链表结点结构的指针类型。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 24 • 尽管在二叉链表中无法由结点直接找到其双亲，但由于 二叉链表结构灵活，操作方便，对于一般情况的二叉树， 甚至比顺序存储结构还节省空间。因此，二叉链表是最常 用的二叉树存储方式。本书后面所涉及到的二叉树的链式 存储结构不加特别说明的都是指二叉链表结构。 • 二叉树的二叉链表存储表示可描述为： typedef struct BiTNode{ elemtype data; struct BiTNode *lchild;*rchild; /*左右孩子指针*/ }BiTNode,*BiTree; 即将BiTree定义为指向二叉链表结点结构的指针类型
6.2.2二叉树的基本操作及实现 二叉树的基本操作通常有以下几种: (1) Initiate(bt)建立一棵空二叉树。 (2) Create(x,bt,rbt)生成一棵以x为根结点的数 据域信息,以二叉树bt和rb为左子树和右子树的二叉树。 (3) Insert(bt,x, parent)将数据域信息为x的结点 插入到二叉树b中作为结点 paren的左孩子结点。如果结 点 parent原来有左孩子结点,则将结点 parent原来的左孩 子结点作为结点x的左孩子结点。 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 25 6.2.2 二叉树的基本操作及实现 二叉树的基本操作通常有以下几种： （1）Initiate（bt）建立一棵空二叉树。 （2）Create（x，lbt，rbt）生成一棵以x为根结点的数 据域信息，以二叉树lbt和rbt为左子树和右子树的二叉树。 （3）InsertL（bt，x，parent）将数据域信息为x的结点 插入到二叉树bt中作为结点parent的左孩子结点。如果结 点parent原来有左孩子结点，则将结点parent原来的左孩 子结点作为结点x的左孩子结点