/************************************************************************
* Create Date :2014/12/10
* Author :zhuang_569
* Description :二叉树的创建
*************************************************************************/
#include "iostream"
using namespace std;
typedef char ELEM_TYPE;
typedef struct BiTNode
{
ELEM_TYPE data;
struct BiTNode *lchild;
struct BiTNode *rchild;
}BiTNode,*pBiTNode;
//函数声明
pBiTNode CreateBeTree(void);
void PreOrderTraverse(pBiTNode pRoot);
void InOrderTraverse(pBiTNode pRoot);
void PostOrderTraverse(pBiTNode pRoot);
int main(void)
{
pBiTNode pBeTreeRoot;
pBeTreeRoot = CreateBeTree(); //创建二叉树根节点
cout<<"二叉树先序输出:";
PreOrderTraverse(pBeTreeRoot);
cout<<"\n"<<"二叉树中序输出:";
InOrderTraverse(pBeTreeRoot);
cout<<"\n"<<"二叉树后序输出:";
PostOrderTraverse(pBeTreeRoot);
return 0;
}
//利用先序遍历建立二叉树
pBiTNode CreateBeTree(void)
{
pBiTNode pRoot;
ELEM_TYPE ch;
cin >> ch;
if('@' == ch)
{
pRoot = NULL;
}
else
{
pRoot = new BiTNode; //为新的节点分配内存空间
pRoot->data = ch;
pRoot->lchild = CreateBeTree();
pRoot->rchild = CreateBeTree();
}
return pRoot; //返回根节点的地址
}
//先序遍历二叉树
void PreOrderTraverse(pBiTNode pRoot)
{
if(NULL != pRoot)
{
cout << pRoot->data;
PreOrderTraverse(pRoot->lchild);
PreOrderTraverse(pRoot->rchild);
}
}
//中序遍历二叉树
void InOrderTraverse(pBiTNode pRoot)
{
if(NULL != pRoot)
{
InOrderTraverse(pRoot->lchild);
cout << pRoot->data;
InOrderTraverse(pRoot->rchild);
}
}
//后序遍历二叉树
void PostOrderTraverse(pBiTNode pRoot)
{
if(NULL != pRoot)
{
PostOrderTraverse(pRoot->lchild);
PostOrderTraverse(pRoot->rchild);
cout << pRoot->data;
}
}
树:
测试结果: