文档介绍：1二叉树的建立二叉树的建立循循环环链链表表文文件件操操作作 2二叉树的建立二叉树的建立 3 二叉树的建立建立二叉树的过程是一个“插入”过程,下面我们用一个例子来讲解这一过程。我们想建立这样一棵二叉树,树中的每一个结点有一个整数数据名为 data ,有两个指针:左指针 L,右指针R,分别指向这个结点的左子树和右子树,显然可以用如下名为 TREE 的结构来描述这种结点: struct TREE { int data; struct TREE * L, * R; } 4 对二叉树最重要的是根,它起定位的作用,因此,首先建立的是根结点。也就是说,如果从键盘输入数据来建立二叉树,第一个数据就是这棵树的根的数据,之后再输入的数据,每一个都要与根中的数据作比较, 以便确定该数据所在结点的插入位置。假定我们这里依然用图 1的中序遍历的方式。即如果待插入结点的数据比根结点的数据小,则将其插至左子树,否则插入右子树。定义一个递归函数 void insert(struct TREE ** proot , struct TREE * p) 其中,指针 p指向含有待插入数据的结点。 proot 为树的根指针的地址。 insert 函数棵理解为将 p结点插入到* proot 所指向的树中。 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结点插入左子树 6 注意在上图中 proot 是被调用函数的形参。从前面对它的定义看, proot 是指针的指针,实际上是指向二叉树根结点的指针的指针,或者说是指向二叉树根结点的指针的地址。如下图。因此,在主程序调用 insert 函数时, 根结点 proot 实参&root 实参为&root, p 形参为 proot ,p下面是建立二叉树的参考程序。 7 #include < > // 预编译命令#include < > // 内存空间分配#define null 0 // 定义空指针常量#define LEN sizeof(struct TREE) // 定义常量,表示结构长度 struct TREE // 结构声明{ int data; // 整型数 struct TREE * L,* R; // TREE 结构指针}; 8 // 被调用函数 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); // 插入右子树}} // 函数体结束 9 // 被调用函数,形参为 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",&