第十二讲 ●二叉树的建立 ●循环链表
1 第十二讲 ⚫二叉树的建立 ⚫循 环 链 表
二叉树的建立
2 二叉树的建立
二叉树的建立 建立二叉树的过程是一个“插入”过程,下面我们用 个例子来讲解这一过程。 我们想建立这样一棵二叉树,树中的每一个结点有 个整数数据名为data,有两个指针:左指针L,右指 针R,分别指向这个结点的左子树和右子树,显然 可以用如下名为TREE的结构来描述这种结点: struct TREe int data: struct TREE XL, xR:
3 二叉树的建立 建立二叉树的过程是一个“插入”过程，下面我们用 一个例子来讲解这一过程。 我们想建立这样一棵二叉树，树中的每一个结点有一 个整数数据名为data，有两个指针：左指针L，右指 针R，分别指向这个结点的左子树和右子树，显然 可以用如下名为TREE的结构来描述这种结点： struct TREE { int data; struct TREE *L, *R; }
对二叉树最重要的是根,它起定位的作用,因此,首先 建立的是根结点。也就是说,如果从键盘输入数据来 建立二叉树,第一个数据就是这棵树的根的数据,之 后再输入的数据,每一个都要与根中的数据作比较, 以便确定该数据所在结点的插入位置。假定我们这里 依然用图1的中序遍历的方式。即如果待插入结点的 数据比根结点的数据小,则将其插至左子树,否则插 入右子树。 定义一个递归函数 void insert(struct TREE **proot, struct TREE*p) 其中,指针p指向含有待插入数据的结点。 pro为树的根指针的地址。 insert函数棵理解为将p结点插入到pro0所指向 的树中
4 对二叉树最重要的是根，它起定位的作用，因此，首先 建立的是根结点。也就是说，如果从键盘输入数据来 建立二叉树，第一个数据就是这棵树的根的数据，之 后再输入的数据，每一个都要与根中的数据作比较， 以便确定该数据所在结点的插入位置。假定我们这里 依然用图1的中序遍历的方式。即如果待插入结点的 数据比根结点的数据小，则将其插至左子树，否则插 入右子树。 定义一个递归函数 void insert(struct TREE **proot, struct TREE *p) 其中，指针p指向含有待插入数据的结点。 proot为树的根指针的地址。 insert函数棵理解为将p结点插入到*proot所指向 的树中
insert( proot, p)可用下列与或结点图来描述 insert(proot, p) 根结点为空 根结点不空, proot==nur 树已存在 图3 将结点p插入根结点 *=p: return 返回 和>data>(Rroo->data p->data<=(proot)->data insert(&((proot)->R),P); nser&(*pro->L),p);将p结点插入右子树 将p结点插入左子树
5 insert(proot, p)可用下列与或结点图来描述 insert(proot,p) 将结点p插入根结点 *proot=p; return; 返回 C 根结点不空， 树已存在 根结点为空 *proot==null p->data<=(*proot)->data insert(&((*proot)->R),p); 将p结点插入右子树 图3 p->data> (*proot)->data insert(&((*proot)->L),p); 将p结点插入左子树