一、前言

上两篇周周练博客讲了二叉树的创建与遍历，创建时，通过创建栈来存放结点，方便二叉树的创建，这种创建二叉树的方式采用了非递归算法，本次内容采用递归的方式来创建二叉树，大家可以通过对比代码量，感受一下递归的魅力。同时遍历过程也是通过递归算法。

如果大家第一次看我的博客是这一篇，这里给大家链接，方便大家了解非递归二叉树遍历及三种遍历方式的理解方式。

1.非递归二叉树创建：【数据结构周周练】008 二叉树的链式创建及测试

2.二叉树的三种遍历方式：【数据结构周周练】009 二叉树的先序、中序、后序遍历（递归算法实现）

重点部分

递归二叉树创建过程，无需创立一个栈空间，同样也比较不容易一步获取双亲结点，栈空间直接从栈顶获取即可，那我们就要根据递归的原理，来创建一个结点保存双亲结点，具体我会在代码中体现。

这次代码无需用户输入，运行就能直接出结果。我将所有需要输入的地方全部转化为数组元素存到数组中，通过调用数组自动赋值。自动创建。

二、题目

将下图用二叉树存入，并通过三种遍历方式对该树进行遍历。其中圆角矩形内为结点数据，旁边数字为结点编号，编号为0的结点为根节点，箭头指向的结点为箭尾的孩子结点。要求遍历每个结点时能够查询当前结点的数据、编号、双亲结点以及孩子结点的编号，如果结点是根节点或者叶子结点，请说明。

 三、代码

#include<iostream>
#include<malloc.h>

using namespace std;

typedef struct BiTNode {
		int data;
		int number;
		int isAsk;
		struct BiTNode *parent,* lChild, * rChild;
	}BiTNode,*BiTree;

int number = 0;
int yon = 0;
int yesOrNo[] = { 1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,0 };
int numData[] = { 12,31,25,67,80,51,77,32 };
BiTree treeParent = NULL;

int OperationBiTree(BiTree &BT) {
	BT = (BiTree)malloc(sizeof(BiTNode));
	if (!BT)
	{
		cout << "空间分配失败" << endl;
		exit(OVERFLOW);
	}
	BT->number = number;
	number++;
	BT->data = numData[BT->number];
	BT->lChild = NULL;
	BT->rChild = NULL;
	BT->parent = treeParent;
	return 1;
}

void PreOrderCreatBiTree(BiTree &BT) {
	
	OperationBiTree(BT);
	treeParent = BT;
	if (yesOrNo[yon++])
		PreOrderCreatBiTree(BT->lChild);
	treeParent = BT;
	if (yesOrNo[yon++])
		PreOrderCreatBiTree(BT->rChild);

}

void VisitBiTree(BiTree BT) {
	cout << "当前结点的编号为：" << BT->number<<", ";
	cout << "数据为：" << BT->data << ",\n";
	if (BT->parent)
		cout << "    当前结点有双亲结点，结点编号为：" << BT->parent->number << ",\n";
	else
		cout << "    当前结点为根节点，无双亲结点\n";
	if (BT->lChild)
		cout << "    当前结点有左孩子结点，结点编号为：" << BT->lChild->number << ",\n";
	if (BT->rChild)
		cout << "    当前结点有右孩子结点，结点编号为：" << BT->rChild->number << ",\n";
	if (!BT->lChild && !BT->rChild)
		cout << "    当前结点为叶子结点\n";
	cout << endl;
	
}

void PreOrderBiTree(BiTree BT) {
	if (BT)
	{
		VisitBiTree(BT);
		PreOrderBiTree(BT->lChild);
		PreOrderBiTree(BT->rChild);
	}
}

void InOrderBiTree(BiTree BT) {
	if (BT)
	{
		InOrderBiTree(BT->lChild);
		VisitBiTree(BT);
		InOrderBiTree(BT->rChild);
	}
}

void PostOrderBiTree(BiTree BT) {
	if (BT)
	{
		PostOrderBiTree(BT->lChild);
		PostOrderBiTree(BT->rChild);
		VisitBiTree(BT);
	}
}

void main() {
	BiTree BT;
	PreOrderCreatBiTree(BT);
	cout << "\n**********************遍历二叉树开始**********************\n" ;
	cout << "\n**********************先序遍历二叉树**********************\n";
	PreOrderBiTree(BT);
	cout << "\n**********************中序遍历二叉树**********************\n";
	InOrderBiTree(BT);
	cout << "\n**********************后序遍历二叉树**********************\n";
	PostOrderBiTree(BT);

}

四、实现效果