【数据结构周周练】010 递归算法实现二叉树的创建与遍历

r囧r小猫 2021-09-16 16:26 378阅读 0赞

# 一、前言 #

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

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

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

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

**重点部分**

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

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

# 二、题目 #

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

![70][]

#  三、代码 #

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

# 四、实现效果 #

![70 1][]

![70 2][]

![70 3][]

[008 _]: https://blog.csdn.net/shuiyixin/article/details/83155167
[009 _]: https://blog.csdn.net/shuiyixin/article/details/83187900
[70]: /images/20210516/68160819b9f34f088529e9baaa09266f.png
[70 1]: /images/20210516/a65fdcb622f24682a30999f394c1b14f.png
[70 2]: /images/20210516/abb351d3fbeb42d1bb196cde9f20cbc0.png
[70 3]: /images/20210516/636d08396efa402ab810fab016d0b09b.png