树和二叉树的操作

1、河南城建学院计算机与数据科学学院数据结构实验报告实验名称：_实验三 树和二叉树的操作     成绩：_ _专业班级：_ _   姓名：_李_    学号：_0_ _  实验日期 ：  2016 年  5 月 11  日一、实验目的1进一步掌握树的结构及非线性特点，递归特点和动态性。2进一步巩固对指针的使用和二叉树的三种遍历方法、建立方法。二、实验内容二叉树的实现和运算（建树、树的三种遍历等）三、实验要求1用C+/C完成算法设计和程序设计并上机调试

2、通过。2撰写实验报告，提供实验结果和数据。3分析算法，并简要给出算法设计小结和心得。四、程序实现1）#include<stdio.h>#include<stdlib.h>#include <string.h>typedef struct BiNodechar s20;struct BiNode *lchild,*rchild;BiTNode,*BiTree;char ch,bt1024;int len=0;void push(char c)if (len<1024)btlen+ = c;BiTree Create_RTree()BiTree T,Q,S

3、;char *p;while(ch!=EOF)ch=getchar();if(ch='n')if(len>0)/输入结束，堆栈中为右节点的值if(Q=(BiTNode*)malloc(sizeof(BiTNode)=NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s);Q->lchild=NULL;Q->rchild=NULL; memcpy(Q->s,bt,len);len =0;return Q;return NULL; else if (ch = '(') if(Q=(BiTNod

4、e*)malloc(sizeof(BiTNode)=NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s);Q->rchild = NULL;Q->lchild =Create_RTree(); ch=getchar();if(ch='n') return Q;Q->s0=ch;Q->rchild=Create_RTree();return Q; else if(ch =')') if(len>0)if(Q=(BiTNode*)malloc(sizeof(BiTNode)=NULL)

5、return NULL;memset(Q->s,0x00,sizeof(Q->s);Q->lchild=NULL;Q->rchild=NULL; memcpy(Q->s,bt,len);len=0;return Q;return NULL; else if(ch ='+'|ch='-'|ch ='*'|ch ='/'|ch ='') if(T=(BiTNode*)malloc(sizeof(BiTNode)=NULL)return NULL;if(Q=(BiTNode*)malloc(

6、sizeof(BiTNode)=NULL)return NULL;memset(Q->s,0x00,sizeof(Q->s);memset(T->s,0x00,sizeof(T->s);T->lchild=NULL;T->rchild=NULL;if(len=0)if(ch ='+'|ch ='-')/ 只有+-号前面可以不是数字,此时左节点为空T->s0=ch;if(S=(BiTNode*)malloc(sizeof(BiTNode)=NULL)return NULL;memset(S->s,0x00,sizeo

7、f(S->s);S->lchild=NULL;S->rchild=NULL;p=S->s;while(1)ch=getchar();if(ch='+'|ch ='-'|ch ='*'|ch ='/'|ch='')break;*p+=ch;T->rchild=S; else return NULL; else /堆栈中为左节点值memcpy(T->s,bt,len);len =0;Q->lchild=T;Q->s0=ch;if(Q->rchild = Create

8、_RTree() = NULL)return NULL;elsereturn Q; elsepush(ch);return NULL;BiTNode *Create_RootTree()BiTree Q,T; while(ch=getchar()!= EOF) if (ch='n')return NULL; else if(ch=':') /构造根节点：= ch=getchar();if(ch!='=') return NULL;if(Q=(BiTNode*)malloc(sizeof(BiTNode)=NULL)return NULL;mems

9、et(Q->s,0x00,sizeof(Q->s);memcpy(Q->s,bt,len);len =0;Q->lchild = NULL;Q->rchild = NULL;if(T=(BiTNode*)malloc(sizeof(BiTNode)=NULL)return NULL;T->lchild = Q;memset(T->s,0x00,sizeof(T->s);memcpy(T->s,":=",2);/继续处理:=后面的数据，作为根节点的右节点if(T->rchild=Create_RTree()=NULL

10、)return NULL;return T; else push(ch);return NULL;void PreOrderTraverse(BiTree T)if(T)printf("%s ",T->s);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);elsereturn;void InOrderTraverse(BiTree T)if(T)InOrderTraverse(T->lchild);printf("%s ",T->s);InOrderTraver

11、se(T->rchild);elsereturn;void PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%s ",T->s);elsereturn;int main()printf("请输入一个中缀表达式：n");BiTree T=NULL;if(T=Create_RootTree()=NULL) return 0;printf("先序遍历：");PreOrde

12、rTraverse(T);printf("n"); printf("中序遍历：");InOrderTraverse(T);printf("n");printf("后序遍历：");PostOrderTraverse(T);printf("n");return 0;2）#include <iostream>#define NULL 0#define Max 50using namespace std;typedef struct nodechar data;struct node *lc

13、,*rc;btnode;void creattree(btnode *&b) /递归创建二叉树char i; cin>>i;if(i='#') b=NULL; elseb=(btnode *)malloc(sizeof(btnode); b->data=i; creattree(*&b->lc); creattree(*&b->rc);void findleafnode(btnode *b) /找出所有叶子结点if(b!=NULL)if(b->lc=NULL&&b->rc=NULL) cout&l

14、t;<b->data<<' 'elsefindleafnode(b->lc);findleafnode(b->rc);btnode *stMax;int front,rear=-1;void allpath(btnode *b) /从叶子结点到根结点的路径if(b!=NULL)rear+; strear=b;/当前结点入栈 if(b->lc=NULL&&b->rc=NULL) /当b为叶子结点时 front=rear; while(front>=0)/输出从根节点到叶子结点的路径 cout<<st

15、front->data<<' ' front-; cout<<endl; rear-; /栈尾指针退一步 /重设栈头指针 else allpath(b->lc); allpath(b->rc); rear-; void main()btnode *b;cout<<"请以先序构造一棵树，无结点时以#代替"cout<<endl; creattree(b); cout<<"叶子结点为："<<endl; findleafnode(b); cout<&l

16、t;endl; cout<<"从所有叶子结点到根结点的路径为："<<endl; allpath(b);cout<<"以上路径中第一条最长路径是："<<endl;五、写出输入数据及运行结果、算法分析1）2）六、心得体会树是常用的数据结构。通过实验加深了我对二叉树的遍历的认识，巩固了课本中所学的关于树的基本算法。按要求完成了实验内容。通过实验，有如下几点收获和体会：1、通过实验还提高了一点改错能力，对于一些常见问题加深了印象。2、编程需要有耐心，尤其实在单步调试的时候，更是马虎不得，有时候关键就是那么一步，错过了就得从头来过了。编程也需要勇气，要勇于发现自己的错误，也要勇于推翻自己之前的思路，要坚信“没有最好，只有更好”。编程，最好是一鼓作气，得天天“摸摸”它，时时想着它，要是过一阵再去碰它那就得先去读懂自己的程序了，一切的一切