创建二叉树（递归）

非递归创建二叉树，需要用到栈，的确太烦了。这里只给出递归创建二叉树的方法。

[cpp]
#include "stdafx.h"
#include<iostream>
using namespace std;
typedef struct BiTreeNode
{
    char data;
    BiTreeNode* left;
    BiTreeNode* right;
}BiTreeNode,*BiTree;

//均为先序创建，即按先序的顺序输入，空节点输入'#'
BiTreeNode* Create()
{
    char ch;
    cin>>ch;
    BiTreeNode* root;

    if(ch=='#')
        return NULL;
    else
    {
        root=new BiTreeNode;
        root->data=ch;
        root->left=Create();
        root->right=Create();
        return root;
    }
}

void CreateBiTree(BiTree &t)//必须用&
{
     char ch;
     cin>>ch;
     if(ch=='#')
         t=NULL;
     else
     {
         t=new BiTreeNode;
         if(!t)
             return;
         t->data=ch;
         CreateBiTree(t->left);
         CreateBiTree(t->right);
     }
}

//先序遍历
void PreOrderTraverse(BiTreeNode* t)
{
    if(t)
    {
        cout<<t->data<<" ";
        PreOrderTraverse(t->left);
        PreOrderTraverse(t->right);
    }

}
int _tmain(int argc, _TCHAR* argv[])
{
    BiTree t=NULL;
    //t=Create();//方法1
    CreateBiTree(t);//方法2
    PreOrderTraverse(t);
    cout<<endl;
    return 0;
}
以上给出了递归创建二叉树的二种方法，输入时都需要输入完全二叉树。

这里再增加一种方法创建二叉树，方法如下：
[cpp]
// node.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

struct node
{
    char value;
    node* left;
    node* right;
    node(char v,node* l=NULL,node* r=NULL):value(v),left(l),right(r)
    {
    }
};

void preordertraverse(node* t)
{
    if(t)
    {
        cout<<t->value<<" ";
        preordertraverse(t->left);
        preordertraverse(t->right);
    }

}

//递归删除，将new的节点delete，防内存泄漏
void deletetree(node* t)
{
    if(t->left==NULL&&t->right==NULL)
    {
        delete t;
        t=NULL;
    }
    if(!t)
        return;
    else
    {
        if(t->left)
            deletetree(t->left);
        if(t->right)
            deletetree(t->right);
        if(t->left==NULL&&t->right==NULL)
        {
            delete t;
            t=NULL;
        }
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    node* t1=new node('7');
    node* t2=new node('8');
    node* t3=new node('5',t1,t2);
    node* t4=new node('4');
    node* t5=new node('6');
    node* t6=new node('2',t4,t3);
    node* t7=new node('3',NULL,t5);
    node* t8=new node('1',t6,t7);

    preordertraverse(t8);

    deletetree(t8);
www.zzzyk.com
    cout<<endl;
    return 0;
}

此方法通过构造函数的方法，处理节点之间的关系，比较方便。

补充：软件开发 , C++ ,