树和二叉树实验
实验题目：二叉树的实现
一、 实验目的
（1）掌握二叉树的逻辑结构；
（2）掌握二叉树的二叉链表存储结构；
（3）验证二叉树的二叉链表存储及遍历操作
二、 实验内容：
（1）建立一颗含有 n 个节点的二叉树，采用二叉链表存储
（2）输出前序、中序和后序遍历该二叉树的遍历结构
三、 设计与编码
1. 本实验用到的理论知识
（1）二叉树的存储结构：二叉链表；
（2）二叉树的四种遍历操作：前序、中序、后序和层序遍历；
2. 算法设计：
（1）二叉树的建立：用递归的方法，先递归建立根结点的左子树，再递归建立根结点
的右子树；
（2）二叉树的遍历操作：四种，均用到递归。
3. 编码
//Bitree.h
#ifndef BiTree_H
#define BiTree_H
struct BiNode //二叉树的结点结构
{
char data;
BiNode *lchild, *rchild;
};
class BiTree
{
public:
BiTree( ){root = Creat(root);} //构造函数，建立一棵二叉树
~BiTree( ){Release(root);} //析构函数，释放各结点的存储空间
void PreOrder( ){PreOrder(root);} //前序遍历二叉树
void InOrder( ){InOrder(root);} //中序遍历二叉树
void PostOrder( ){PostOrder(root);} //后序遍历二叉树
void LeverOrder( ); //层序遍历二叉树
private:
BiNode *root; //指向根结点的头指针
BiNode *Creat(BiNode *bt); //构造函数调用
void Release(BiNode *bt); //析构函数调用
void PreOrder(BiNode *bt); //前序遍历函数调用
void InOrder(BiNode *bt); //中序遍历函数调用
void PostOrder(BiNode *bt); //后序遍历函数调用
};
#endif
//Bitree.cpp
#include
using namespace std;
#include "Bitree.h"
BiNode *BiTree::Creat(BiNode *bt)
{
char ch;
cout
cin>>ch;
if (ch=='#') return NULL;
else{
bt = new BiNode; //生成一个结点
bt->data=ch;
bt->lchild = Creat(bt->lchild); //递归建立左子树
bt->rchild = Creat(bt->rchild); //递归建立右子树
}
return bt;
}
void BiTree::Release(BiNode *bt)
{
if (bt != NULL){
Release(bt->lchild); //释放左子树
Release(bt->rchild); //释放右子树
delete bt;
}
}
void BiTree::PreOrder(BiNode *bt)
{
if(bt==NULL) return;
else {
coutdata
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
void BiTree::InOrder(BiNode *bt)
{
if (bt==NULL) return; //递归调用的结束条件
else {
InOrder(bt->lchild); //中序递归遍历root 的左子树
coutdata
InOrder(bt->rchild); //中序递归遍历root 的右子树
}
}
void BiTree::PostOrder(BiNode *bt)
{
if (bt==NULL) return; //递归调用的结束条件
else {
PostOrder(bt->lchild); //后序递归遍历root 的左子树
PostOrder(bt->rchild); //后序递归遍历root 的右子树
coutdata
}
}
void BiTree::LeverOrder( )
{
const int MaxSize=100;
int front=-1, rear=-1; //采用顺序队列，并假定不会发生上溢
BiNode *Q[MaxSize], *q;
if (root==NULL) return;
else {
Q[++rear]=root;
while (front!=rear)
{
q=Q[++front];
coutdata
if (q->lchild!=NULL) Q[++rear]=q->lchild;
if (q->rchild!=NULL) Q[++rear]=q->rchild;
}
}
}
//Bitree_main.cpp
#include
using namespace std;
#include "Bitree.h"
void main()
{
BiTree T; //创建一棵树
cout
T.PreOrder( );
cout
cout
T.InOrder( );
cout
cout
T.PostOrder( );
cout
cout
T.LeverOrder();
cout
}
注：源程序中Q[rear++]，Q[front++]，而rear,front 初始值均为-1，数组下标不会为 -1，故错误，分别改为Q[++rear]，Q[++front]即可。
四、 运行与测试
（1）输入二叉树为
结果为：
（2）输入二叉树为：
输出结果为：
五、 总结
二叉树的存储结构—二叉链表，以及基于二叉链表的二叉树的建立，四种遍历二叉树的方法，尤其是递归思想在二叉树的构造函与遍历中的使用，需要特别注意，也要掌握。
实验题目：树的实现
一、 实验目的
（1） 树的逻辑结构
（2） 树的孩子兄弟存储结构
（3） 验证树的孩子兄弟存储结构及遍历操作
二、 实验内容
（1） 采用孩子兄弟表示法建立一棵树
（2） 基于树的孩子兄弟表示法实现前序和后序遍历树的操作
三、 设计与编码
1. 本实验用到的理论知识
（1）树的孩子兄弟表示法
（2）树的逻辑存储结构—孩子兄弟存储结构
（3）树的前序、后序遍历
2. 算法设计
（1）建立一棵树
先输入根结点。再递归建立左子树，右子树
（2）树的遍历
前序遍历：访问根结点、递归访问左子树、右子树
后序遍历：访问左子树、再访问右子树、最后访问根结点
3. 编码
//Tree.h
#ifndef Tree_H
#define Tree_H
const int Max = 20;
struct TNode
{
};
class Tree
{
public:
Tree(); ~Tree() { Release(root); } //析构函数，释放各结点的存储空间 void PreOrder() { PreOrder(root); } void PostOrder() { PostOrder(root); } char data; TNode *firstchild, *rightsib;
private:
};
#endif
//Tree.cpp TNode *root; void PreOrder(TNode *bt); void PostOrder(TNode *bt); void Release(TNode *bt);
#include
using namespace std;
#include "Tree.h"
Tree::Tree()
{
TNode *Q[Max] = { NULL }; char ch1 = '#', ch2 = '#',ch0='#'; int front = -1, rear = -1; TNode *p = NULL, *q = NULL,*s = NULL; cout > ch1; cout data = ch1; p->firstchild = p->rightsib = NULL; root = p; Q[++rear] = p; cout
while (ch1 != '#' || ch2 != '#') { p = new TNode; p->data = ch2; p->firstchild = p->rightsib = NULL; Q[++rear] = p; while (front != rear) { q = Q[front + 1]; if (q->data != ch1) front++; else { if (q->firstchild == NULL) q->firstchild = p; else { } s = q->firstchild; while (s->rightsib != NULL) s = s->rightsib; s->rightsib = p;
} } } } cout
void Tree::Release(TNode *bt)
{
}
void Tree::PreOrder(TNode *bt) if (bt == NULL) return; //递归调用的结束条件 else { } Release(bt->firstchild); //后序递归释放bt 的第一棵子树 Release(bt->rightsib); //后序递归释放bt 的右兄弟子树 delete bt; //释放根结点
}
void Tree::PostOrder(TNode *bt)
{
}
if (bt == NULL) return; //递归调用的结束条件 else { } PostOrder(bt->firstchild); //后序递归遍历root 的第一棵子树 PostOrder(bt->rightsib); //后序递归遍历root 的右兄弟子树 cout data; //访问根结点的数据域 if (bt == NULL) return; //递归调用的结束条件 else { } cout data; //访问根结点的数据域 PreOrder(bt->firstchild); //前序递归遍历root 的第一棵子树 PreOrder(bt->rightsib); //前序递归遍历root 的右兄弟子树
//Tree_main.cpp
#include
using namespace std;
#include "Tree.h"
int main()
{
}
四、 运行与测试
输入的树为： Tree t1; cout
输出结果为：
五、 总结
树的孩子兄弟表示法以及孩子兄弟存储结构，将其用程序语言来实现，其中指针的运用比较灵活，需要认真考虑。在程序中，也运用了递归的思想，递归在算法设计中还是非常有用的。
树和二叉树实验
实验题目：二叉树的实现
一、 实验目的
（1）掌握二叉树的逻辑结构；
（2）掌握二叉树的二叉链表存储结构；
（3）验证二叉树的二叉链表存储及遍历操作
二、 实验内容：
（1）建立一颗含有 n 个节点的二叉树，采用二叉链表存储
（2）输出前序、中序和后序遍历该二叉树的遍历结构
三、 设计与编码
1. 本实验用到的理论知识
（1）二叉树的存储结构：二叉链表；
（2）二叉树的四种遍历操作：前序、中序、后序和层序遍历；
2. 算法设计：
（1）二叉树的建立：用递归的方法，先递归建立根结点的左子树，再递归建立根结点
的右子树；
（2）二叉树的遍历操作：四种，均用到递归。
3. 编码
//Bitree.h
#ifndef BiTree_H
#define BiTree_H
struct BiNode //二叉树的结点结构
{
char data;
BiNode *lchild, *rchild;
};
class BiTree
{
public:
BiTree( ){root = Creat(root);} //构造函数，建立一棵二叉树
~BiTree( ){Release(root);} //析构函数，释放各结点的存储空间
void PreOrder( ){PreOrder(root);} //前序遍历二叉树
void InOrder( ){InOrder(root);} //中序遍历二叉树
void PostOrder( ){PostOrder(root);} //后序遍历二叉树
void LeverOrder( ); //层序遍历二叉树
private:
BiNode *root; //指向根结点的头指针
BiNode *Creat(BiNode *bt); //构造函数调用
void Release(BiNode *bt); //析构函数调用
void PreOrder(BiNode *bt); //前序遍历函数调用
void InOrder(BiNode *bt); //中序遍历函数调用
void PostOrder(BiNode *bt); //后序遍历函数调用
};
#endif
//Bitree.cpp
#include
using namespace std;
#include "Bitree.h"
BiNode *BiTree::Creat(BiNode *bt)
{
char ch;
cout
cin>>ch;
if (ch=='#') return NULL;
else{
bt = new BiNode; //生成一个结点
bt->data=ch;
bt->lchild = Creat(bt->lchild); //递归建立左子树
bt->rchild = Creat(bt->rchild); //递归建立右子树
}
return bt;
}
void BiTree::Release(BiNode *bt)
{
if (bt != NULL){
Release(bt->lchild); //释放左子树
Release(bt->rchild); //释放右子树
delete bt;
}
}
void BiTree::PreOrder(BiNode *bt)
{
if(bt==NULL) return;
else {
coutdata
PreOrder(bt->lchild);
PreOrder(bt->rchild);
}
}
void BiTree::InOrder(BiNode *bt)
{
if (bt==NULL) return; //递归调用的结束条件
else {
InOrder(bt->lchild); //中序递归遍历root 的左子树
coutdata
InOrder(bt->rchild); //中序递归遍历root 的右子树
}
}
void BiTree::PostOrder(BiNode *bt)
{
if (bt==NULL) return; //递归调用的结束条件
else {
PostOrder(bt->lchild); //后序递归遍历root 的左子树
PostOrder(bt->rchild); //后序递归遍历root 的右子树
coutdata
}
}
void BiTree::LeverOrder( )
{
const int MaxSize=100;
int front=-1, rear=-1; //采用顺序队列，并假定不会发生上溢
BiNode *Q[MaxSize], *q;
if (root==NULL) return;
else {
Q[++rear]=root;
while (front!=rear)
{
q=Q[++front];
coutdata
if (q->lchild!=NULL) Q[++rear]=q->lchild;
if (q->rchild!=NULL) Q[++rear]=q->rchild;
}
}
}
//Bitree_main.cpp
#include
using namespace std;
#include "Bitree.h"
void main()
{
BiTree T; //创建一棵树
cout
T.PreOrder( );
cout
cout
T.InOrder( );
cout
cout
T.PostOrder( );
cout
cout
T.LeverOrder();
cout
}
注：源程序中Q[rear++]，Q[front++]，而rear,front 初始值均为-1，数组下标不会为 -1，故错误，分别改为Q[++rear]，Q[++front]即可。
四、 运行与测试
（1）输入二叉树为
结果为：
（2）输入二叉树为：
输出结果为：
五、 总结
二叉树的存储结构—二叉链表，以及基于二叉链表的二叉树的建立，四种遍历二叉树的方法，尤其是递归思想在二叉树的构造函与遍历中的使用，需要特别注意，也要掌握。
实验题目：树的实现
一、 实验目的
（1） 树的逻辑结构
（2） 树的孩子兄弟存储结构
（3） 验证树的孩子兄弟存储结构及遍历操作
二、 实验内容
（1） 采用孩子兄弟表示法建立一棵树
（2） 基于树的孩子兄弟表示法实现前序和后序遍历树的操作
三、 设计与编码
1. 本实验用到的理论知识
（1）树的孩子兄弟表示法
（2）树的逻辑存储结构—孩子兄弟存储结构
（3）树的前序、后序遍历
2. 算法设计
（1）建立一棵树
先输入根结点。再递归建立左子树，右子树
（2）树的遍历
前序遍历：访问根结点、递归访问左子树、右子树
后序遍历：访问左子树、再访问右子树、最后访问根结点
3. 编码
//Tree.h
#ifndef Tree_H
#define Tree_H
const int Max = 20;
struct TNode
{
};
class Tree
{
public:
Tree(); ~Tree() { Release(root); } //析构函数，释放各结点的存储空间 void PreOrder() { PreOrder(root); } void PostOrder() { PostOrder(root); } char data; TNode *firstchild, *rightsib;
private:
};
#endif
//Tree.cpp TNode *root; void PreOrder(TNode *bt); void PostOrder(TNode *bt); void Release(TNode *bt);
#include
using namespace std;
#include "Tree.h"
Tree::Tree()
{
TNode *Q[Max] = { NULL }; char ch1 = '#', ch2 = '#',ch0='#'; int front = -1, rear = -1; TNode *p = NULL, *q = NULL,*s = NULL; cout > ch1; cout data = ch1; p->firstchild = p->rightsib = NULL; root = p; Q[++rear] = p; cout
while (ch1 != '#' || ch2 != '#') { p = new TNode; p->data = ch2; p->firstchild = p->rightsib = NULL; Q[++rear] = p; while (front != rear) { q = Q[front + 1]; if (q->data != ch1) front++; else { if (q->firstchild == NULL) q->firstchild = p; else { } s = q->firstchild; while (s->rightsib != NULL) s = s->rightsib; s->rightsib = p;
} } } } cout
void Tree::Release(TNode *bt)
{
}
void Tree::PreOrder(TNode *bt) if (bt == NULL) return; //递归调用的结束条件 else { } Release(bt->firstchild); //后序递归释放bt 的第一棵子树 Release(bt->rightsib); //后序递归释放bt 的右兄弟子树 delete bt; //释放根结点
}
void Tree::PostOrder(TNode *bt)
{
}
if (bt == NULL) return; //递归调用的结束条件 else { } PostOrder(bt->firstchild); //后序递归遍历root 的第一棵子树 PostOrder(bt->rightsib); //后序递归遍历root 的右兄弟子树 cout data; //访问根结点的数据域 if (bt == NULL) return; //递归调用的结束条件 else { } cout data; //访问根结点的数据域 PreOrder(bt->firstchild); //前序递归遍历root 的第一棵子树 PreOrder(bt->rightsib); //前序递归遍历root 的右兄弟子树
//Tree_main.cpp
#include
using namespace std;
#include "Tree.h"
int main()
{
}
四、 运行与测试
输入的树为： Tree t1; cout
输出结果为：
五、 总结
树的孩子兄弟表示法以及孩子兄弟存储结构，将其用程序语言来实现，其中指针的运用比较灵活，需要认真考虑。在程序中，也运用了递归的思想，递归在算法设计中还是非常有用的。