数据结构实验 二叉树的操作实验三 二叉树的操作
1、实验目的
1、掌握二叉树的逻辑结构；
2、掌握二叉树的二叉链表存储结构；
3、掌握基于二叉链表存储的二叉树的遍历操作的实现。
2、实验内容
1、采用二叉链表存储建立一棵含有n个结点的二叉树；
2、前序打印该二叉树的所有叶子结点；
3、统计该二叉树的结点个数；
4、计算该二叉树的深度；
5、交换该二叉树的所有左右子树。
3、程序实现
1、二叉链表结点类型BiNode.h
template
struct BiNode
{
T data;
BiNode *lchild,*rchild;
};...
实验三 二叉树的操作
1、实验目的
1、掌握二叉树的逻辑结构；
2、掌握二叉树的二叉链表存储结构；
3、掌握基于二叉链表存储的二叉树的遍历操作的实现。
2、实验内容
1、采用二叉链表存储建立一棵含有n个结点的二叉树；
2、前序打印该二叉树的所有叶子结点；
3、统计该二叉树的结点个数；
4、计算该二叉树的深度；
5、交换该二叉树的所有左右子树。
3、程序实现
1、二叉链表结点类型BiNode.h
template
struct BiNode
{
T data;
BiNode *lchild,*rchild;
};
2、二叉树的建立及操作BiTree.h
template
struct BiNode
{
T data;
BiNode *lchild,*rchild;
};
template
class BiTree
{
public:
BiTree( ); //构造函数，初始化一棵二叉树，其前序序列由键盘输入
~BiTree(); //析构函数，释放二叉链表中各结点的存储空间
BiNode* Getroot(); //获得指向根结点的指针
void PreOrder(BiNode *root); //前序遍历二叉树
void InOrder(BiNode *root); //中序遍历二叉树
void PostOrder(BiNode *root); //后序遍历二叉树
void LevelOrder(BiNode *root); //层序遍历二叉树
private:
BiNode *root; //指向根结点的头指针
BiNode* Creat(); //有参构造函数调用
void Release(BiNode *root); //析构函数调用
};
template
BiTree::BiTree()
{
cout<<"请按前根序输入该二叉树的各个结点(#号表示为空):\n";
this->root=Creat();
}
template
BiNode* BiTree::Creat()
{
BiNode *root;
T ch;
cin>>ch;
if (ch=='#') root = NULL;
else{
root = new BiNode; //生成一个结点
root->data=ch;
root->lchild=Creat(); //递归建立左子树
root->rchild=Creat(); //递归建立右子树
}
return root;
}
template
BiTree::~BiTree()
{
Release(root);
}
template
BiNode* BiTree::Getroot( )
{
return root;
}
template
void BiTree::PreOrder(BiNode *root)
{
if(root==NULL) return;
else{
cout<data<<" ";
PreOrder(root->lchild);
PreOrder(root->rchild);
}
}
template
void BiTree::InOrder (BiNode *root)
{
if (root==NULL) return; //递归调用的结束条件
else{
InOrder(root->lchild); //中序递归遍历root的左子树
cout<data<<" "; //访问根结点的数据域
InOrder(root->rchild); //中序递归遍历root的右子树
}
}
template
void BiTree::PostOrder(BiNode *root)
{
if (root==NULL) return; //递归调用的结束条件
else{
PostOrder(root->lchild); //后序递归遍历root的左子树
PostOrder(root->rchild); //后序递归遍历root的右子树
cout<data<<" "; //访问根结点的数据域
}
}
template
void BiTree::LevelOrder(BiNode *root)
{
const int MaxSize = 100;
int front = 0;
int rear = 0; //采用顺序队列，并假定不会发生上溢
BiNode* Q[MaxSize];
BiNode* q;
if (root==NULL) return;
else{
Q[rear++] = root;
while (front != rear)
{
q = Q[front++];
cout<data<<" ";
if (q->lchild != NULL) Q[rear++] = q->lchild;
if (q->rchild != NULL) Q[rear++] = q->rchild;
}
}
}
template
void BiTree::Release(BiNode* root)
{
if (root != NULL){
Release(root->lchild); //释放左子树
Release(root->rchild); //释放右子树
delete root;
}
}
3、主程序实现
#include
#include "BiTree.h"
int SumNode(BiNode *root)//统计二叉树结点个数
{
int sum;
if(root==NULL)return 0;
else{
sum=SumNode(root->lchild)+1;
sum+=SumNode(root->rchild);
return sum;
}
}
void PrePrint(BiNode *root)//前序打印二叉树叶子结点
{
if(root==NULL) return;
else{
if(root->lchild==NULL&&root->rchild==NULL)
cout<data<<' ';
PrePrint(root->lchild);
PrePrint(root->rchild);
}
}
int TreeDeepth(BiNode *root)//计算二叉树的深度
{
int deepth;
if(root==NULL) return 0;
else{
deepth=(TreeDeepth(root->lchild)+1)>(TreeDeepth(root->rchild)+1)?(TreeDeepth(root->lchild)+1):(TreeDeepth(root->rchild)+1);
return deepth;
}
}
void Changechild(BiNode *root)//交换二叉树的所有左右子树
{
BiNode *temp;
if(root==NULL||(root->lchild==NULL&&root->rchild==NULL)) return;
else
{
Changechild(root->lchild);
Changechild(root->rchild);
if(root->lchild==NULL)
{
root->lchild=root->rchild;
root->rchild=NULL;
}
if(root->rchild==NULL)
{
root->rchild=root->lchild;
root->lchild=NULL;
}
else
{
temp=root->lchild;
root->lchild=root->rchild;
root->rchild=temp;
}
}
}
void main()
{
BiTree Q;
int deepth,sum;
cout<<"Q的前序遍历为:\n";
Q.PreOrder(Q.Getroot());
cout<<"\nQ的中序遍历为:\n";
Q.InOrder(Q.Getroot());
cout<<"\nQ的后序遍历为:\n";
Q.PostOrder(Q.Getroot());
cout<<"\nQ的层序遍历为:\n";
Q.LevelOrder(Q.Getroot());
sum=SumNode(Q.Getroot());
cout<<"\n结点个数为:"<
本文档为【数据结构实验 二叉树的操作】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483