实验五 二叉树基本操作的编程实现

【实验目的】

内容：二叉树基本操作的编程实现

要求：

二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

验证性实验（学时数：2H）

【实验内容】

以下的选题都可以作为本次实验的推荐题目

1. 建立二叉树，并以前序遍历的方式将结点内容输出。

2. 将一个表示二叉树的数组结构转换成链表结构。

3. 将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序及后序遍历结果，并计算出表达式之结果。

【思考问题】

1. 二叉树是树吗？它的定义为什么是递归的？

2. 三种根序遍历主要思路是什么？

3. 如果不用遍历算法一般启用什么数据结构实现后序遍历？

4. 举出二叉树的应用范例？

【参考代码】

（一）建立二叉树，并以前序遍历的方式将结点内容输出*/

/*===============================================*/ /*程序构思： */ /*输入元素值后建立二叉树，以递归的方式做前序遍历，*/ /*其顺序为：结点－左子－右子树，并将二叉树结点内容输出。*/ #include<stdlib.h> #include<stdio.h> struct tree /*声明树的结构 */ { struct tree *left; /*存放左子树的指针 */ int data; /*存放结点数据内容 */ struct tree *right; /*存放右子树的指针 */ }; typedef struct tree treenode; /*声明新类型树结构 */ typedef treenode *b_tree; /*声明二叉树的链表 */ /*===============================================*/ /*插入二叉树结点 */ /*===============================================*/ b_tree insert_node (b_tree root, int node) { b_tree newnode; /*声明树根指针 */ b_tree currentnode; /*声明目前结点指针 */ b_tree parentnode; /*声明父结点指针 */

/*建立新结点的内存空间 */ newnode=(b_tree )malloc (sizeof(treenode)); newnode->data=node; /*存入结点内容 */ newnode->right=NULL; /*设置右指针初值 */ newnode->left=NULL; /*设置左指针初值 */ if (root==NULL) return newnode; /*返回新结点的位置 */ else { currentnode=root; /*存储目前结点指针 */ while (currentnode!=NULL) { parentnode=currentnode; /*存储父结点指针 */ if (currentnode->data>node) /*比较结点的数值大小 */ currentnode=currentnode->left; /*左子树 */ else currentnode=currentnode->right; /*右子树 */ } if (parentnode->data>node) /*将父结点和子结点做连结*/ parentnode->left=newnode; /*子结点为父结点之左子树*/ else parentnode->right=newnode; /*子结点为父结点之右子树*/ }return root; /*返回根结点之指针 */ } /*===============================================*/ /*建立二叉树 */ /*===============================================*/ b_tree create_btree (int *data, int len) { b_tree root=NULL; /*根结点指针 */ int i; for (i=0; i<len; i++) /*建立树状结构 */ root=insert_node(root, ); return root; } /*===============================================*/ /*二叉树前序遍历 */ /*===============================================*/ void preorder (b_tree point) { if (point!=NULL) /*遍历的终止条件 */ { printf ("%2d", point->data); /*处理打印结点内容 */ preorder (point->left); /*处理左子树 */ /*处理右子树 */ } } /*==================================================*/ /*主程序：建立二叉树，并以前序遍历输出二叉树结点内容*/ /*==================================================*/ void main() { b_tree root=NULL; /*树根指针 */ int i, index; int value; /*读入输入值所使用的暂存变量*/ int nodelist[20]; /*声明存储输入数据之数组*/ printf ("\n Please input the elements of binary tree(Exit for 0): \n"); index=0;

/*------------------读取数值存到数组中------------------*/ scanf ("%d", &value); /*读取输入值存到变量value*/

while (value!=0) {

nodelist[index]=value; } scanf ("%d", &value);

/*----------------------root=create_btree(nodelist, index); 建立二叉树----------------------*/

/*--------------------前序遍历二叉树--------------------*/

printf ("\n The preorder traversal result is ("); } printf (") \n");

/*

/*Please input the elements of binary tree(Exit for 0): 希望的结果 /*6 3 1 9 5 7 4 8 0 /* /*The preorder traversal result is (6 3 1 5 4 9 7 8) */ */ */

（二）将一个表示二叉树的数组结构转换成链表结构

/*===============================================*/ /*/*程序构思：

/*给定一个二叉树数组结构，使用递归方式建立一棵二叉树， */ */ 并中序遍历的方式输出二叉树结点内容。*/

#include <stdlib.h> #include <stdio.h> struct tree { /*声明树的结构 */

struct tree *left; int data; /* 存放左子树的指针 */ }; struct tree *right; /*存放右子树的指针/*存放结点数据内容 */ */ typedef struct tree treenode; typedef treenode *b_tree; /*声明新类型树结构

/*声明二叉树的链表 */ */ /*===============================================*/ /*/*===============================================*/ 使用递归建立树状结构 */

b_tree create_btree (int *nodelist, int position) { b_tree newnode; /*声明新结点指针 */

if (nodelist[position]==0 || position>15) /*递归的终止条件*/

return NULL;

else

{ /*----------------建立新结点的内存空间----------------*/

newnode=(b_tree) malloc (sizeof(treenode));

/*--------------------建立结点内容--------------------*/

newnode->data=nodelist[position];

/*-------------------newnode->left=create_btree(nodelist, 2*position); 递归建立左子树-------------------*/

/*-------------------递归建立右子树-------------------*/ */ */

return newnode; /*返回复制树的位置 */ } } /*===============================================*/ /*二叉树中序遍历打印结点内容 */ /*===============================================*/ void inorder_print_btree (b_tree point) { if (point!=NULL) /*遍历的终止条件 */ { / *处理左子树 */ /*处理打印结点内容 */ inorder_print_btree(point->right); /*处理右子树 */ } } /*================================================*/ /*主程序：建立链表二叉树，并以中序遍历打印结点内容*/ /*================================================*/ void main() { b_tree root=NULL; /*树根指针 */ int i; /*----------------声明二叉树数组结点数据----------------*/ int nodelist[16]={0,5,2,9,1,4,7,0,0,0,3,0,6,8,0,0}; /*---------------------建立树状结构---------------------*/ root=create_btree(nodelist, 1); /*----------------打印原数组中的结点内容----------------*/ printf ("\n The node content of array_structure is: \n"); for (i=0; i<16; i++) printf ("[%2d]", nodelist[i]); printf ("\n"); /*------------打印树状结构（链表）的结点内容------------*/ printf ("\n The node content of linklist_structure is: \n"); ); printf ("\n"); } /*希望的结果 */ /*The node content of array_structure is: */ /*[0] [5] [2] [9] [1] [4] [7] [0] [0] [0] [3] [0] [6] [8] [0] [0]*/ /* */ /*The node content of linklist_structure is: */ /*[1] [2] [3] [4] [5] [6] [7] [8] [9] */ （三）二叉树的应用

/*程序构思： */ /*将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，*/ /*再分别输出前序、中序及后序遍历结果，并计算出表达式之结果。*/ #include <stdlib.h> #include <stdio.h> struct tree /*声明树的结构 */ { struct tree *left; /*存放左子树的指针 */ char data; /*存放结点数据内容 */ struct tree *right; /*存放右子树的指针 */ }; typedef struct tree treenode; /*声明新类型树结构 */ typedef treenode *b_tree; /*声明二叉树的链表 */ /*===============================================*/

/*使用递归建立二叉树 */ /*===============================================*/ b_tree create_btree (int *nodelist, int position) { b_tree newnode; /*声明新结点指针 */ if (nodelist[position]==0 || position>7) /*递归的终止条件*/ return NULL; else { /*----------------建立新结点的内存空间----------------*/ newnode=(b_tree) malloc (sizeof(treenode)); /*--------------------建立结点内容--------------------*/ newnode->data=nodelist[position]; /*-------------------递归建立左子树-------------------*/ newnode->left=create_btree(nodelist, 2*position); /*-------------------递归建立右子树-------------------*/ return } } /*===============================================*/ /*二叉树前序遍历打印结点内容 */ /*===============================================*/ void preorder (b_tree point) { if (point!=NULL) /*遍历的终止条件 */ { printf ("%2c", point->data); /*处理打印结点内容 */ preorder(point->left); /*处理左子树 */ preorder(point->right); /*处理右子树 */ } } /*===============================================*/ /*二叉树中序遍历打印结点内容 */ /*===============================================*/ void inorder (b_tree point) { if (point!=NULL) /*遍历的终止条件 */ { inorder(point->left); /*处理左子树 */ printf ("%2c", point->data); /*处理打印结点内容 */ inorder(point->right); /*处理右子树 */ } } /*===============================================*/ /*二叉树后序遍历打印结点内容 */ /*===============================================*/ void postorder (b_tree point) { if (point!=NULL) /*遍历的终止条件 */ { postorder(point->left); /*处理左子树 */ postorder(point->right); /*处理右子树 */ printf ("%2c", point->data); /*处理打印结点内容 */ } } /*===============================================*/ /*计算表达式结果值 */ /*===============================================*/

int calculate(b_tree point) { int oper1=0; /*前操作数变量 */ int oper2=0; /*后操作数变量 */ if (point->left==NULL && point->right==NULL) return else { oper1=calculate(point->left); /*左子树 */ oper2=calculate(point->right); /*右子树 */ return get_value(point->data, oper1, oper2); } } /*===============================================*/ /*抽取运算值并计算 */ /*===============================================*/ int get_value(int oper, int oper1, int oper2) { switch ((char)oper) { case '*' : return (oper1*oper2); case '/' : return (oper1/oper2); case '+' : return (oper1+oper2); case '-' : return (oper1-oper2); } } /*================================================*/ /*主程序：建立表达式二叉树，并计算结果 */ /*================================================*/ void main() { b_tree root=NULL; /*声明表达式二叉树指针 */ int cal_result; /*计算结果 */ /*----------------声明二叉树数组结点数据----------------*/ int nodelist[8]={' ','+','*','/','4','8','6','2'}; root=create_btree(nodelist, 1); /*建立表达式二叉树 */ /*----------------前序打印----------------*/ printf ("\n Preorder expression: ["); preorder(root); printf ("]\n"); /*----------------中序打印----------------*/ printf ("\n Inorder expression: ["); inorder(root); printf ("]\n"); /*----------------后序打印----------------*/ printf ("\n Postorder expression: ["); postorder(root); printf ("]\n"); /*------------计算表达式结果------------*/ cal_result=calculate(root); printf ("\n Calculate result is [%2d] \n", cal_result); } /*希望的结果 */ /*Preorder expression: [+ * 4 8 / 6 2] */ /*Inorder expression: [4 * 8 + 6 / 2] */ /*Postorder expression: [4 8 * 6 2 / +] */ /* */ /*Calculate result is [35] */

【实验小结】 (总结本次实验的重难点及心得、体会、收获)

得 分_____________

评阅日期_____________

教师签名__ __________