文档介绍：第十二讲
二叉树的建立
循环链表
1
二叉树的建立
2
二叉树的建立
建立二叉树的过程是一个“插入”过程,下面我们用一个例子来讲解这一过程。
我们想建立这样一棵二叉树,树中的每一个结点有一个整数数据名为data,有两个指针:左指针L,右指针R,分别指向这个结点的左子树和右子树,显然可以用如下名为TREE的结构来描述这种结点:
struct TREE
{
int data;
struct TREE *L, *R;
}
3
对二叉树最重要的是根,它起定位的作用,因此,首先建立的是根结点。也就是说,如果从键盘输入数据来建立二叉树,第一个数据就是这棵树的根的数据,之后再输入的数据,每一个都要与根中的数据作比较,以便确定该数据所在结点的插入位置。假定我们这里依然用图1的中序遍历的方式。即如果待插入结点的数据比根结点的数据小,则将其插至左子树,否则插入右子树。
定义一个递归函数
void insert(struct TREE **proot, struct TREE *p)
其中,指针p指向含有待插入数据的结点。
proot为树的根指针的地址。
insert函数棵理解为将p结点插入到*proot所指向的树中。
4
insert(proot, p)可用下列与或结点图来描述
5
注意在上图中proot是被调用函数的形参。从前面对它的定义看,proot是指针的指针,实际上是指向二叉树根结点的指针的指针,或者说是指向二叉树根结点的指针的地址。如下图。因此,在主程序调用insert函数时,
根结点
proot
实参
&root
实参为&root, p
形参为 proot, p
下面是建立二叉树的参考程序。
6
#include <> // 预编译命令
#include <> // 内存空间分配
#define null 0 // 定义空指针常量
#define LEN sizeof(struct TREE) // 定义常量,表示结构长度
struct TREE // 结构声明
{
int data; // 整型数
struct TREE *L,*R; // TREE结构指针
};
7
// 被调用函数insert,将结点插入二叉树
void insert (struct TREE **proot, struct TREE* p)
{ // 函数体开始
if (*proot==null) // 如果根结点为空
{
*proot = p; // 将结点p插入根结点
return; // 返回
}
else // 根结点不为空
{
// 如果p结点数据小于等于根结点数据
if (p->data <= (*proot)->data)
insert( &((*proot)->L), p); // 插入左子树
else // 如果p结点数据大于等于根结点数据
insert( &((*proot)->R), p); // 插入右子树
}
} // 函数体结束
8
// 被调用函数,形参为TREE结构指针,输出二叉树内容
void print(struct TREE *root)
{ // 函数体开始
if (root == null) // 根或子树根结点为空
return; // 返回
print(root->L); // 输出左子树内容
printf("%d",root->data);// 输出根结点内容
print(root->R); // 输出右子树内容
} // 被调用函数结束
void main() // 主函数开始
{ // 函数体开始
struct TREE *root, *p; // TREE型结构指针
int temp; // 临时变量,用于用户输入数据
root = null; // 初始化二叉树根结点为空
p = null; // 初始化待插入结点的指针为空
printf("请输入待插入结点的数据\n"); // 提示信息
printf("如果输入-1表示插入过程结束\n");// 提示信息
scanf("%d",&temp); // 输入待插入结点数据
9
while(temp != -1) // 当型循环,-1为结束标志
{ // 循环体开始
// 为待插入结点分配内存单元
p = (struct TREE *) malloc(LEN);
p->data = temp; // 将temp赋值给p结点的数据域
p->L = p->R = null; // 将p结点的左右指针域置为空
insert( &root, p ); // 将p结点插入到根为root的树中