数据结构实验(二叉树的基本操作实现)

时间:2022-09-23 17:35:38

实验题目: 二叉树的基本操作实现               

实验目的:掌握二叉树的二叉链存储结构及表示。

          掌握二叉树的三种遍历算法(递归和非递归两类)。

          运用三种遍历的方法求解二叉树的有关问题。

实验内容:实现二叉树的二叉链表存储结构;

          实现先序、中序和后序遍历二叉树;

          遍历二叉树的应用:计算叶子结点、左右子树交换等。

 

要求:1、二叉树基本操作已实现,学习和进一步理解。

      2 、在求总结点的程序中加入求叶子结点的功能。

      3 、左右子树交换,按中序和后序是否也可以?

      4 、选作:按层遍历二叉树。

 实验代码:

#include<stdio.h>
#include
<malloc.h>
#include
<string.h>
#include
<stdlib.h>
#include
<iostream>
#define MAXTSIZE 1000
using namespace std;

/*
测试数据: abc##de#g##f###
*/

typedef
struct BiTNode
{
char data; // 结点数据域
struct BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

void CreateBiTree(BiTree &T) // 先序遍历建立二叉链表
{
char ch;
cin
>>ch;
// scanf("%c",&ch);
if(ch=='#')
T
=NULL;
else
{
T
=(BiTNode *)malloc(sizeof(BiTNode));
T
->data=ch;
CreateBiTree(T
->lchild);
CreateBiTree(T
->rchild);
}
}

void travel1(BiTree T) // 先序遍历
{
if(T)
{
printf(
"%c",T->data);
travel1(T
->lchild);
travel1(T
->rchild);
}
}

void travel2(BiTree T) // 中序遍历
{
if(T)
{
travel2(T
->lchild);
printf(
"%c",T->data);
travel2(T
->rchild);
}
}

void travel3(BiTree T) // 后序遍历
{
if(T)
{
travel3(T
->lchild);
travel3(T
->rchild);
printf(
"%c",T->data);
}
}

int count(BiTree T) // 计算叶子结点的个数
{
if(T==NULL) return 0;
int cnt=0;
if((!T->lchild)&&(!T->rchild))
{
cnt
++;
}
int leftcnt=count(T->lchild);
int rightcnt=count(T->rchild);
cnt
+=leftcnt+rightcnt;
return cnt;
}

int Depth(BiTree T) // 计算二叉树的深度
{
if(T==NULL) return 0;
else
{
int m=Depth(T->lchild);
int n=Depth(T->rchild);
return m>n?(m+1):(n+1);
}
}

void exchange(BiTree T,BiTree &NewT) // 交换左右子树
{
if(T==NULL)
{
NewT
=NULL;
return ;
}
else
{
NewT
=(BiTNode *)malloc(sizeof(BiTNode));
NewT
->data=T->data;
exchange(T
->lchild,NewT->rchild); // 复制原树的左子树给新树的右子树
exchange(T->rchild,NewT->lchild); // 复制原树的右子树给新树的左子树
}
}

int main()
{
puts(
"**************************");
puts(
"1. 建立二叉树");
puts(
"2. 先序遍历二叉树");
puts(
"3. 中序遍历二叉树");
puts(
"4. 后序遍历二叉树");
puts(
"5. 计算叶子结点个数");
puts(
"6. 计算二叉树的深度");
puts(
"7. 交换二叉树的左右子树");
puts(
"0. 退出");
puts(
"**************************");
BiTree Tree,NewTree;
int choose;
while(~scanf("%d",&choose),choose)
{
switch(choose)
{
case 1:
puts(
"温馨提醒:输入请以 '#' 为左/右子树空的标志!");
CreateBiTree(Tree);
break;
case 2:
printf(
"先序遍历结果为:");
travel1(Tree);
puts(
"");
break;
case 3:
printf(
"中序遍历结果为:");
travel2(Tree);
puts(
"");
break;
case 4:
printf(
"后序遍历结果为:");
travel3(Tree);
puts(
"");
break;
case 5:
printf(
"叶子结点个数为:%d\n",count(Tree));
break;
case 6:
printf(
"二叉树的深度为:%d\n",Depth(Tree));
break;
case 7:
exchange(Tree,NewTree);
Tree
=NewTree;
puts(
"交换成功!\n");
break;
}
}
system(
"pause");
return 0;
}