递归法先序构造一棵二叉树

《递归法先序构造一棵二叉树》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学了蛮久的数据结构了，看过很多的数据结构的书，讲到二叉树这一树结构类型的时候时，很多教材只说了遍历二叉树的方法，却没有讲怎么构造二叉树。下面是我看过别人的二叉树的构造方法之后，自己又写的怎样构造一棵二叉树的方法。采用线序的方法构造的，下面给出了现成的代码。拿出来给大家分享一下。（成功是站在别人的肩膀上）#include#includeusingnamespacestd;template//二叉树存储节点的定义structBiNode{Tdata;//节点的数据域BiNode*lchil

2、d;//二叉树的左节点BiNode*rchild;//二叉树的右节点};template//二叉树的定义，用类实现classBiTree{public:BiTree()//构造函数，构造一棵二叉树{cout<<"请输入二叉树的节点信息，空的节点用#代替："<root=Create();}~BiTree()//析构函数，析构一颗二叉树{Release(root);//释放二叉树的节点内存}voidPreOrd(BiNode*root);//先序遍历二叉树voidInOrd(BiNode*

3、root);//中序遍历二叉树voidPostOrd(BiNode*root);//后续遍历一颗二叉树BiNode*GetRoot();//获取根节点private:BiNode*root;//根节点BiNode*Create();//递归构造一棵二叉树voidRelease(BiNode*root);//释放一棵二叉树的节点的内存};//通过递归构造一棵二叉树templateBiNode*BiTree::Create(){BiNode*root;//定义二叉树的节点charch

4、;cin>>ch;if(ch=='#')root=NULL;//空节点else{root=newBiNode;//为节点分配内存空间root->data=ch;//节点的数据域赋值root->lchild=Create();//递归构造左子树root->rchild=Create();//递归构造右子树}returnroot;}//返回指向根节点的指针templateBiNode*BiTree::GetRoot(){returnthis->root;}//释放二叉树的内存template

5、voidBiTree::Release(BiNode*root){if(root!=NULL){Release(root->lchild);//释放左子树的节点内存Release(root->rchild);//释放右子树的节点内存}deleteroot;}//先序遍历二叉树templatevoidBiTree::PreOrd(BiNode*root){if(root!=NULL)//如果节点非空，则以先序递归遍历二叉树{cout<data<<"";//访问节点的数据PreOrd(root

6、->lchild);//递归遍历左子树PreOrd(root->rchild);//递归遍历右子树}}//中序遍历二叉树templatevoidBiTree::InOrd(BiNode*root){if(root!=NULL)//如果节点非空，则以中序递归遍历二叉树{InOrd(root->lchild);//递归遍历左子树cout<data<<"";//访问节点的数据InOrd(root->rchild);//递归遍历右子树}}//后续遍历二叉树templatevoidBiTr

7、ee::PostOrd(BiNode*root){if(root!=NULL)//如果节点非空，则以后序递归遍历二叉树{PostOrd(root->lchild);//递归遍历左子树PostOrd(root->rchild);//递归遍历右子树cout<data<<"";//访问节点的数据}}intmain(void){BiTreebitree;BiNode*root=bitree.GetRoot();cout<<"先序遍历："<

8、l;cout<<"后续遍历；"<