基于C语言二叉树的建立,先序,中序,后序遍历(包含完整代码)_编写二叉树的创建、二叉树的先序、中序和后序遍历算法的程序实现。

首先加入两个头文件:#include <stdio.h>    

                                 #include <stdlib.h>

1.定义树中每个节点的结构体

 typedef struct Tree
{
    int data;//数据域 
    struct Tree *lchild;//左子树 
    struct Tree *rchild;//右子树 
}Tree;

2.新建节点(初始化一个节点)

Tree *initTree(int data)
{
	Tree *t = (Tree *)malloc(sizeof(Tree));//申请内存空间 
	t->data = data;//写入元素 
	t->lchild = NULL;//左右子树都为空 
	t->rchild = NULL;
	return t;
}

 3.查找

int search(Tree *t,int data) 
{
	if(t==NULL)//判断是否为空,如果为空直接结束并返回-1 
		return -1;
	else
	{
		if(t->data==data)
		{
			printf("查找成功!\n");
			return t->data;			
		}
		search(t->lchild,data);//递归,向左子树查找 
		search(t->rchild,data);//递归,向右子树查找 
	}
}

4.插入节点

void insert(Tree **t,int data)//因为要修改节点中的值,这里使用双重解引用 
{/*双重解引用:通过两次解引用,找到指针指向的内存和内存中的数据*/
	if(*t==NULL)//如果传入的节点为空,直接新建一个节点,并把元素写入 
	{
		*t = initTree(data);
		return;		
	}
	if((*t)->data>data)//如果该节点内的元素大于data,向左子树找(小于向右子树找) 
		insert(&(*t)->lchild,data);//传入解引用t的地址,才能修改值 
	else
		insert(&(*t)->rchild,data); 
	
}

5.创建一个树

Tree *create(int *data,int n)
{
	int i;
	Tree *root = NULL;//定义根 
	for(i=0;i<n;i++)//挨个插入元素到树中 
		insert(&root,data[i]);
	return root;
}

6.先序遍历(根左右)

void preTree(Tree *root)
{
	if(root==NULL)
		return ;
	printf("%d ",root->data);//输出根元素 
	preTree(root->lchild);//递归,找左子树(进栈和出栈) 
	preTree(root->rchild);//递归,找右子树(进栈和出栈) 
}

7.中序遍历(左根右)

void inTree(Tree *root)
{
	if(root==NULL)
		return;
	inTree(root->lchild);//不断递归,压栈,找最下层第一个左子树,然后回溯出栈 
	printf("%d ",root->data);//按照左根右的顺序不断输出(出栈) 
	inTree(root->rchild);//不断递归,压栈,出栈,找右子树输出 
}

8.后序遍历(左右根)

void enTree(Tree *root)
{
	if(root==NULL)
		return;
	enTree(root->lchild);//递归,左子树 
	enTree(root->rchild);//递归,右子树 
	printf("%d ",root->data);//边出栈,边输出 
}

9.主函数验证

int main()
{
	int num[10] = {5,3,8,2,4,1,6,7,9,0};
	Tree *root = create(num,10);//建立一颗树并把根赋值给root 
	preTree(root);//验证先序遍历 
	printf("\n");
	inTree(root);//验证中序遍历 
	printf("\n");
	enTree(root);//验证后续遍历 
 
	return 0; 
} 

完整代码如下:

/*排序二叉树,左小右大*/
#include <stdio.h>
#include <stdlib.h>
/*定义树的结构体*/
typedef struct Tree
{
	int data;//数据域 
	struct Tree *lchild;//左子树 
	struct Tree *rchild;//右子树 
}Tree;
 
/*新建节点(初始化一个节点)*/
Tree *initTree(int data)
{
	Tree *t = (Tree *)malloc(sizeof(Tree));//申请内存空间 
	t->data = data;//写入元素 
	t->lchild = NULL;//左右子树都为空 
	t->rchild = NULL;
	return t;
}
/*查找*/
int search(Tree *t,int data) 
{
	if(t==NULL)//判断是否为空,如果为空直接结束并返回-1 
		return -1;
	else
	{
		if(t->data==data)
		{
			printf("查找成功!\n");
			return t->data;			
		}
		search(t->lchild,data);//递归,向左子树查找 
		search(t->rchild,data);//递归,向右子树查找 
	}
}
/*插入节点*/
void insert(Tree **t,int data)//因为要修改节点中的值,这里使用双重解引用 
{/*双重解引用:通过两次解引用,找到指针指向的内存和内存中的数据*/
	if(*t==NULL)//如果传入的节点为空,直接新建一个节点,并把元素写入 
	{
		*t = initTree(data);
		return;		
	}
	if((*t)->data>data)//如果该节点内的元素大于data,向左子树找(小于向右子树找) 
		insert(&(*t)->lchild,data);//传入解引用t的地址,才能修改值 
	else
		insert(&(*t)->rchild,data); 
	
}
/*创建一个树*/
Tree *create(int *data,int n)
{
	int i;
	Tree *root = NULL;//定义根 
	for(i=0;i<n;i++)//挨个插入元素到树中 
		insert(&root,data[i]);
	return root;
}
/*先序遍历(根左右)*/
void preTree(Tree *root)
{
	if(root==NULL)
		return ;
	printf("%d ",root->data);//输出根元素 
	preTree(root->lchild);//递归,找左子树(进栈和出栈) 
	preTree(root->rchild);//递归,找右子树(进栈和出栈) 
}
/*中序遍历(左根右)*/
void inTree(Tree *root)
{
	if(root==NULL)
		return;
	inTree(root->lchild);//不断递归,压栈,找最下层第一个左子树,然后回溯出栈 
	printf("%d ",root->data);//按照左根右的顺序不断输出(出栈) 
	inTree(root->rchild);//不断递归,压栈,出栈,找右子树输出 
} 
/*后序遍历(左右根)*/
void enTree(Tree *root)
{
	if(root==NULL)
		return;
	enTree(root->lchild);//递归,左子树 
	enTree(root->rchild);//递归,右子树 
	printf("%d ",root->data);//边出栈,边输出 
}
int main()
{
	int num[10] = {5,3,8,2,4,1,6,7,9,0};
	Tree *root = create(num,10);//建立一颗树并把根赋值给root 
	preTree(root);//验证先序遍历 
	printf("\n");
	inTree(root);//验证中序遍历 
	printf("\n");
	enTree(root);//验证后续遍历 
 
	return 0; 
}