《建立二叉树二叉链表存储结构实现有关操作》由会员分享,可在线阅读,更多相关《建立二叉树二叉链表存储结构实现有关操作(4页珍藏版)》请在金锄头文库上搜索。
1、一、实验题目:建立二叉树二叉链表存储结构实现有关操作.二、问题描述:建立二叉树的二叉链表存储结构实现以下操作(选择其中的两个做)(1)输出二叉树(2)先序遍历二叉树(3)中序遍历二叉树(4)后序遍历二叉树(5)层次遍历二叉树三、需求分析:我选做以上的2.3两小问(1) 建立二叉链表树(2) 先序遍历二叉树:若二叉树为空,则空操作;否则先访问根结点,再先序遍历左子树,最后先序遍历右子树(3) 中序遍历二叉树:若二叉树为空,则空操作;否则先访问根结点,再中序遍历左子树,最后中序遍历右子树测试数据:a,b,c,d,e测试输出结果为先根遍历:a,b,d,c,e中根遍历:b,d,a,e,c四、概要设计:
2、(1) 结点结构定义:structbtnodechardata;/数据bitreptrlchild;/左节点指针bitreptrrchild;/右节点指针;(2) 二叉树的定义与初始化:bitreptrCreateTree()bitreptra,b,c,d,e;bitreptrnodes5;for(intj=0;jlchild=NULL;nodesj-rchild=NULL;a=nodes0;b=nodes1;c=nodes2;d=nodes3;e=nodes4;a-data=a;a-lchild=b;a-rchild=c;b-data=b;b-rchild=d;c-data=c;c-lchi
3、ld=e;d-data=d;e-data=e;returna;voidvisit(constbitreptrnode)coutdatalchild);preorder(node-rchild);(4)中根遍历:voidinorder(constbitreptrroot)bitreptrnode=root;if(node!=NULL)inorder(node-lchild);visit(node);inorder(node-rchild);五、详细设计及模块代码:#includemalloc.h#includeiostream.htypedefstructbtnode*bitreptr;stru
4、ctbtnode/数据/左节点指针/右节点指针/建立一个树,函数返回一个树的头指针chardata;bitreptrlchild;bitreptrrchild;bitreptrCreateTree()bitreptra,b,c,d,e;bitreptrnodes5;for(intj=0;jlchild=NULL;nodesj-rchild=NULL;a=nodes0;b=nodes1;c=nodes2;d=nodes3;e=nodes4;a-data=a;a-lchild=b;a-rchild=c;b-data=b;b-rchild=d;c-data=c;c-lchild=e;d-data=d
5、;e-data=e;returna;voidvisit(constbitreptrnode)coutdatalchild);preorder(node-rchild);/中根遍历voidinorder(constbitreptrroot)bitreptrnode=root;if(node!=NULL)inorder(node-lchild);visit(node);inorder(node-rchild);intmain(intargc,char*argv)bitreptrroot;root=CreateTree();coutvv先根遍历vvendl;preorder(root);coutvv中根遍历vvendl;inorder(root);return0;六、运行结果:七、经验小结:运用递归的思想在做二叉树遍历的时候很重要,可以起到化繁为简的作用。