二叉树的建立及遍历

数据结构实验报告

实验三名称：二叉树

姓名：高宁鑫

学号：201417525

班级：2014175

专业：数学与应用数学

指导老师：黄春艳

一、实验目的

(1)掌握二叉树的定义和存储表示，学会建一棵二叉树的方法

(2)掌握二叉树的遍历（前序，中序，后序）采用递归和非递归方法

二、实验要求

(1)建二叉树

(2)遍历

三、实验原理

(1)利用递归原理建立一棵二叉链表的二叉树：为了让每个结点确认是否有左右孩子，对原二叉树进行扩展，将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值“.”获得一个扩展二叉树，通过遍历序列确定一棵二叉树。

(2)进行二叉树的遍历：指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。

四、实验环境

Windows XP系统, Vc6软件

五、算法实现及步骤

实现的主要算法：

(1)首先定义二叉树的存储形式，这里使用了二叉链表

typedef struct Node //创建结点类型结构体

{ DataType data;

struct Node *LChild;

struct Node *RChild; }BitNode,*BitTree;

(2)建立一个二叉树

void CreatBiTree(BitTree *bt) //用扩展前序遍历序列创建二叉树如果是当前树根置为空 否则申请一个新节点//

{ char ch;

ch=getchar();

if(ch=='.')*bt=NULL;

else

{ *bt=(BitTree)malloc(sizeof(BitNode));

(*bt)->data=ch;

CreatBiTree(&((*bt)->LChild));

CreatBiTree(&((*bt)->RChild));

} }

(3)建立递归方法二叉树的前序、中序、后序遍历

void PreOrder(BitTree root) //前序遍历二叉树的递归算法

{ if (root!=NULL)

{ visit(root ->data);

PreOrder(root ->LChild);

PreOrder(root ->RChild);

} }

void InOrder(BitTree root) //中序遍历二叉树的递归算法

{ if (root!=NULL)

{ InOrder(root ->LChild);

visit(root ->data);

InOrder(root ->RChild);

} }

void PostOrder(BitTree root) //后序遍历求二叉树的递归算法

{ if(root!=NULL)

{ PostOrder(root ->LChild);

PostOrder(root ->RChild);

visit(root ->data);

} }

(4)建立非递归方法二叉树的前序、中序、后序遍历

void preOrder2(BinTree *root) //非递归前序遍历

{ stack s;BinTree *p=root;

while(p!=NULL||!s.empty())

{ while(p!=NULL)

{ cout<data<<"";

s.push(p);

p=p->lchild;

}if(!s.empty())

{ p=s.top();

s.pop();

p=p->rchild；

}}}

void inOrder2(BinTree *root) //非递归中序遍历

{ stack s;

BinTree *p=root;

while(p!=NULL||!s.empty())

{ while(p!=NULL)

{ s.push(p);

p=p->lchild;

}if(!s.empty())

{ p=s.top();

cout<data<<"";

s.pop();

p=p->rchild;

}}}

void postOrder2(BinTree *root) //非递归后序遍历

{ stack s;

BinTree *p=root;

BTNode *temp;

while(p!=NULL||!s.empty())

{ while(p!=NULL)//沿左子树往下搜索，直至出现没有左子树的结点

{ BTNode *btn=(BTNode *)malloc(sizeof(BTNode));

btn->btnode=p;

btn->isFirst=true;

s.push(btn);

p=p->lchild;

} if(!s.empty())

{ temp=s.top();

s.pop();

if(temp->isFirst==true) //表示是第一次出现在栈顶

{ temp->isFirst=false;

s.push(temp);

p=temp->btnode->rchild;

} else //第二次出现在栈顶

{ cout<btnode->data<<"";

p=NULL;

}}}}

六、实验结果

递归方法的遍历结果：

非递归方法的遍历结果：

七、心得体会

通过这次实验，让我对树有了更深入的认识，不仅再次熟悉了树以及二叉树的存储结构：顺序存储结构，链式存储结构；而且更加清楚二叉树的遍历原理以及三种遍历方法。在这次实验中，多次应用到了递归，这样让我进一步掌握了递归的算法思想。

然而在输入二叉树中的元素时，只能按设定的前序遍历的次序输入合法的结点的值，不然程序无法进行。总的来说，通过这次实验，让我对树有了更多的认识，明白书本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。

主程序源代码：

递归方法：

#include

#include

#include

#include

typedef int DataType;

typedef struct Node //创建结点类型结构体

{ DataType data;

struct Node *LChild;

struct Node *RChild;

}

BitNode,*BitTree;

void CreatBiTree(BitTree *bt) //用扩展前序遍历序列创建二叉树如果是当前树根置为空 否则申请一个新节点//

{ char ch;

ch=getchar();

if(ch=='.')*bt=NULL;

else

{ *bt=(BitTree)malloc(sizeof(BitNode));

( *bt)->data=ch;

CreatBiTree(&((*bt)->LChild));

CreatBiTree(&((*bt)->RChild));

}

}

void visit(char ch)//访问根节点

{ printf("%c",ch);

}

void PreOrder(BitTree root) //前序遍历二叉树的递归算法

{ if (root!=NULL)

{ visit(root ->data);

PreOrder(root ->LChild);

PreOrder(root ->RChild);

}

}

void InOrder(BitTree root) //中序遍历二叉树的递归算法

{ if (root!=NULL)

{ InOrder(root ->LChild);

visit(root ->data);

InOrder(root ->RChild);

}

} void PostOrder(BitTree root) //后序遍历求二叉树的递归算法

{ if(root!=NULL)

{ PostOrder(root ->LChild);

PostOrder(root ->RChild);

visit(root ->data);

}

}

void main()

{

BitTree T;

int layer;

layer=0;

printf("请输入二叉树中的元素(以扩展前序遍历序列输入,其中.代表空子树):\n"); CreatBiTree(&T);

printf("前序遍历序列为:");

PreOrder(T);

printf("\n中序遍历序列为:");

InOrder(T); printf("\n后序遍历序列为:");

PostOrder(T);

}

非递归方法

#include

#include

#include

using namespace std;

typedef struct node

{ char data;

struct node *lchild,*rchild;

}BinTree;

typedef struct node1

{

BinTree *btnode;

bool isFirst;

}BTNode;

void creatBinTree(char *s,BinTree *&root) //创建二叉树，s为形如A(B,C(D,E))形式的字符串

{

int i;

bool isRight=false;

stack s1; //存放结点

stack s2; //存放分隔符

BinTree *p,*temp;

root->data=s[0];

root->lchild=NULL;

root->rchild=NULL;

s1.push(root);

i=1;

while(i

{

if(s[i]=='(')

{

s2.push(s[i]);

isRight=false;

}

else if(s[i]==',')

{

isRight=true;

}

else if(s[i]==')')

{

s1.pop();

s2.pop();

}

else if(isalpha(s[i]))

{

p=(BinTree *)malloc(sizeof(BinTree));

p->data=s[i];

p->lchild=NULL;

p->rchild=NULL;

temp=s1.top();

if(isRight==true)

{

temp->rchild=p;

cout<emp->data<<"的右孩子是"<

}

else

{

temp->lchild=p;

cout<data<<"的左孩子是"<

}

if(s[i+1]=='(')

s1.push(p);

}i++;

}

}

void display(BinTree *root) //显示树形结构

{

if(root!=NULL)

{

cout<data;

if(root->lchild!=NULL)

{

cout<<'(';

display(root->lchild);

}

if(root->rchild!=NULL)

{

cout<<',';

display(root->rchild);

cout<<')';

}

}

}

void preOrder2(BinTree *root) //非递归前序遍历

{

stack s;

BinTree *p=root;

while(p!=NULL||!s.empty())

{

while(p!=NULL)

{

cout<data<<"";

s.push(p);

p=p->lchild;

}

if(!s.empty())

{

p=s.top();

s.pop();

p=p->rchild;

}

}}

void inOrder2(BinTree *root) //非递归中序遍历

{

stack s;

BinTree *p=root;

while(p!=NULL||!s.empty())

{

while(p!=NULL)

{

s.push(p);

p=p->lchild;

}

if(!s.empty())

{

p=s.top();

cout<data<<"";

s.pop();

p=p->rchild;

}

}

}

void postOrder2(BinTree *root) //非递归后序遍历

{

stack s;

BinTree *p=root;

BTNode *temp;

while(p!=NULL||!s.empty())

{

while(p!=NULL) //沿左子树一直往下搜索，直至出现没有左子树的结点

{

BTNode *btn=(BTNode *)malloc(sizeof(BTNode));

btn->btnode=p;

btn->isFirst=true;

s.push(btn);

p=p->lchild;

}

if(!s.empty())

{

temp=s.top();

s.pop();

if(temp->isFirst==true) //表示是第一次出现在栈顶

{

temp->isFirst=false;

s.push(temp);

p=temp->btnode->rchild;

}

else //第二次出现在栈顶

{

cout<btnode->data<<"";

p=NULL;

}

}

}

}

int main(int argc, char *argv[])

{

char s[100];

while(scanf("%s",s)==1)

{

BinTree *root=(BinTree *)malloc(sizeof(BinTree));

creatBinTree(s,root);

printf("前序遍历序列为:");

preOrder2(root);

cout<

printf("中序遍历序列为:");

inOrder2(root);

cout<

printf("后序遍历序列为:");

postOrder2(root);

cout<

}

return 0;

}

本文来源：https://www.2haoxitong.net/k/doc/9c97e6e89a89680203d8ce2f0066f5335a81674c.html