二叉树的建立及遍历

1、数据结构实验报告实验三名称：二叉树 姓名：高宁鑫学号：201417525班级：2014175专业：数学与应用数学 指导老师：黄春艳一、实验目的(1)掌握二叉树的定义和存储表示，学会建一棵二叉树的方法(2)掌握二叉树的遍历（前序，中序，后序）采用递归和非递归方法二、实验要求(1)建二叉树(2)遍历三、实验原理(1)利用递归原理建立一棵二叉链表的二叉树：为了让每个结点确认是否有左右孩子，对原二叉树进行扩展，将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值“.”获得一个扩展二叉树，通过遍历序列确定一棵二叉树。(2)进行二叉树的遍历：指从根结点出发，按照某种次序依次访问二叉树中的所有结点，

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='

3、;.')*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 -&g

4、t;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)建立非递归方法二叉树的前

5、序、中序、后序遍历void preOrder2(BinTree *root) /非递归前序遍历 stack<BinTree*> s;BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) cout<<p->data<<"" s.push(p); p=p->lchild; if(!s.empty() p=s.top(); s.pop(); p=p->rchild；void inOrder2(BinTree *root) /非递归中序遍历 stack<BinTr

6、ee*> 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<<p->data<<"" s.pop(); p=p->rchild; void postOrder2(BinTree *root) /非递归后序遍历 stack<BTNode*> s; BinTree *p=root; BTNode *temp;while(p!=NULL|!s.e

7、mpty() 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

8、; else /第二次出现在栈顶 cout<<temp->btnode->data<<"" p=NULL; 六、实验结果递归方法的遍历结果：非递归方法的遍历结果：七、心得体会 通过这次实验，让我对树有了更深入的认识，不仅再次熟悉了树以及二叉树的存储结构：顺序存储结构，链式存储结构；而且更加清楚二叉树的遍历原理以及三种遍历方法。在这次实验中，多次应用到了递归，这样让我进一步掌握了递归的算法思想。 然而在输入二叉树中的元素时，只能按设定的前序遍历的次序输入合法的结点的值，不然程序无法进行。总的来说，通过这次实验，让我对树有了更多的认识，明白书

9、本上的程序一定要自己去调试，这样才能将书本程序与老师讲的内容融会贯通，达到温故而知新。主程序源代码：递归方法：#include<stdio.h>#include<stdlib.h>#include <malloc.h>#include <conio.h>typedef int DataType; typedef struct Node /创建结点类型结构体 DataType data; struct Node *LChild; struct Node *RChild; BitNode,*BitTree;void CreatBiTree(BitTr

10、ee *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(BitT

11、ree 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(

12、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); p

13、rintf("n后序遍历序列为:"); PostOrder(T);非递归方法#include <iostream>#include<string.h>#include<stack>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 *&a

14、mp;root) /创建二叉树，s为形如A(B,C(D,E)形式的字符串 int i; bool isRight=false; stack<BinTree*> s1; /存放结点 stack<char> s2; /存放分隔符 BinTree *p,*temp; root->data=s0; root->lchild=NULL; root->rchild=NULL; s1.push(root); i=1; while(i<strlen(s) if(si='(') s2.push(si); isRight=false; else if

15、(si=',') isRight=true; else if(si=')') s1.pop(); s2.pop(); else if(isalpha(si) p=(BinTree *)malloc(sizeof(BinTree); p->data=si; p->lchild=NULL; p->rchild=NULL; temp=s1.top(); if(isRight=true) temp->rchild=p; cout<<temp->data<<"的右孩子是"<<si<

16、<endl; else temp->lchild=p; cout<<temp->data<<"的左孩子是"<<si<<endl; if(si+1='(') s1.push(p); i+; void display(BinTree *root) /显示树形结构 if(root!=NULL) cout<<root->data; if(root->lchild!=NULL) cout<<'(' display(root->lchild); i

17、f(root->rchild!=NULL) cout<<',' display(root->rchild); cout<<')' void preOrder2(BinTree *root) /非递归前序遍历 stack<BinTree*> s; BinTree *p=root; while(p!=NULL|!s.empty() while(p!=NULL) cout<<p->data<<"" s.push(p); p=p->lchild; if(!s.empt

18、y() p=s.top(); s.pop(); p=p->rchild; void inOrder2(BinTree *root) /非递归中序遍历 stack<BinTree*> 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<<p->data<<"" s.pop(); p=p->rchild; void postOrder2(BinTree *root) /非递归后序遍历 stack<BTNode*> s; BinTree *p=root; BTNode *temp; while(p!=NULL|!s.empty() while(p!=NULL) /沿左子树一直往下搜索，直至出现没有左子树的结点 BTNode *btn=(BTNode *)malloc(sizeof(BTNode); btn->btnode=p; b