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