《数据结构与算法》实验:树型结构的建立与遍历
《数据结构与算法》实验报告 |
|||
学生姓名 |
郭茁宁 |
院(系) |
计算机科学与技术 |
学 号 |
1183710109 |
专 业 |
软件工程 |
实验时间 |
2019年11月22日(周五) |
实验地点 |
格物213室 |
实验项目 |
实验2/5:树型结构的建立与遍历(3学时) |
||
实验目的:将课程的基本原理、技术和方法与实际应用相结合,训练和提高学生组织、存储和处理信息的能力,以及复杂问题的数据结构设计能力和程序设计能力,培养软件设计与开发所需要的实践能力。 实验要求:灵活运用基本的数据结构和算法知识,对实际问题进行分析和抽象;结合程序设计的一般过程和方法为实际问题设计数据结构和有效算法;用高级语言对数据结构和算法进行编程实现、调试,测试其正确性和有效性。 |
|||
实验内容: 树型结构的遍历是树型结构算法的基础,本实验要求编写程序演示二叉树的存储结构的建立方法和遍历过程。
|
|||
数据结构定义:
|
|||
算法设计与分析(要求画出核心内容的程序流程图):
首先用class封装数据结构(面向对象):
在依次实现遍历功能:
|
|||
实验测试结果及结果分析: 样例: 结果: level_trave: A B C D E H G F N M pre_order_recursion: A B C E D H F N G M in_order_recursion: A E C B F H N D G M post_order_recursion: E C F N H M G D B A pre_order_non_recur: A B C E D H F N G M in_order_non_recur: A E C B F H N D G M post_order_non_recur: E C F N H M G D B A complete_binary_tree: false lowest_common_ancestor: A |
|||
问题及解决方法:
|
|||
源程序名称:lab2.cpp |
注意:正文文字为宋体小4号,图中文字为宋体5号。行距为多倍行距1.25。
源程序与此报告打包提交,压缩包采用学号命名。
#include <cstdio>
#include <cstdlib>
#include <iostream>
using namespace std;
#define Point_Num 100
#define Child_Num 2
class Tree
{
public:
char val;
Tree *son[Child_Num],*fa;
Tree()
{
for (int i=0;i<Child_Num;i++) son[i]=NULL;
fa=NULL;
}
void init(char value){val=value;}
void add(Tree *child,int child_num)
{
son[child_num]=child;
child->fa=this;
}
bool leaf(){return this==NULL?false:son[0]==NULL&&son[1]==NULL;}
};
class node
{
public:
Tree *data;
node *next;
};
class Queue//head<x<=tail
{
public:
node *head,*tail;
Queue()
{
head=new node();
head->next=NULL;
tail=head;
}
bool empty(){return head==tail;}
void push(Tree *member)
{
node *x=new node();
x->data=member;
tail->next=x;
x->next=NULL;
tail=x;
}
Tree *pop()
{
if (empty()) return NULL;
Tree *pop_obj=front();
node *last=head;
head=head->next;
delete last;
return pop_obj;
}
Tree *front(){return head->next->data;}
Tree *back(){return tail->data;}
};
class Stack
{
public:
node *top;
bool empty(){return top->next==NULL;}
Stack()
{
top=new node();
top->data=NULL;
top->next=NULL;
}
void push(Tree *member)
{
node *x=new node();
x->data=member;
x->next=top;
top=x;
}
Tree *pop()
{
if (empty()) return NULL;
Tree *pop_obj=get_top();
node *last=top;
top=top->next;
delete last;
return pop_obj;
}
Tree *get_top()
{
if (empty()) return NULL;
return top->data;
}
};
void level_trave(Tree *head)
{
Queue qu;
for (qu.push(head);!qu.empty();)
{
for (int i=0;i<Child_Num;i++) if (qu.front()->son[i]!=NULL) qu.push(qu.front()->son[i]);
printf("%c ",qu.pop()->val);
}
}
void pre_order_recursion(Tree *head)
{
printf("%c ",head->val);
if (head->son[0]!=NULL) pre_order_recursion(head->son[0]);
if (head->son[1]!=NULL) pre_order_recursion(head->son[1]);
}
void in_order_recursion(Tree *head)
{
if (head->son[0]!=NULL) in_order_recursion(head->son[0]);
printf("%c ",head->val);
if (head->son[1]!=NULL) in_order_recursion(head->son[1]);
}
void post_order_recursion(Tree *head)
{
if (head->son[0]!=NULL) post_order_recursion(head->son[0]);
if (head->son[1]!=NULL) post_order_recursion(head->son[1]);
printf("%c ",head->val);
}
void pre_order_non_recur(Tree *head)
{
Stack sta;
Tree *x=head;
while (!sta.empty()||x!=NULL)
{
if (x!=NULL)
{
printf("%c ",x->val);
sta.push(x);
x=x->son[0];
}
else x=sta.pop()->son[1];
}
}
void in_order_non_recur(Tree *head)
{
Stack sta;
Tree *x=head;
while (!sta.empty()||x!=NULL)
{
if (x!=NULL)
{
sta.push(x);
x=x->son[0];
}
else
{
if (sta.get_top()!=NULL) printf("%c ",sta.get_top()->val);
x=sta.pop()->son[1];
}
}
}
void post_order_non_recur(Tree *head)
{
Stack sta;
Tree *t,*cur,*pre;
sta.push(head);
while (!sta.empty())
{
t=sta.get_top();
if ((t->son[0]==NULL&&t->son[1]==NULL)||(pre!=NULL&&(pre==t->son[0]||pre==t->son[1])))
{
cur=sta.pop();
printf("%c ",cur->val);
pre=cur;
}
else
{
if (t->son[1]!=NULL) sta.push(t->son[1]);
if (t->son[0]!=NULL) sta.push(t->son[0]);
}
}
}
bool complete_binary_tree(Tree *head)
{
Queue qu;
qu.push(head);
Tree *last=NULL;
while (!qu.empty())
{
if ((qu.front()->son[0]==NULL&&qu.front()->son[1]!=NULL)||(last->leaf()&&!last->leaf())) return false;
for (int i=0;i<Child_Num;i++) if (qu.front()->son[i]!=NULL) qu.push(qu.front()->son[i]);
last=qu.pop();
}
return true;
}
char LCA(Tree *head,Tree *x,Tree *y)
{
Tree *a=x,*b=y;
while (a!=b)
{
a=(a==head?y:a->fa);
b=(b==head?x:b->fa);
}
return a->val;
}
int main()
{
freopen("init.txt","r",stdin);
//freopen("ans.txt","w",stdout);
Tree *list[Point_Num];
int n,head_num,numx,numy;
char x,chx,chy;
scanf("%d\n",&n);
for (int i=0;i<n;i++)
{
scanf("%c ",&x);
list[i]=new Tree();
list[i]->init(x);
}
scanf("%d",&head_num);
for (int i=0,di,si,ni;i<n-1;i++)//dad_i son_i num_i
{
scanf("%d%d%d",&di,&si,&ni);
list[di]->add(list[si],ni);
}
printf("level_trave: "); level_trave(list[head_num]); printf("\n");
printf("pre_order_recursion: "); pre_order_recursion(list[head_num]); printf("\n");
printf("in_order_recursion: "); in_order_recursion(list[head_num]); printf("\n");
printf("post_order_recursion: "); post_order_recursion(list[head_num]); printf("\n");
printf("pre_order_non_recur: "); pre_order_non_recur(list[head_num]); printf("\n");
printf("in_order_non_recur: "); in_order_non_recur(list[head_num]); printf("\n");
printf("post_order_non_recur: "); post_order_non_recur(list[head_num]); printf("\n");
cout<<"complete_binary_tree: "<< boolalpha << complete_binary_tree(list[head_num])<<endl;
scanf("%c %c",&chx,&chy);
for (int i=0;i<n;i++)
{
if (list[i]->val==chx) numx=i;
if (list[i]->val==chy) numy=i;
}
cout<<"lowest_common_ancestor: " << LCA(list[head_num],list[numx],list[numy]) <<endl;
fclose(stdin);
//fclose(stdout);
return 0;
}