[数据结构与算法]数据结构——二叉树创建与遍历（递归与非递归）

二叉树使用递归的方式创建：
首先输入数据，如果输入的数据是结束的数据就会返回上一层递归，进入到上一个节点并创建右孩子；如果输入数据符合创建数据的要求，就将改数据赋值给当前节点，并为当前节点的左孩子和右孩子开辟空间，创建左孩子节点；

int createTree(struct binaryTree *root)
{
	if(root == NULL){
		return 0;
	}
	int data;
	scanf("%d",&data);

	if(data == 0){
		return 0;
	}else{
		root->data = data;
	}

	root->left = (struct binaryTree *)malloc(sizeof(struct binaryTree));
	root->right = (struct binaryTree *)malloc(sizeof(struct binaryTree));

	printf("please input left data\n");
	if(createTree(root->left) == 0){
		free(root->left);
		root->left = NULL;
	}
	printf("please input right data\n");
	if(createTree(root->right) == 0){
		free(root->right);
		root->right = NULL;
	}

	return 1;
}

二叉树递归遍历
通过改变打印节点数据的位置来实现先序，中序，后序递归遍历

void headPrint(struct binaryTree *root)            //前序遍历
{
	if(root != NULL){
		printf("%d ",root->data);
		headPrint(root->left);
		headPrint(root->right);
	}
}

void middlePrint(struct binaryTree *root)          //中序遍历
{
	if(root != NULL){
		middlePrint(root->left);
		printf("%d ",root->data);
		middlePrint(root->right);
	}
}
void endPrint(struct binaryTree * root)            //后序遍历
{
	if(root != NULL){
		endPrint(root->left);
		endPrint(root->right);
		printf("%d ",root->data);
	}
}

二叉树非递归遍历：
为了实现非递归遍历，用到栈；

void forPrint(struct binaryTree *root)     
{
	struct binaryTree *p = root;      //创建一个用于遍历二叉树的临时节点；
	struct binaryTree *stack[10];     //创建用于存放节点数据的结构体指针数组
	int top = -1;                     //结构体指针数组的下标
	while(p != NULL || top != -1){    //当临时节点不为空（遍历到的二叉树节点有数据），或者下标不为0（用于存放节点数据的结构体指针数组中有数据）
		if(p != NULL){                //遍历到的当前节点不为空
			stack[++top] = p;         //存放入数组中
			printf("%d ",p->data);    //打印当前节点数据
			p = p->left;              //遍历到当前节点的左孩子
		}else{
			p = stack[top--];         //如果当前节点为空节点，主要返回到当前节点的父亲
			p = p->right;             //从父亲遍历到右孩子；
		}
	}
}

void miPrint(struct binaryTree *root)    //中序遍历原理同先序遍历
{
        struct binaryTree *p = root;
        struct binaryTree *stack[10];
        int top = -1;
        while(p != NULL || top != -1){
                if(p != NULL){
                        stack[++top] = p;
                        p = p->left;
                }else{
                        p = stack[top--];
			printf("%d ",p->data);
			p = p->right;
                        
                }
        }
}

层序遍历
使用数组的方式来存放节点，使用两个下标来进行遍历；

void cengPrint(struct binaryTree *root)
{
	int index1 = 0;                     //首先定义两个下标用于遍历二叉树，index2用来不断遍历打印二叉树节点，index1用来动态添加index2的左右孩子到数组中；
	int index2 = 0;

	struct binaryTree *arr[10];        //创建结构体指针数组，用于存放节点数据

	arr[index1++] = root;              //首先利用第一个index设置数组第一个元素是传入的根节点

	while(index1>index2){                     //由于index2是用来遍历打印节点数据的，而index2是用来添加index2的左右孩子，所以比index1小
		if(arr[index2] != NULL){              //index2表示当前遍历到的二叉树的节点
			printf("%d ",arr[index2]->data);  //打印当前遍历的节点数据
			arr[index1++] = arr[index2]->left;       //将当前遍历的左孩子利用index1加入到数组中
			arr[index1++] = arr[index2]->right;      //将当前遍历的右孩子利用index1加入到数组中
		}
		index2++;                                    //遍历下一个节点
	}
}

整体代码

#include <stdio.h>
#include <stdlib.h>

struct binaryTree{
	int data;
	struct binaryTree *left;
	struct binaryTree *right;
};

int createTree(struct binaryTree *root)
{
	if(root == NULL){
		return 0;
	}
	int data;
	scanf("%d",&data);

	if(data == 0){
		return 0;
	}else{
		root->data = data;
	}

	root->left = (struct binaryTree *)malloc(sizeof(struct binaryTree));
	root->right = (struct binaryTree *)malloc(sizeof(struct binaryTree));

	printf("please input left data\n");
	if(createTree(root->left) == 0){
		free(root->left);
		root->left = NULL;
	}
	printf("please input right data\n");
	if(createTree(root->right) == 0){
		free(root->right);
		root->right = NULL;
	}

	return 1;
}

void headPrint(struct binaryTree *root)
{
	if(root != NULL){
		printf("%d ",root->data);
		headPrint(root->left);
		headPrint(root->right);
	}
}

void middlePrint(struct binaryTree *root)
{
	if(root != NULL){
		middlePrint(root->left);
		printf("%d ",root->data);
		middlePrint(root->right);
	}
}
void endPrint(struct binaryTree * root)
{
	if(root != NULL){
		endPrint(root->left);
		endPrint(root->right);
		printf("%d ",root->data);
	}
}

void forPrint(struct binaryTree *root)
{
	struct binaryTree *p = root;
	struct binaryTree *stack[10];
	int top = -1;
	while(p != NULL || top != -1){
		if(p != NULL){
			stack[++top] = p;
			printf("%d ",p->data);
			p = p->left;
		}else{
			p = stack[top--];
			p = p->right;
		}
	}
}

void miPrint(struct binaryTree *root)
{
        struct binaryTree *p = root;
        struct binaryTree *stack[10];
        int top = -1;
        while(p != NULL || top != -1){
                if(p != NULL){
                        stack[++top] = p;
                        p = p->left;
                }else{
                        p = stack[top--];
			printf("%d ",p->data);
			p = p->right;
                        
                }
        }
}


void cengPrint(struct binaryTree *root)
{
	int index1 = 0;
	int index2 = 0;

	struct binaryTree *arr[10];

	arr[index1++] = root;

	while(index1>index2){
		if(arr[index2] != NULL){
			printf("%d ",arr[index2]->data);
			arr[index1++] = arr[index2]->left;
			arr[index1++] = arr[index2]->right;
		}
		index2++;
	}
}
int main()
{
	struct binaryTree *root = (struct binaryTree *)malloc(sizeof(struct binaryTree));
	printf("plesae input root data\n");
	createTree(root);

	printf("head Print:\n");
	headPrint(root);
	printf("\n");


	printf("forPrint\n");
	forPrint(root);
	printf("\n");

	printf("middle Print:\n");
        middlePrint(root);
        printf("\n");

	printf("mmiprint\n");
	miPrint(root);
	printf("\n");

	printf("end Print:\n");
        endPrint(root);
        printf("\n");

	printf("cengPrint\n");
	cengPrint(root);
	printf("\n");

	return 0;
}