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

学了蛮久的数据结构了，看过很多的数据结构的书，讲到二叉树这一树结构类型的时候时，很多教材只说了遍历二叉树的方法，却没有讲怎么构造二叉树。下面是我看过别人的二叉树的构造方法之后，自己又写的怎样构造一棵二叉树的方法。采用线序的方法构造的，下面给出了现成的代码。拿出来给大家分享一下。（成功是站在别人的肩膀上）#include#includeusing namespace std;template /二叉树存储节点的定义struct BiNodeT data;/节点的数据域BiNode * lchild;/二叉树的左节点BiNode * rchild;/二叉树的右节点;template /二叉树的定义，用类实现class BiTreepublic:BiTree()/构造函数，构造一棵二叉树cout请输入二叉树的节点信息，空的节点用#代替：root = Create();BiTree()/析构函数，析构一颗二叉树Release(root);/释放二叉树的节点内存void PreOrd(BiNode *root);/先序遍历二叉树void InOrd(BiNode *root);/中序遍历二叉树void PostOrd(BiNode *root);/后续遍历一颗二叉树BiNode * GetRoot();/获取根节点private:BiNode * root;/根节点BiNode * Create();/递归构造一棵二叉树void Release(BiNode *root);/释放一棵二叉树的节点的内存;/通过递归构造一棵二叉树template BiNode *BiTree:Create()BiNode * root;/定义二叉树的节点char ch;cinch;if(ch = #) root = NULL;/空节点elseroot = new BiNode;/为节点分配内存空间root-data = ch;/节点的数据域赋值root-lchild = Create();/递归构造左子树root-rchild = Create();/递归构造右子树return root;/返回指向根节点的指针template BiNode * BiTree:GetRoot()return this-root;/释放二叉树的内存template void BiTree:Release(BiNode * root)if(root != NULL)Release(root-lchild);/释放左子树的节点内存Release(root-rchild);/释放右子树的节点内存delete root;/先序遍历二叉树template void BiTree:PreOrd(BiNode *root)if(root != NULL)/如果节点非空，则以先序递归遍历二叉树coutdatalchild);/递归遍历左子树PreOrd(root-rchild);/递归遍历右子树/中序遍历二叉树template void BiTree:InOrd(BiNode *root)if(root != NULL)/如果节点非空，则以中序递归遍历二叉树InOrd(root-lchild);/递归遍历左子树coutdatarchild);/递归遍历右子树/后续遍历二叉树template void BiTree:PostOrd(BiNode *root)if(root != NULL)/如果节点非空，则以后序递归遍历二叉树PostOrd(root-lchild);/递归遍历左子树PostOrd(root-rchild);/递归遍历右子树coutdata ;/访问节点的数据int main(void)BiTree bitree;BiNode *root = bitree.GetRoot();cout先序遍历：endl;bitree.PreOrd(root);coutendl;cout后续遍历；endl;bitree.PostOrd(root);coutendl;cout中序遍历：endl;bitree.InOrd(root);coutendl;return 0;测试数据如下输入:abd#g