注意在上图中pro是被调用函数的形参。从前面对它 的定义看, proot是指针的指针,实际上是指向二叉 树根结点的指针的指针,或者说是指向二叉树根结点 的指针的地址。如下图。因此,在主程序调用 Insert 函数时, 实参 根结点 &root proot 实参为&root,p 形参为 proot,p 下面是建立二叉树的参考程序
6 注意在上图中proot是被调用函数的形参。从前面对它 的定义看，proot是指针的指针，实际上是指向二叉 树根结点的指针的指针，或者说是指向二叉树根结点 的指针的地址。如下图。因此，在主程序调用insert 函数时， 根结点 proot 实参 &root 实参为 &root, p 形参为 proot, p 下面是建立二叉树的参考程序
#include <stdio. hi ∥预编译命令 #include <malloc.h> ∥内存空间分配 #define null o ∥定义空指针常量 # define len sizeof( struct TREE)∥定义常量,表示结构长度 struct TREE ∥结构声明 int data: ∥整型数 struct TREE *L*R: ∥TREE结构指针
7 #include <stdio.h> // 预编译命令 #include <malloc.h> // 内存空间分配 #define null 0 // 定义空指针常量 #define LEN sizeof(struct TREE) // 定义常量，表示结构长度 struct TREE // 结构声明 { int data; // 整型数 struct TREE *L,*R; // TREE结构指针 };
∥被调用函数 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 // 被调用函数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); // 插入右子树 } } // 函数体结束
∥被调用函数,形参为TREE结构指针,输出二叉树内容 void print(struct TREE * root) ∥函数体开始 if (root == null) ∥根或子树根结点为空 return: ∥返回 print(root-> L); ∥输出左子树内容 printf("%d",root->data);/输出根结点内容 print(root->R) ∥输出右子树内容 ∥被调用函数结束 void maino ∥主函数开始 ∥函数体开始 struct TREE*root,*p;∥TREE型结构指针 int temp ∥临时变量,用于用户输入数据 root= null: ∥初始化二叉树根结点为空 p= null: ∥初始化待插入结点的指针为空 printi("请输入待插入结点的数据n");∥提示信息 printi("如果输入-1表示插入过程结束n");∥提示信息 scanf("%d",&temp);∥输入待插入结点数据
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",&temp); // 输入待插入结点数据
while(temp!=-1) ∥当型循环,-1为结束标志 ∥循环体开始 ∥/为待插入结点分配内存单元 p=(struct TREE*) malloc(LeN); p>data=temp;∥将temp赋值给p结点的数据域 p>L=p->R=nuli∥将p结点的左右指针域置为空 insert(&root,p);∥将p结点插入到根为root的树中 ∥/&root表示二叉树根结点的地址 printi('"请输入待插入结点的数据m");∥提示信息 printi("如果输入-1表示插入过程结束m");/提示信息 scant("%d,&temp);∥输入待插入结点数据 ∥循环体结束 if (root==null ∥如果根结点为空 printf("这是一棵空树。Ⅶ");∥输出空树信息 eise ∥根结点不为空 print(root); ∥调用 print函数,输出二叉树内容 ∥主函数结束
10 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的树中， // &root表示二叉树根结点的地址 printf("请输入待插入结点的数据\n"); // 提示信息 printf("如果输入-1表示插入过程结束\n");// 提示信息 scanf("%d",&temp); // 输入待插入结点数据 } // 循环体结束 if (root==null) // 如果根结点为空 printf("这是一棵空树。\n");// 输出空树信息 else // 根结点不为空 print(root); // 调用print函数，输出二叉树内容 } // 主函数结束