【数据结构与算法基础】树与二叉树的互化_二叉树转化为树

前言

数据结构，一门数据处理的艺术，精巧的结构在一个又一个算法下发挥着他们无与伦比的高效和精密之美，在为信息技术打下坚实地基的同时，也令无数开发者和探索者为之着迷。

也因如此，它作为博主大二上学期最重要的必修课出现了。由于大家对于上学期C++系列博文的支持，我打算将这门课的笔记也写作系列博文，既用于整理、消化，也用于同各位交流、展示数据结构的美。

此系列文章，将会分成两条主线，一条“数据结构基础”，一条“数据结构拓展”。“数据结构基础”主要以记录课上内容为主，“拓展”则是以课上内容为基础的更加高深的数据结构或相关应用知识。

欢迎关注博主，一起交流、学习、进步，往期的文章将会放在文末。

---

在开始这篇文章的讨论之前，让我们先来看一篇短文

二叉树不是树是怎么回事呢？二叉树和树相信大家都很熟悉，但是二叉树和树二叉树不是树是怎么回事呢，下面就让小编带大家一起了解吧。
二叉树和树二叉树不是树，其实就是根据课本上的描述，二叉树不是树，大家可能会很惊讶二叉树和树那么像怎么会二叉树不是树呢？但事实就是这样，博主也感到非常惊讶。
这就是关于二叉树不是树的事情了，大家有什么想法呢，欢迎在评论区告诉博主一起讨论哦！

哦吼，先别急着退出，这是个正经账号。。。。。

这篇文章，我们主要想讨论的就是树和二叉树及其之间的相互转化。

尽管二叉树和树都带有“树”，尽管他们外形长得十分相似，仿佛给树增加若干限定条件就能在他的子集中定义出二叉树的概念。但实际上，我们还是习惯于将二叉树和树看作是两个不同的数据结构，他们相似，但没有包含关系。总之一句话就是树是树，二叉树是二叉树，二叉树不是树的特殊情况

当然，博主认为我们没有必要在定义处特别纠结于这个问题，先记住它，再在实践中尝试检验并接受它。

树和二叉树的区别

所以对这个问题的讨论还是应该结合定义之外更加广阔的场景来看。

在存储结构上

二叉树通常采用顺序存储结构或者链式存储结构。

顺序存储结构就是对完全二叉树的结点自上而下，从左向右的进行编号，将对应的结点值存在顺序表中的相应位置。

链式存储结构指的是二叉链表的存储格式，有时还会多引入一个父指针指向父节点，形成双向链表

树通常采用父指针链接结构或者儿子链表结构。二叉树中的二叉链表结构或者说确定个数分叉链接结构在树中显然不能正常表示父子关系，因为树的子节点个数并不存在具体上限。不仅如此，二叉树中的顺序存储结构更不能适配树的存储。

当然，二叉链表也可以用于树的存储，但是那是一种左儿子右兄弟的存法，和二叉树的存储含义大相径庭

在性质上

二者也有很大的不同

二叉树中结点的子树分成了左子树和右子树，即使某节点只有一棵子树，也要指明其是左子树还是右子树，这至少说明了二叉树是有序的

对比树的定义就会发现，树中结点的子树并没有明确的次序定义，树是无序的。

另外，二叉树中还有各种独特的定义，像“满二叉树”，“完全二叉树”等等，这些都与二叉树的有序性不无关系。而这类的定义无法给出一个树的版本。

另外，从面向对象的角度来说，树与二叉树也不能是继承的关系。

二者的实现方式存在明显的不同，在存储和行为上存在差异甚至是矛盾的地方，完全不适合继承的概念。

所以，我们最好还是将它们看作是两种不同的数据结构，在讨论时不要混为一谈。

树和二叉树的互化

树与二叉树不是同一种结构，但是他们可以互化。一般来说，我们基于二者间的一种自然对应方式可以完成互化的过程。

二叉树和树的自然对应

树和二叉树的自然对应关系在于：树中结点至多有一个大儿子和一个大兄弟，二叉树中结点至多有两个儿子。

基于这个关系，我们就可以将树中结点对应到二叉树中的结点，并将其大儿子结点作为左子节点，将其大兄弟结点作为右子节点。

完成对应的步骤可以总结如下：

1. 在所有兄弟结点之间加一条连线。
2. 对每个结点，除保留与其大儿子和其大兄弟结点的连线之外， 去掉该节点与其他儿子结点的连线
3. 调整部分连线方向、长短是指成为规范图形

这个过程看起来有些难理解，其实举个粟子就明白了：

先整一个一般的树：

兄弟结点之间连线：

除大兄弟和大儿子连线之外，删除其他儿子连线：

最后调整一下位置，这一步并没有改变树的结构：

ok，这样一棵树就转化成为二叉树啦~

那么将二叉树转化为树的过程其实是反过来的，再举个粟子：

我们来整一棵二叉树：

没错，就是刚刚那棵，稍微改动了一下。

改动一下位置，将右子结点放到同一水平线上，左子节点放在同一垂直线上：

不错，很有精神！

再将同一层兄弟结点间的连线去掉，与上一层父节点连线加上：

这样一棵二叉树就转化成为树啦~

下面就让我们编写代码来完成这个过程。

在转化之前，有必要先来定义一下两种树的结点：

结点结构体定义

先来普通结点定义，子节点采用链表的形式进行存储：

struct TreeNode;
struct NodeSon{
   //儿子链表结点
	Tree * son;//子节点
	NodeSon * next;	//链表中后继节点
};

struct TreeNode{
   //树中结点结构体定义
	int value;//结点值
	NodeSon * head;//子节点链表头结点
};
1
2
3
4
5
6
7
8
9
10
11
12

二叉树结点定义：

struct BiTreeNode{
   
	int value;
	BiTreeNode * left;
	BiTreeNode * right;
};
1
2
3
4
5
6

二叉树化树

给定需求如下：

给定一棵二叉树的前序遍历序列，空的子节点使用0来表示。将这棵二叉树转化成自然对应的树并输出每个结点及其子节点
输入格式：
输入为一样，包含二叉树的前序序列，空的子节点使用0来表示
样例输入：
8 5 1 0 6 0 2 0 0 3 4 0 0 7 0 0 0

样例输入的二叉树，是这个样子的：

化成树，是这个样子的：

要将二叉树转化成为树，要把握一个重点，就是将二叉树的左节点当做子节点，将二叉树的右节点当兄弟结点。

那么怎么表示子节点和兄弟结点呢？如果我们在构建过程中引入父节点这个参数，问题就会变得简单了。

每次我们根据二叉树当前结点值构建树的当前结点，并将它加入到父节点的子节点链表中。接着，遍历二叉树的左子节点，其父节点为当前结点。而后再遍历二叉树的右子节点，其父节点为当前结点的父节点。

首先，先写一个函数读取并生成这棵二叉树：

BiTreeNode * createBiTree(){
   
	int val;
	cin >> val;
	if(val == 0){
   
		return NULL;
	}
	BiTreeNode * node = new BiTreeNode();
	node->val = val;
	node->left = createBiTree();//创建左子树
	node->right = createBiTree();//创建右子树
	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

接着我们实现将二叉树转化成为树的函数：

TreeNode * biToTree(BiTreeNode * biNode,TreeNode * fa){
   //将二叉树转化为树，参数为二叉树结点和树节点的父节点
	if(biNode == NULL){
   
		return NULL;
	}
	TreeNode * node = new TreeNode();//创建树节点
	node->head = NULL<
1
2
3
4
5
6
7