树——构造遍历二叉树

AngelNH

发布于 2020-04-16 11:18:08

5590

发布于 2020-04-16 11:18:08

文章被收录于专栏：AngelNI

构造二叉树，遍历二叉树，先序+中序构造二叉树后序遍历，中序+后序构造二叉树先序遍历。

构造二叉树

利用二叉链表构造二叉树的每一个结点

typedef struct TNode
{
    char data;
    struct TNode *lchild,*rchild;
}*Tree;

先序遍历顺序建立二叉链表

#include<stdio.h>
#include<stdlib.h>
typedef struct TNode
{
    char data;
    struct TNode *lchild,*rchild;
}TNode,*Tree;
void Create(TNode *T)
{
    char ch;
    scanf("%c",&ch);
    if(ch=='#')
        *T=NULL;
    else
    {
        T=(TNode *)malloc(sizeof(TNode));
        if(!*T)
            exit(-1);
        T->data=ch;
        Create(T->lchild);
        Create(T->rchild);
    }
}
int main()
{
    TNode *T;
    printf("输入树(#代表空节点):");
    Create(T);
    //我是省略号//
}

遍历二叉树

//二叉树的先序遍历//
void travel_pre(TNode T)
{
    if(T==NULL)
        return ;
    printf("%c ",T->data);
    travel_pre(T->lchild);
    travel_pre(T->rchild);
}
//二叉树的中序遍历//
void travel_in(TNode T)
{
   if(T==NULL)
       return ;
   travel_in(T->lchild);
   printf("%C ",T->data);
   travel_in(T->rchild);
}
//二叉树的后序遍历//
void travel_post(TNode T)
{
    if(T==NULL)
        return;
    travel_post(T->lchild);
    travel_post(T->rchild);
    printf("%c ",T->data);
}

先序+中序构造二叉树

根据先序和中序遍历结果还原二叉树基础理论比较好理解，多做几道这些类似的题，也能孰能生巧。关键之处，还是在于代码实现。

这是一道OJ题，请移步HDU1710

因为还原二叉树是一个递归的问题，将复杂地问题简化为一个个小问题，所以就拿三个结点的二叉树举栗。

先序：ABC；

中序：BAC；

我们都知道先序遍历是根左右，而中序遍历是左根右，我们可以通过先序找到根节点，根据中序中根节点的位置，就可以找到根节点的左子树（左孩子），和右子树（右孩子）；根据这个规则就可以还原一颗二叉树了。

例如下面的例子。

不难发现根节点是A，那么中序中的1~~k就为左子树，k~~尾就为右子树。同理，先序中pre+1~~pre+k为左子树，pre+k+1~~尾为右子树。其他以此类推。

#include<stdlib.h>
#include<stdio.h>
struct TNode
{
	int data;
	TNode * lchild,* rchild;
}*Tree;
int a[1000],b[1000];
int n;
//代码的核心之处//
TNode * Creat(int *a,int *b,int n)
{
	TNode * T;
	for(int i =0;i < n ; ++i)
	{
		if(a[0]==b[i])
		{
			T = (TNode *)malloc(sizeof(TNode));
			T->data = b[i];
			T->lchild = Creat(a+1,b,i);
			T->rchild = Creat(a+i+1,b+i+1,n-i-1);
			return T; 
		}
	}
	return NULL;
}
//后序遍历二叉树
void travel_post(TNode *R)
{
	if(R!=NULL)
	{
		travel_post(R->lchild);
		travel_post(R->rchild);
		if(R==Tree)
		{
			printf("%d\n",R->data);
		}
		else{
			printf("%d ",R->data);
		}
	}
}
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		Tree = NULL;
        //先序
		for(int i =0;i<n;++i)
		{
			scanf("%d",&a[i]);
		}
        //中序
		for(int i =0;i<n;++i)
		{
			scanf("%d",&b[i]);
		}
		Tree = Creat(a,b,n);
		travel_post(Tree);
	}
	return 0;
}

中序+后序构造二叉树

中序+后序构造二叉树和先序+中序构造二叉树类似，关键之处在于，找到每个二叉结点的根，左孩子，右孩子的位置，然后递归就可以了。

#include<stdio.h>
#include<stdlib.h>
struct TNode
{
	int data;
	TNode *lchild,*rchild;
}*Tree;
int a[1000],b[1000];
int n;
//核心区
TNode * Creat(int *a,int *b,int n)
{
    TNode * T;
    T = (TNode *)malloc(sizeof(TNode));
    if(n<=0)
    	return NULL;
    else
    {
    	T->data = b[n-1];
    	int * p;
    	for(p = a;p<a+n;p++)
    	{
    		if(*p==b[n-1])
    			break;
		}
		int t = p-a;
		T->lchild = Creat(a,b,t);
		T->rchild = Creat(a+t+1,b+t,n-t-1);
		return T;
	}
}
//先序遍历
void travel_pre(TNode * R)
{
	if(R!=NULL)
	{
		if(R==Tree)
			printf("%d",R->data);
		else
			printf(" %d",R->data);
		travel_pre(R->lchild);
		travel_pre(R->rchild);
	}
}
int main()
{
	while(~scanf("%d",&n))
	{
		Tree =NULL;
		for(int i =0;i<n;++i)
		{
			scanf("%d",&a[i]);
		}
		for(int i =0;i<n;++i)
		{
			scanf("%d",&b[i]); 
		}
		Tree = Creat(a,b,n);
		travel_pre(Tree);    
		printf("\n"); 
	 } 
	 return 0;
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2019-10-18|，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树