递归法创建二叉树

用递归法创建二叉树

定义二叉树的结构如下：

typedef struct TreeNode{
    char a;
    struct TreeNode *left;
    struct TreeNode *right; 
}Tree;

定义的结构体Tree里有三个成员，a，左子树left，右子树right

二叉树创建遍历规则:

1.前序:根-左-右

2.中序:左-根-右

3.后序:左-右-根

定义的函数:

void CreateTree(TreeNode * &T)//先序法创建二叉树 
{
 
    char data;
    cin>>data;
    if(data=='#')
        T=NULL;
    else 
    {
         T=new TreeNode;
         T->a=data;
         CreateTree(T->left);
         CreateTree(T->right);
    }
}

void PreorderTree(TreeNode *T)//前序遍历二叉树 
{
    if(T==NULL)
        return;
    cout<<T->a<<" ";
    PreorderTree(T->left);
    PreorderTree(T->right);
}

void InorderTree(TreeNode *T)//中序遍历二叉树 
{
    if(T==NULL)
        return;
    InorderTree(T->left);
    cout<<T->a<<" ";
    InorderTree(T->right);
}

void PostorderTree(TreeNode *T)//后序遍历二叉树
{
    if(T==NULL)
        return;
    PostorderTree(T->left);
    PostorderTree(T->right);
    cout<<T->a<<" ";
}

主要原理：

先输入要创建的二叉树序列(#表示该子树为空），通过递归和先序法创建一棵二叉树，从根节点依次递归左子树直至左子树为空，再从该子树依次递归右子树依次返回直至根节点，之后再从根节点递归右子树。
之后分别用前序遍历二叉树，中序遍历二叉树，后序遍历二叉树的方法遍历二叉树后输出。

主函数如下：

int main()
{
	cout<<"请输入先序创建二叉树的序列:"<<endl;
	 Tree *T;
	 CreateTree(T);
	 cout<<"前序遍历的结果为:";
	 PreorderTree(T);
	 cout<<endl;
	 cout <<"中序遍历的结果为:";
	 InorderTree(T);
	 cout<<endl;
	 cout <<"后序遍历的结果为:";
	 PostorderTree(T);
	 return 0;
}

具体代码如下：

二叉树示例：

输入: A B D F # # # E # # C G # # #

创建的二叉树如下：

前序遍历的结果为:A B D F E C G
中序遍历的结果为:F D B E A G C
后序遍历的结果为:F D B E A G C