我去，很惊恐啊，我就先放上边一晚上，俺还没写完就几十观看了
再看可不带白嫖的嗷
我还没写完没写完没写完！！！！
就是我们写以下代码的模型
递归实现的二叉树的三种遍历和复制删除
#include<iostream>//递归实现二叉树的简单的创建，三种查询方式，复制及复制后的迅速删除它（手动狗头）
#include<stdlib.h>//使用malloc需调用此头文件
using namespace std;
typedef struct BINARYNODE {//就是创建二叉树的一个节点，使用链式存储的方法
char ch;
struct BINARYNODE* lchild;//存放左子树
struct BINARYNODE* rchild;//存放右子树
}BinaryNode;
void menu(void);
void caidancaozuo(BinaryNode *root);
void CreateBinaryTree();//创建一个子树
//先序遍历
void Recursion(BinaryNode* root);
//inorder(中序遍历)
void Inorder(BinaryNode* root);
//后序遍历
void Postorder(BinaryNode* root);
//求叶子节点的总数
void sumleaf(BinaryNode* root, int& num);
//求高度
int qiugao(BinaryNode* root);
//复制二叉树
BinaryNode* CopyBinaryNode(BinaryNode* root);//其实我们在创建的时候就立马删除了
//释放节点所创建的空间
void FreeSpaceCopyBinaryNode(BinaryNode* root);
int main(void)
{
cout<<"抱歉我们必须先创建一个二叉树才能进行后续的操作"<<endl;
menu();
cout<<"抱歉以下的操作是基于我们已经创建的二叉树上进行操作的"<<endl;
CreateBinaryTree();
}
void menu(void)
{ //很经典的菜单形式
char a01[] = "（1）先序遍历二叉树";
char a02[] = "（2）中序遍历二叉树";
char a03[] = "（3）后序遍历二叉树";
char a04[] = "（4）求此二叉树的叶子节点总数";
char a05[] = "（5）求此二叉树的高度";
char a06[] = "（6）复制此二叉树，并返回复制后的先序的查询结果,然后我们便会把它删除";
char a07[] = "（额外的菜单）出入任意不在前面菜单的数字将结束程序";
printf("%-50s", a01);
printf("%-50s\n", a02);
printf("%-50s", a03);
printf("%-50s\n", a04);
printf("%-50s", a05);
printf("%-50s\n", a06);
printf("%-50s\n", a07);
}
void caidancaozuo(BinaryNode* root)//再次自我感觉良好觉得这个自我调用也不赖，放前边了
{
cout << "请问你想选择哪个指令" << endl;
int mingling;
cin >> mingling;
// cout<<endl;
switch (mingling)
{
case 1:
{
Recursion(root);
cout<<endl;//为了使界面更好看所以加上了这行
caidancaozuo(root);
break;
}
case 2:
{
Inorder(root);
cout<<endl;
caidancaozuo(root);
break;
}
case 3:
{
Postorder(root);
cout<<endl;
caidancaozuo(root);
break;
}
case 4:
{
int num=0;//这行必须创建在外面
sumleaf(root,num);
cout << "您的二叉树里的叶子的总数有" << num << "个" << endl;
caidancaozuo(root);
break;
}
case 5:
{
int gaodu = qiugao(root);
cout << "您的二叉树的高度是" << gaodu << endl;
caidancaozuo(root);
break;
}
case 6:
{
BinaryNode* test = CopyBinaryNode(root);
cout << "复制后的二叉树为" << endl;
Recursion(test);
cout<<endl;
FreeSpaceCopyBinaryNode(test);//创建后立马删除的原因是我们复制得来的二叉树是完全利用的链式
//和在Create函数里的二叉树的创建稍微有些不同，传入不到下一个函数里
//属于是在构建函数时的失误但我不想改了
caidancaozuo(root);
break;
}
default:
cout << "您已经决定退出此程序，程序即将退出" << endl;
break;
}
}
void CreateBinaryTree() {
//创建一个二叉树是很难的，以后会单独的再写一期，这个就手动的写上了，模型在文章的开头
//建立节点
BinaryNode node1 = { 'A',NULL,NULL };
BinaryNode node2 = { 'B',NULL,NULL };
BinaryNode node3 = { 'C',NULL,NULL };
BinaryNode node4 = { 'D',NULL,NULL };
BinaryNode node5 = { 'E',NULL,NULL };
BinaryNode node6 = { 'F',NULL,NULL };
BinaryNode node7 = { 'G',NULL,NULL };
BinaryNode node8 = { 'H',NULL,NULL };
//建立节点关系
node1.lchild = &node2;
node1.rchild = &node6;
node2.rchild = &node3;
node3.lchild = &node4;
node3.rchild = &node5;
node6.rchild = &node7;
node7.lchild = &node8;
caidancaozuo(&node1);
//这下边的注释是我没搞菜单时弄的测试的东西，你要觉得没用请自觉忽略
// int num = 0;
// sumleaf(&node1, num);
// cout << "您的二叉树里的叶子的总数有" << num << "个" << endl;
// int gaodu = qiugao(&node1);
// cout << "您的二叉树的高度是" << gaodu << endl;
// qiugao(&node1);
//
//
// BinaryNode* test = CopyBinaryNode(&node1);
//
// cout << "复制后的二叉树为" << endl;
// Recursion(test);
// CopyBinaryNode(&node1);
// cout << "先序遍历二叉树" << endl;
// Recursion(&node1);
// cout << "中序遍历二叉树" << endl;
// Inorder(&node1);
// cout << "后序遍历二叉树" << endl;
// Postorder(&node1);
}
void Recursion(BinaryNode* root) {
if (root == NULL) {
return;
}
//先序遍历
//先访问根节点
cout << root->ch ;
//遍历左子树
Recursion(root->lchild);//递归调用，自己好好想想
//遍历右子树
Recursion(root->rchild);
}
void Inorder(BinaryNode* root) {
if (root == NULL) {
return;
}
//中序序遍历
//遍历左子树
Recursion(root->lchild);
//先访问根节点
cout << root->ch ;
//遍历右子树
Recursion(root->rchild);
}
void Postorder(BinaryNode* root) {
if (root == NULL) {
return;
}
//后序遍历
//遍历左子树
Recursion(root->lchild);
//遍历右子树
Recursion(root->rchild);
//先访问根节点
cout << root->ch ;
}
void sumleaf(BinaryNode* root, int& num) {
if (root == NULL) {
return;
}
if (root->lchild == NULL && root->rchild == NULL)
{
num++;
}
sumleaf(root->lchild, num);
sumleaf(root->rchild, num);
}
int qiugao(BinaryNode* root)
{
if (root == NULL) {
return 0;
}
int lheight = qiugao(root->lchild);
int rheight = qiugao(root->rchild);
int height = lheight > rheight ? lheight + 1 : rheight + 1;//若是最下面的一行那就会返回一个一嘛，如此反复
//自己好好想想
return height;
}
BinaryNode* CopyBinaryNode(BinaryNode* root)
{
if (root == NULL)
{
return NULL;//那就是说，假如你的左右的节点是NULL的话，那就给他们的子赋值为NULL
}
BinaryNode* lchild = CopyBinaryNode(root->lchild);//在递归调用时
BinaryNode* rchild = CopyBinaryNode(root->rchild);
BinaryNode* NewNode = (BinaryNode*)malloc(sizeof(BinaryNode));
NewNode->ch=root->ch;
NewNode->lchild = lchild;
NewNode->rchild = rchild;
return NewNode;
}
void FreeSpaceCopyBinaryNode(BinaryNode* root)
{
if(root==NULL)
{
return ;
}
FreeSpaceCopyBinaryNode(root->lchild);
FreeSpaceCopyBinaryNode(root->rchild);
free(root);
}//您在白嫖？