第十二讲 ●二叉树的建立 ●循环链表
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->datadata 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->datadata insert(&((*proot)->R),p); 将p结点插入右子树 图3 p->data> (*proot)->data insert(&((*proot)->L),p); 将p结点插入左子树
注意在上图中pro是被调用函数的形参。从前面对它 的定义看, proot是指针的指针,实际上是指向二叉 树根结点的指针的指针,或者说是指向二叉树根结点 的指针的地址。如下图。因此,在主程序调用 Insert 函数时, 实参 根结点 &root proot 实参为&root,p 形参为 proot,p 下面是建立二叉树的参考程序
6 注意在上图中proot是被调用函数的形参。从前面对它 的定义看，proot是指针的指针，实际上是指向二叉 树根结点的指针的指针，或者说是指向二叉树根结点 的指针的地址。如下图。因此，在主程序调用insert 函数时， 根结点 proot 实参 &root 实参为 &root, p 形参为 proot, p 下面是建立二叉树的参考程序
#include ∥内存空间分配 #define null o ∥定义空指针常量 # define len sizeof( struct TREE)∥定义常量,表示结构长度 struct TREE ∥结构声明 int data: ∥整型数 struct TREE *L*R: ∥TREE结构指针
7 #include // 预编译命令 #include // 内存空间分配 #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 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 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函数，输出二叉树内容 } // 主函数结束