二叉树的建立.ppt

说明： 1、由于getchar()返回的是整数（ASCII码值）,因此，temp定义为整数型。 2、EOF被定义为-1，当getchar()函数返回-1时结束，这里EOF被定义为-1，在DOS系统中只有用Ctrl+Z才能结束键盘输入。从实验中可以看出getchar()函数是将键盘输入的字符的ASCII码的形式存至缓冲区，敲入字符之后，须回车才响应输出 a // 敲入的小写字符 temp = 97 // 回车之后，输入’a’的ASCII码 A // 回应大写字符’A’， temp = 10 // 输出回车键的ASCII码值 3、在上述程序基础上，将getchar改为getch，观察程序运行情况。这时不再显示敲入的小写字母，屏幕上看到的都是大写字母了。但显示的ASCII码值仍是小写字母的码值。 退出方式用Ctrl+Break 4、将getch改为getche再试，观察有何变化？ 5、字符串的读写函数gets()和puts()。 * * 二叉树的建立 循 环 链 表 文 件 操 作 二叉树的建立 二叉树的建立 建立二叉树的过程是一个“插入”过程，下面我们用一个例子来讲解这一过程。 我们想建立这样一棵二叉树，树中的每一个结点有一个整数数据名为data，有两个指针：左指针L，右指针R，分别指向这个结点的左子树和右子树，显然可以用如下名为TREE的结构来描述这种结点： struct TREE { int data; struct TREE *L, *R; } 对二叉树最重要的是根，它起定位的作用，因此，首先建立的是根结点。也就是说，如果从键盘输入数据来建立二叉树，第一个数据就是这棵树的根的数据，之后再输入的数据，每一个都要与根中的数据作比较，以便确定该数据所在结点的插入位置。假定我们这里依然用图1的中序遍历的方式。即如果待插入结点的数据比根结点的数据小，则将其插至左子树，否则插入右子树。 定义一个递归函数 void insert(struct TREE **proot, struct TREE *p) 其中，指针p指向含有待插入数据的结点。 proot为树的根指针的地址。 insert函数棵理解为将p结点插入到*proot所指向的树中。 insert(proot, p)可用下列与或结点图来描述 注意在上图中proot是被调用函数的形参。从前面对它的定义看，proot是指针的指针，实际上是指向二叉树根结点的指针的指针，或者说是指向二叉树根结点的指针的地址。如下图。因此，在主程序调用insert函数时， 根结点 proot 实参 root 实参为 root, p 形参为 proot, p 下面是建立二叉树的参考程序。 #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); // 插入右子树 } } // 函数体结束 // 被调用函数，形参为TREE结构指针，输出二叉树内容 void print(struct TREE *root) { // 函数体开始 if (root == null) // 根或子树根结点为空 return; // 返回 print(root-L); // 输出左子树内容 printf(%d,root-data);// 输出根结点内容 print(root-R); // 输出右子树内容 } // 被调用函数结束 void main()