数据结构实验: 二进制排序树

****************************** /

//定义数据结构

struct NODE

{

int数据；

节点*左；

节点*对；

};

/ *************************

*定义是否找到徽标.

我认为递归用法不应包含cout之类的输出语句，

因为递归调用将导致递归输出，

因此定义一个标志

在此处使用全局变量不是很好

但是为了简单起见，仅此而已！ ！ ！

****************************** /

int标志= 0;

//整个程序被封装到一个类中

类树

{

公开

:

树（）;

//根据整数数组和该数组的元素构造一棵树

void buildTree（int data []，int n）;

//三种遍历方法.

void preorder（）;

void inorder（）;

void postorder（）;

//查找功能

无效搜索（int temp）;

私人:

//用于遍历树的辅助功能

void recursive_inorder（节点*根）；

void recursive_preorder（NODE * root）;

void recursive_postorder（节点*根）；

void recursive_search（NODE * root，int temp）;

/ ********************************************

这称为插入函数，在构造树时需要

要构建二进制排序树，我在这里使用递归.

请注意我在这里使用双指针，因为我想在根目录中插入值！

但是，我们知道要更改root的值，必须使用指针（地址）.

否则，作为形式参数操作，保留该函数不会更改形式参数的值.

********************************************* /

无效插入（节点**树数据结构二叉排序树，整数键）；

节点*根; //树根

};

//在构造函数中将root设置为NULL

树::树（）

{

root = NULL;

}

无效树::插入（节点**树，整数键）

{

如果（* tree == NULL）

{

/ ***************************

请注意此处的用法，我们必须使用（*树），

因为定义了双指针，

我们要操作的是地址中的内容！

**************************** /

*树=新节点（）;

（*树）-> data =键;

（*树）->左= NULL;

（*树）->右= NULL;

返回；

}

如果（键<（*树）->数据）

{

/ *****************

递归用法，如果您不理解，

所以我们先来看一下递归！

*********************** /

插入（＆（*树）->左键）;

}

其他

{

/ *****************

递归用法，如果您不理解，

所以我们先来看一下递归！

*********************** /

插入（＆（*树）->右键）;

}

}

/ ********************

这是使用递归函数insert（）构建树！

根据比较数组的值的大小，动态插入它.

************************* /

void Tree :: buildTree（int数据[]，int n）

{

cout <<“开始构建排序的二叉树...” << endl << endl;

for（int i = 0; i

{

插入（＆根，数据[i]）；

}

cout <<“排序的二叉树的构建完成了……” << endl << endl;

}

// [顺序遍历]层次二叉树

void Tree ::预订（）

{

cout <<“顺序遍历...” << endl;

recursive_preorder（root）;

cout << endl;

}

// [第一次遍历]分层二叉树的辅助方法.

空树:: recursive_preorder（NODE * root）

{

节点* p =根; //以根节点进行操作.

//打印当前访问的节点

如果（p！= NULL）

{

cout << p->数据<<“->”; //访问（）

}

/ *******************

递归遍历左右子树，

在左右子树访问NULL的情况下

*********************** /

如果（p->向左！= NULL）

{

recursive_preorder（p->向左）;

}

如果（p->对！= NULL）

{

recursive_preorder（p->向右）;

}

}

// [序列遍历]层次二叉树

无效树:: inorder（）

{

cout <<“有序遍历...” << endl;

recursive_inorder（根）；

cout << endl;

}

//层次二叉树的[中间遍历]辅助功能

空树:: recursive_inorder（节点*根）

{

节点* p =根; //以根节点进行操作.

/ *******************

首先转到最左侧的子树，

直到访问NULL，

那是左子树的结尾

返回

开始访问该节点.

*********************** /

如果（p == NULL）

{

返回；

}

/ *******************

首先遍历最左边的节点，

然后，访问该节点，

如果节点不为NULL，

只需[递归遍历]左，中和右节点.

*********************** /

如果（p->向左！= NULL）

{

recursive_inorder（p->向左）;

}

cout << p->数据<<“->”; //访问（）

如果（p->对！= NULL）

{

recursive_inorder（p->向右）;

}

}

// [后遍历]分层二叉树

void Tree ::后继（）

{

cout <<“后序遍历...” << endl;

recursive_postorder（根）；

cout << endl;

}

//分层二叉树的[后遍历]辅助功能.

无效树:: recursive_postorder（节点*根）

{

节点* p =根; //以根节点进行操作.

/ *******************

首先转到最左侧的子树，

直到访问NULL，

那是左子树的结尾

返回

开始访问该节点.

*********************** /

如果（p == NULL）

{

返回；

}

/ *******************

首先遍历最左边的节点，

然后，访问该节点数据结构二叉排序树，

如果节点不为NULL，

只需[递归遍历]左，中和右节点.

*********************** /

如果（p->向左！= NULL）

{

recursive_postorder（p->左）;

}

如果（p->对！= NULL）

{

recursive_postorder（p->向右）;

}

cout << p->数据<<“->”; //访问（）

}

无效树:: :: recursive_search（节点*根，整数温度）

{

/ *******************

使用顺序遍历进行搜索！

*********************** /

节点* p =根; //以根节点进行操作.

//转到当前节点，如果它等于要搜索的值，则将其标记.

如果（p！= NULL）

{

如果（p->数据==温度）

flag = 1;

}

如果（p->向左！= NULL）

{

recursive_search（p->左侧，临时）；

}

如果（p->对！= NULL）

{

recursive_search（p->正确，临时）；

}

}

空树::搜索（临时）

{

//使用recursive_search进行递归搜索.

recursive_search（根目录，临时目录）；

}

void main（）

{

int数据[10] = {8,3,6,1,5,2,9,7,4,0}; //定义一个数组.

树；

tree.buildTree（data，10）; //构建树

/ ****************************************

通过三种方式遍历我们构造的分类二叉树！

************************************ /

tree.inorder（）;

tree.preorder（）;

tree.postorder（）;

int temp;

cout <<“请输入要查找的值: ” << endl;

cin >> temp;

tree.search（temp）; //开始搜索

开关（标志）

{

情况1:

cout <<“得到它...” << endl << endl;

休息；

情况0:

cout <<“无法获取...” << endl << endl;

休息；

}

}

================================================ ======================================

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-191388-1.html