2022年数据结构二叉树的建立和遍历 .pdf
数据结构实验三二叉树的建立和遍历一、实验目的1、掌握二叉树链式存储的类型定义及实现。2、掌握二叉树链式存储的各类基本运算方法。如二叉树的创建、遍历、查找等运算。3、掌握二叉树用不同方法表示所对应的不同输入形式。4、掌握二叉树中个重要性质在解决实际问题中的应用。二、实验内容建立二叉树并实现各种遍历：1、创建二叉树2、用递归方法实现二叉树的各种遍历3、求二叉树的深度、结点数目、叶子结点数目在算法实现上，从算法的效率看，递归方法书写形式较为简洁，更为直观，一般具有较好的空间效率。附加要求：采用先 中 后序用非递归的方法遍历二叉树。重点：理解遍历二叉树的过程.三、算法实现（读懂程序，并进行程序填空）#includestdio.h#includestring.h#include#include#define Max 20 /结点的最大个数using namespace std;typedef struct node char data;struct node*lchild,*rchild;名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -BinTNode;/自定义二叉树的结点类型typedef BinTNode*BinTree;/定义二叉树的指针int NodeNum,leaf;/NodeNum为结点数，leaf为叶子数BinTree CreatBinTree(void)/=基于先序遍历算法创建二叉树=/=要求输入先序序列，其中加入虚结点#以示空指针的位置=BinTree T;char ch;if(ch=getchar()=#)return(NULL);/读入#，返回空指针 else T=(BinTNode*)malloc(sizeof(BinTNode);/生成结点T-data=ch;T-lchild=CreatBinTree();/构造左子树T-rchild=CreatBinTree();/构造右子树return(T);void Preorder(BinTree bt)/=NLR 先序遍历=if(bt!=NULL)printf(%c,bt-data);/访问结点Preorder(bt-lchild);/先序遍历左子树名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -Preorder(bt-rchild);/先序遍历右子树 void Inorder(BinTree bt)/=LNR 中序遍历=void Postorder(BinTree bt)/=LRN 后序遍历=int TreeDepth(BinTree bt)/=采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=int hl,hr,max;if(bt)名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -hl=TreeDepth(bt-lchild);/求左深度hr=TreeDepth(bt-rchild);/求右深度max=hlhr?hl:hr;/取左右深度的最大值NodeNum=NodeNum+1;/求结点数if(hl=0&hr=0)leaf=leaf+1;/若左右深度为 0，即为叶子。return(max+1);else return(0);void Levelorder(BinTree T)/=利用先进先出（FIFO）队列，按层次遍历二叉树=int front=0,rear=1;BinTNode*cqMax,*p;/定义结点的指针数组cq cq1=T;/根入队 while(front!=rear)front=(front+1)%NodeNum;p=cqfront;/出队printf(%c,p-data);/出队，输出结点的值if(p-lchild!=NULL)rear=(rear+1)%NodeNum;cqrear=p-lchild;/左子树入队if(p-rchild!=NULL)名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -rear=(rear+1)%NodeNum;cqrear=p-rchild;/右子树入队 void main()/=主函数=BinTree root;int i,depth;printf(n);printf(Creat Bin_Tree；Input preorder:);/输入完全二叉树的先序序列，/用#代表虚结点，如 ABD#CE#F#root=CreatBinTree();/创建二叉树，返回根结点 do /从菜单中选择遍历方式，输入序号。printf(t*select*n);printf(t1:Preorder Traversaln);printf(t2:Iorder Traversaln);printf(t3:Postorder traversaln);printf(t4:PostTreeDepth,Node number,Leaf numbern);printf(t5:Level Depthn);/按层次遍历之前，先选择4，求出该树的结点数。printf(t0:Exitn);printf(t*n);scanf(%d,&i);/输入菜单序号（0-5）名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -switch(i)case 1:printf(Print Bin_tree Preorder:);Preorder(root);break;case 2:printf(Print Bin_Tree Inorder:);Inorder(root);break;case 3:printf(Print Bin_Tree Postorder:);Postorder(root);break;case 4:depth=TreeDepth(root);/求树的深度及叶子数printf(BinTree Depth=%d BinTree Node number=%d,depth,NodeNum);printf(BinTree Leaf number=%d,leaf);break;case 5:printf(LevePrint Bin_Tree:);Levelorder(root);break;default:exit(1);printf(n);while(i!=0);注意：建立二叉树时，没有左右子树以#代替名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -
