本文共 2518 字，大约阅读时间需要 8 分钟。

一、前言

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

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

1.非递归二叉树创建：

2.二叉树的三种遍历方式：

重点部分

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

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

二、题目

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

 三、代码

#include
   
    #include
    
     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);}
    
   

四、实现效果