二叉树的建立与遍历.doc

《二叉树的建立与遍历.doc》由会员分享，可在线阅读，更多相关《二叉树的建立与遍历.doc（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、一 、实验目的1学会实现二叉树结点结构和对二叉树的基本操作。2掌握对二叉树每种操作的具体实现，学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。二 、实验要求1认真阅读和掌握二叉树的结构、构造和遍历等内容。2编写完整程序完成下面的实验内容并上机运行。3整理并上交实验报告。 三、实验内容1编写程序任意输入二叉树的结点个数和结点值，构造一棵二叉树，采用三种递归遍历算法(前序、中序、后序)对这棵二叉树进行遍历并计算出二叉树的高度。2 .编写程序生成下面所示的二叉树，并采用先序遍历的非递归算法对此二叉树进行遍历。 四、实验步骤（描述实验步骤及中间的结果或现象。在实验中做了什么事情，怎么做的，

2、发生的现象和中间结果）代码：#include#includetypedef int ElemType;typedef bool Status; #define OK 1 #define ERROR 0#define OVERFLOW -2#define STACK_INT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量/树typedef struct NodeElemType data;struct Node *lchild,*rchild;BiTNode,*BiTree;/栈typedef struct BiTree *base;

3、 BiTree *top; int stacksize;/当前已分配的存储空间SqStack;/ /构造一个空栈Status InitStack(SqStack &S)S.base = (BiTree *) malloc(sizeof(BiTree); if(!S.base) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INT_SIZE; return OK;/插入元素e为栈顶元素Status Push(SqStack &S, BiTree e) if(S.top - S.base = S.stacksize) /若栈满，则追加存储空

4、间S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree); if(!S.base) return ERROR; S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S.top = e; S.top+; return OK; /删除S的栈顶元素，并用e返回Status Pop(SqStack &S,BiTree &e) if(S.base = S.top) return ERROR; S.top-; e = *S.top; retu

5、rn OK; / 若栈S为空栈，则返回OK，否则返回ERROR Status StackEmpty(SqStack S) if(S.top = S.base) return OK; else return ERROR; /-/先序创建二叉树Status CreatBiTree(BiTree &T)int ch; scanf(%d,&ch);if(ch=0) T=NULL;elseif(!(T=(BiTree)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch; CreatBiTree(T-lchild );CreatBiTree(T-rchild );

6、 return OK;/访问数据Status Visit(ElemType e) printf(%d ,e); return OK;/先序遍历二叉树Status PreOrder(BiTree T)if(T)Visit(T-data); / 访问结点 PreOrder(T-lchild); / 遍历左子树 PreOrder(T-rchild);/ 遍历右子树 return OK; /中序遍历Status InOrder(BiTree &T)if(T)InOrder(T-lchild); Visit(T-data); InOrder(T-rchild); return OK;/后序遍历Statu

7、s PostOrder(BiTree & T)if(T)PostOrder(T-lchild); PostOrder(T-rchild); Visit(T-data); return OK;/求二叉树的深度(后序遍历)int Depth(BiTree &T) int depthval,depthLeft,depthRight;if(!T) depthval=0; elsedepthLeft=Depth(T-lchild); depthRight=Depth(T-rchild); depthval=1+(depthLeftdepthRight?depthLeft:depthRight); ret

8、urn depthval;/先序遍历二叉树非递归算法Status InOrderTraverse(BiTree &T)BiTree p; SqStack S;InitStack(S);p=T;while(p|!StackEmpty(S)if(p) printf(%2d,p-data);Push(S,p);p=p-lchild;else Pop(S,p); p=p-rchild ;return OK;/计算二叉链表存储的二叉树中度数为1的结点数void Count(BiTree T, int& count) if ( T ) if (!T-lchild&T-rchild)| (!T-rchild

9、&T-lchild) count+; / 对结点计数 Count( T-lchild, count); Count( T-rchild, count); void main()BiTree root;int count=0; root=NULL; printf(先序输入数据(以0为空):);CreatBiTree(root);printf(先序遍历:); PreOrder(root); printf(n);printf(中序遍历:); InOrder(root); printf(n);printf(后序遍历:); PostOrder(root); printf(n);printf(树的深度为：

10、);printf(%dn,Depth(root);printf(先序遍历(非递归):);InOrderTraverse(root);printf(n度数为1的结点数为：);Count(root,count);printf(%d,count);printf(n);五、实验结果与讨论（描述最终得到的结果，并进行分析说明，可能的误差原因）六、总结（说明实验过程中遇到的问题及解决办法；新发现或个人的收获；未解决/需进一步研讨的问题或建议新实验方法等）七、思考与提高1如何计算二叉链表存储的二叉树中度数为1的结点数？2已知有棵以二叉链表存储的二叉树，root指向根结点，p指向二叉树中任一结点，如何求从根结

11、点到p所指结点之间的路径?1void Count(BiTree T, int& count) if ( T ) if (!T-lchild&T-rchild)| (!T-rchild&T-lchild) count+; / 对结点计数 Count( T-lchild, count); Count( T-rchild, count); 2. #include#includetypedef int ElemType;typedef bool Status; #define OK 1 #define ERROR 0#define OVERFLOW -2#define STACK_INT_SIZE 1

12、00 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量/树typedef struct NodeElemType data;struct Node *lchild,*rchild,*parent;BiTNode,*BiTree;/栈typedef struct BiTree *base; BiTree *top; int stacksize;/当前已分配的存储空间SqStack;/构造一个空栈Status InitStack(SqStack &S)S.base = (BiTree *) malloc(sizeof(BiTree); if(!S.base

13、) exit(OVERFLOW); S.top = S.base; S.stacksize = STACK_INT_SIZE; return OK;/插入元素e为栈顶元素Status Push(SqStack &S, BiTree e) if(S.top - S.base = S.stacksize) /若栈满，则追加存储空间 S.base = (BiTree *) realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(BiTree); if(!S.base) return ERROR; S.top = S.base + S.stacksi

14、ze; S.stacksize += STACKINCREMENT; *S.top = e; S.top+; return OK; /删除S的栈顶元素，并用e返回Status Pop(SqStack &S,BiTree &e) if(S.base = S.top) return ERROR; S.top-; e = *S.top; return OK; / 若栈S为空栈，则返回OK，否则返回ERROR Status StackEmpty(SqStack S) if(S.top = S.base) return OK; else return ERROR; /-/先序创建二叉树Status Cr

15、eatBiTree(BiTree &T,BiTree q)int ch;BiTree p;p=q; scanf(%d,&ch);if(ch=0) T=NULL;elseif(!(T=(BiTree)malloc(sizeof(BiTNode)exit(OVERFLOW);T-data=ch;T-parent=p;p=T; CreatBiTree(T-lchild,p ); CreatBiTree(T-rchild,p ); return OK;BiTree Search(BiTree &T,int e)BiTree p; SqStack S;InitStack(S);p=T;while(p|!

16、StackEmpty(S)if(p) if(p-data=e) return p;Push(S,p);p=p-lchild;else Pop(S,p); p=p-rchild ; void Print(BiTree T,BiTree &p) SqStack S;InitStack(S);while(p-data !=T-data) Push(S,p); p=p-parent;printf(%d ,p-data); while(StackEmpty(S)=0)Pop(S,p); printf(%d ,p-data);void main()BiTree T,p,q=NULL;int e; printf(先序输入数据(以0为空):); CreatBiTree(T,q); printf(到达结点数据为：); scanf(%d,&e);p=Search(T,e);printf(根到结点路径为：);Print(T,p);printf(n);9