p5.cpp

创建二叉树修改二叉树添加二叉树删除二叉树

/*
	源文件名：P5.cpp
	功能：二叉树操作
*/
#include <iostream.h>
#include <iomanip.h>
#include <conio.h>
#include <stdio.h>
#include <process.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct BiTNode        //二叉树结点类型
{
	int data;         //数据
	int tem1,tem2;    //辅助数据（实习题不用）
	BiTNode *left;    //左子树指针
	BiTNode *right;   //右子树指针
};

BiTNode *Tree;      //本程序操作的二叉树根指针
#define LEN sizeof(BiTNode)
typedef int Status ;
const max=100;
int elem[max],list[max],b=0;        //存放原始数据
int counter=0;
void wait()
{
	cout << "\n\n请按任意键继续" << flush;
	getch();
}
//从键盘输入个数和随机数种子，在数组elem中生成指定个数的数据，供其他程序使用，0表示数据结束
void init0(int elem[]);

//在本程序所在的位置生成文本文件Map.txt，其中显示以Tree为根指针的二叉树      
void showBinTree(BiTNode *Tree);

//从键盘输入个数和随机数种子，以Tree为根指针，生成指定结点个数的二叉树，供其他程序使用
BiTNode *init1();   
void PreOrderTraverse(BiTNode *Tree);
void InOrderTraverse(BiTNode *Tree);
void PostOrderTraverse(BiTNode *Tree);
void BuildsortTree(int x);
void BinarysortTree(BiTNode *Tree);
void SearchTree(BiTNode *Tree);
void DeleteTree(BiTNode *Tree);

//主函数，显示功能菜单（包括生成二叉树、显示二叉树），键盘选择后执行对应功能
void main()
{
	char choice;
	while (1)
	{
		system("cls");
		cout << "\n\n\n\n";
		cout << "\t\t            二叉树操作  \n";
		cout << "\t\t======================================";
		cout << "\n\n";
		cout << "\t\t             1：初始化      \n";
		cout << "\t\t             2：显示        \n";
		cout << "\t\t             3：先序遍历以Tree为根指针的二叉树    \n";
		cout << "\t\t             4：中序遍历以Tree为根指针的二叉树           \n";
		cout << "\t\t             5：后序遍历以Tree为根指针的二叉树       \n";
		cout << "\t\t             6：生成以Tree为根指针的二叉排序树        \n";
		cout << "\t\t             7：查找结点        \n";
		cout << "\t\t             8：删除结点      \n";
		cout << "\t\t             0：退出        \n";
		cout << "\n";
		cout << "\t\t请选择：" << flush;

		choice = getch();
		system("cls");
		
		switch(choice)
		{
			case '1':
				init0(elem);
				
				break;
			case '2':
				showBinTree(Tree);
				break;
			case '3':
				PreOrderTraverse(Tree);
				wait();
				break;
			case '4':
				InOrderTraverse(Tree);
				wait();
				break;
			case '5':
				PostOrderTraverse(Tree);
				wait();
				break;
			case'6':
				Tree=NULL;
                BinarysortTree(Tree);
                showBinTree(Tree);
                b=1;
				wait();
				break;
			case'7':
				SearchTree(Tree);
                break;
			case'8':
				DeleteTree(Tree);
				break;
			
			case '0':
				exit(0);
		}
	}
  
}

#include "BinT.h"


//先序、中序、后序遍历以Tree为根指针的二叉树

//使用数组elem中的随机数序列（以0表示结束，不包括0），生成以Tree为根指针的二叉排序树

//在以Tree为根指针的二叉排序树中查找结点

//从以Tree为根指针的二叉排序树中删除结点（适用各种位置的结点）

//对以Tree为根指针的二叉树,从根结点开始，逐层从左到右输出各结点的数据
//提示：用数组 BiTNode *queue[max] 构成队列，利用这个队列实现功能

//*1、随机生成二叉树。 2、生成并保存先（后）序、中序输出序列。 3、按照保存的一对输出序列恢复出二叉树。 4、生成先（后）序、中序输出序列。 5、比较两对输出序列。

//*不用递归，先序、中序、后序遍历以Tree为根指针的二叉树
//提示：用数组 BiTNode *stack[max] 构成堆栈，利用这个堆栈实现功能

//*用缩入格式的多行文本表示以Tree为根指针的二叉树，例如：
//  324
//     123
//      746
//      690
//     567

//*用广义表表示以Tree为根指针的二叉树，例如
// (324(123(746()())(690()()))(567()()))

//*使用数组elem中的随机数序列（以0表示结束，不包括0），生成赫夫曼树，计算平均带权路径长度