二叉树的各种创建方法_二叉树的建立

1.前序创建

#include<stdlib.h>
#include<malloc.h>
#include<iostream>
#include<stack>
#include<queue>
using namespace std;
typedef  char ElemType;
typedef struct  BtNode
{
	BtNode *leftchild;
	BtNode *rightchild;
	ElemType data;
}BtNode,*BinaryTree;
//购买结点
BtNode *Buynode()
{
	BtNode *p=(BtNode *)malloc(sizeof(BtNode));
	if(NULL==p)  exit(1);
	memset(p,0,sizeof(BtNode));
	return p;
}
void *Freenode(BtNode *ptr)
{
	free(ptr);
}

第一种建树方法(通过结点进行创建二叉树)

//方法一
//前序创建二叉树
void *PreCreateTree(BinaryTree  *ptr)
{
	char ch;
	cin>>ch;
	if(ch!='#'||ptr!=NULL)
        {
		*ptr=Buynode();
		(*ptr)->data=ch;
		PreCreateTree(&(*ptr)->leftchild);
		PreCreateTree(&(*ptr)->rightchild);
	}
}
int main()
{
	BinaryTree root=NULL;
	PreCreateTree(&root);
}

第二种创建方法：

//利用指针  
void Createtree4(BtNode ** const p,char *&str)  
{  
    if(  str != NULL && *str != '#')  
    {  
        (*p) = Buynode();  
        (*p)->data = *str;  
        Createtree4(&(*p)->leftchild,++str);  
        Createtree4(&(*p)->rightchild,++str);  
    }  
  
}

第三种用前序方法创建二叉树（通过传入空，进行创建）

BtNode *CreateTree()
{
	ElemType x;
	BtNode *s=NULL;
	cin>>x;
	if(x!=END)
	{
		s=Buynode();
		s->data=x;
		s->leftchild=CreateTree();
		s->rightchild=CreateTree();
	}
	return s;
}

第四种用前序创建二叉树，通过传入引用(如果不是传入的是引用，会出现问题)

//传引用建树  
BtNode *Createtree1(char *&str)  
{  
     BtNode *p = NULL;  
     if( str != NULL && *str != '#')  
     {  
         p = Buynode();  
         p->data = *str;  
         p->leftchild = Createtree1(++str);  
         p->rightchild = Createtree1(++str);  
     }  
     return p;  
       
}

第五种创建方法：

//引用转换成二级指针建树  
BtNode *Createtree2(char ** const str)  
{  
    BtNode *p = NULL;  
    if( str != NULL  && *str != NULL && **str != '#')  
    {  
        p = Buynode();  
        p->data = **str;  
        p->leftchild = Createtree1(++*str);  
        p->rightchild = Createtree1(++*str);  
    }  
    return p;  
  
}  

第六种创建方法：

 
//给一个结点建立左右孩子  
void Createtree3(BtNode *&p,char *&str)  
{  
    if(  str != NULL && *str != '#')  
    {  
        p = Buynode();  
        p->data = *str;  
        Createtree3(p->leftchild,++str);  
        Createtree3(p->rightchild,++str);  
    }  
}  

2.用前序和中序创建二叉树

方法一：

//用前序和中序创建二叉树
*BtNode* CreateTreePI(char ps[],char is[],int n )
{
	if(n<=0)
	{
		return NULL;
	}
	BtNode* p=(BtNode*)malloc(sizeof(BtNode));
	int i=0;
	int m;
	while(i<n)
	{
		if(ps[0]==is[i])
		{
			m=i;
			break;
		}
		++i;
	}
	if(i>=n)
	{
		return NULL;
	}
	p->data=ps[0];
	p->leftchild=CreateTreePI(ps+1,is,m);
	p->rightchild=CreateTreePI(ps+m+1,is+m+1,n-m-1);
	return p;
}
int main()
{
	char ps[]="ABDGHCEIF";
	char is[]="GDHBAEICF";
	int len=strlen(ps);
	CreateTreePI(ps,is,len);
}

方法二：

int Findvalue(char *is,ElemType p,int n)  
{  
     for(int i = 0;i < n;++i)  
     {  
         if(is[i] == p)  
             return i;  
     }  
     return -1;  
}  
//根据前序和中序建立一个二叉树  
BtNode *CreatePM(char *pr,char *is,int n)  
{  
     ElemType p = pr[0];  
     BtNode *tmp = NULL;  
     if(n > 0)  
     {  
         int m = Findvalue(is,p,n);  
         if(-1 == m) exit(1);  
         tmp  = Buynode();  
         tmp->data = p;  
         tmp->leftchild = CreatePM(pr+1,is,m);  
         tmp->rightchild = CreatePM(pr+m+1,is+m+1,n-m-1);  
      
     }  
     return tmp;  
}  
BtNode *CreatetreePM(char *pr,char *is,int n)  
{  
      if(pr == NULL || is == NULL || n < 1) return NULL;  
      return  CreatePM(pr,is,n);  
        
} 

3.用中序和后序创建二叉树

方法一：

//用中序和后序创建二叉树
BtNode* CreateTreeIL(char is[],char ls[],int n)
{
	if(n<=0)
	{
		return NULL;
	}
	BtNode *p=(BtNode*)malloc(sizeof(BtNode));
	int i=0;
	int m;
	while(i<n)
	{
		if(ls[n-1]==is[i])
		{
			m=i;
			break;
		}
		++i;
	}
	if(i>=n)
	{
		return NULL;
	}
	p->data=ls[n-1];
	p->leftchild= CreateTreeIL(is,ls,m);
	p->rightchild= CreateTreeIL(is+m+1,ls+m,n-m-1);
	return p;
}
int main()
{
	char is[]="GDHBAEICF";
	char ls[]="GHDBIEFCA";
	int len=strlen(is);
	CreateTreeIL(is,ls,len);
} 

方法二：

// 根据中序和后序建立一个二叉树  
BtNode *CreateML(char *mi,char *la,int n)  
{  
    ElemType p = la[n-1];  
    BtNode *tmp = NULL;  
    if(n > 0)  
    {  
        int m = Findvalue(mi,p,n);  
        if(-1 == m) exit(1);  
        tmp  = Buynode();  
        tmp->data = p;  
        tmp->leftchild = CreateML(mi,la,m);  
        tmp->rightchild = CreateML(mi+m+1,la+m,n-m-1);  
    }  
    return tmp;  
}  
BtNode *CreatetreeML(char *mi,char *la,int n)  
{  
    if(mi == NULL || la == NULL || n < 1) return NULL;  
    return  CreateML(mi,la,n);  
  
}