創建二叉樹（遞歸）

非遞歸創建二叉樹，需要用到棧，的確太煩了。這裡只給出遞歸創建二叉樹的方法。

[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.2cto.com
    cout<<endl; 
    return 0; 
} 

此方法通過構造函數的方法，處理節點之間的關系，比較方便。