二叉树的创建和遍历

目录

一.二叉树的创建

1.顺序存储二叉树的创建

2.链式存储二叉树的创建

2.1先序和中序创建二叉树

2.2中序和后序创建二叉树

二.二叉树的递归遍历

1.二叉树的遍历原理

2.中序遍历

3.先序遍历

4.后序遍历

三.二叉树的非递归遍历

1.中序遍历

2.先序遍历

3.后序遍历

方法2：用出栈的次数进行判断

四.层次遍历二叉树

一.二叉树的创建

二叉树的创建可以选择顺序存储方式创建二叉树和链式存储方式创建二叉树。

我们为了创建一棵完整的二叉树，需要对普通的二叉树进行拓展，如图所示：

 其实建立二叉树也是利用了递归的原理。只不过在原来应该是打印结点的地方，改成了生成结点，给结点赋值的操作而已。大家可以先看后面的二叉树的遍历，再来看二叉树的创建。

1.顺序存储二叉树的创建

顺序存储一般使用的是一维数组存储二叉树的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右兄弟的关系等。

现在实现顺序存储二叉树的创建：

分析：创建二叉树的过程利用递归算法。如果该节点存在则对该节点创建一个新的二叉树。将一个大的二叉树分解成小的二叉树，在进行回退。

 根据箭头所指方向即可以理解递归算法创建二叉树的过程。代码如下所示：

//创建二叉树
BtNode* CreateBtStr(const char* &str)
{
	BtNode* s = nullptr;
	if (*str != '#')
	{
		s = Buynode();
		s->data = *str;
		s->leftchild = CreateBtStr(++str);
		s->rigthchild = CreateBtStr(++str);
	}
	return s;
}
BtNode* CreateTreeStr(const char* str)
{
	if (nullptr == str || strlen(str) <= 0) return nullptr;
	else return CreateBtStr(str);
}

顺序二叉树由于物理空间连续，如果为满二叉树或者完全二叉树，则不会造成空间的浪费；如果二叉树为一棵斜树，则会造成空间的浪费。如图分析：

如图所示：有大量空间被浪费。所以顺序存储二叉树一般情况选择的是满二叉树或者完全二叉树。因此我们也要用链式存储实现二叉树的创建。 

一棵深度为K的右斜树，它只有K个结点，却需要分配2^K-1个存储单元空间。这显然是对存储空间的浪费。所以顺序存储结构一般只用于完全二叉树。 

2.链式存储二叉树的创建

既然顺序存储适用性不强，我们就考虑链式存储结构。二叉树每个结点最多哟两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫作二叉链表。

 先对二叉树结点进行结构体定义，结点包括两个指针域（指向左右孩子的指针域）和一个数据域（结点本身）

再设计一个购买新结点的函数，每构建一个结点都需要购买一个结点。这种方式比顺序存储更节省空间。

typedef struct BtNode {
	struct BtNode* leftchild;
	struct BtNode* rigthchild;
	ElemType data;
}BtNode,*BinaryTree;
 
BtNode* Buynode() {
	BtNode* s = (BtNode*)malloc(sizeof(BtNode));
	if (nullptr == s)exit(1);
	memset(s, 0, sizeof(BtNode));
	return s;
}

设计一个找到根节点位置的函数 ，后序创建二叉树会用到。也可以等到设计二叉树过程中发现需要用到在去设计。

//找到根节点的位置
int FindPos(const char* istr, int n, char ch)
{
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (istr[i] == ch)
		{
			pos = i;
			break;
		}
	}
	return pos;
}

2.1先序和中序创建二叉树

可以根据先序和中序遍历二叉树的结果推出这棵二叉树的样子。我们对此进行一个分析：

例如：

先序遍历结果：ABCDEFGH  中序遍历结果：CBEDFAGH

1.先序遍历结果首元素为二叉树的根节点，即此二叉树的跟结点为A；

2.在中序遍历中也找到根节点A，找到根节点A之后，我们可以得知根节点A的左边为它的左子树，右边为它的右子树；

3.现在根据根据中序遍历结果找到A的左右子树之后，计算左右子树元素个数分别为多少，将先序遍历也根据从左至右按左右子树个数分开为左右子树；

4.将新分好的左右子树分别重新进行上述操作；

5.利用递归算法，完成二叉树的创建。

代码如下：

//先序和中序创建二叉树
BtNode* CreateBTreePI(const char* pstr, const char* istr, int n)
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = Buynode();
		s->data = pstr[0];
		int pos = FindPos(istr, n, pstr[0]);
		if (-1 == pos) exit(1);
		s->leftchild = CreateBTreePI(pstr + 1, istr, pos);
		s->rigthchild = CreateBTreePI(pstr + pos + 1, istr + pos + 1, n - pos - 1);
	}
	return s;
}
BtNode* CreateBinaryTreePI(const char* pstr, const char* istr)
{
	int n = strlen(pstr);
	int m = strlen(istr);
	if (nullptr == pstr || nullptr == istr || n < 1 || m < 1 || n != m) return nullptr;
	else return CreateBTreePI(pstr, istr, n);
 
}

2.2中序和后序创建二叉树

也可以根据中序和后序遍历二叉树的结果推出这棵二叉树的样子。我们对此进行一个分析：

例如：

中序遍历结果：CBEDFAGH  后序遍历结果：CEFDBHGA

1.后序遍历结果最后一个元素为二叉树的根节点，即此二叉树的跟结点为A；

2.在中序遍历中也找到根节点A，找到根节点A之后，我们可以得知根节点A的左边为它的左子树，右边为它的右子树；

3.现在根据根据种序遍历结果找到A的左右子树之后，计算左右子树元素个数分别为多少，将后序遍历也根据从右至左按左右子树个数分开为左右子树；

4.将新分好的左右子树分别重新进行上述操作；

5.利用递归算法，完成二叉树的创建。

代码如下：

//中序和后序建立二叉树
BtNode* CreateBTreeIL(const char* istr, const char* lstr, int n)
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = Buynode();
		s->data = lstr[n - 1];
		int pos = FindPos(istr, n, lstr[n - 1]);
		s->leftchild = CreateBTreeIL(istr, lstr, pos);
		s->rigthchild = CreateBTreeIL(istr + pos + 1, lstr + pos, n - pos - 1);
	}
	return s;
}
BtNode* CreateBinaryTreeIL(const char* istr, const char* lstr)
{
	int n = strlen(istr);
	int m = strlen(lstr);
	if (nullptr == istr || nullptr == lstr || n < 1 || m < 1 || n != m) return nullptr;
	else return CreateBTreeIL(istr, lstr, n);
 
}

二.二叉树的递归遍历

1.二叉树的遍历原理

在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树总全部结点逐一进行某种处理。这就提出了一个遍历二叉树的问题，即如何按某条搜索路劲巡防树中的每个结点，使得每个结点均被访问依次。“访问”的含义很广，可以是对结点做各种处理，如输出结点的信息等。遍历对线性结构来说，是一个容易解决的问题，而对二叉树则不然，由于二叉树是一种非线性结构，每个结点都有可能有两颗子树，因而需要寻找一种规律，以便使二叉树上的节点能排列在一个线性队列上，从而便于遍历。

二叉树的遍历（traversing binary tree）是指从根节点出发，按照某种次序依次访问二叉树中的所有节点，使得每个结点被访问依次且仅被访问一次。

关键词：访问和次序 

2.中序遍历

中序遍历二叉树：1.访问左孩子2.打印根节点3.访问右孩子（用递归算法实现）

 
//二叉树的顺序存储结构
//中序遍历
void InOrder(BtNode* ptr) {
	if (ptr != nullptr) {
		InOrder(ptr->leftchild);
		printf("%c", ptr->data);
		InOrder(ptr->rigthchild);
	}
}
 
//二叉树的链式存储结构
//中序遍历二叉树
void InOrder_Ar(const int* nums, int i, int n)
{
	if (i < n && nums[i] != -1)
	{
		InOrder_Ar(nums, i * 2 + 1, n); // leftchild;
		printf("%5d", nums[i]);
		InOrder_Ar(nums, i * 2 + 2, n); // rightchild;
	}

3.先序遍历

先序遍历二叉树：1..打印根节点2.访问左孩子3.访问右孩子（用递归算法实现）

//二叉树的顺序存储结构
//先序遍历
void PreOrder(BtNode* ptr) {
	if (ptr != nullptr) {
		printf("%c", ptr->data);
		PreOrder(ptr->leftchild);
		PreOrder(ptr->rigthchild);
	}
}
//二叉树的链式存储结构
//先序遍历二叉树
void PreOrder_Ar(const int* nums, int i, int n)
{
	if (i < n && nums[i] != -1)
	{
		printf("%5d", nums[i]);
		PreOrder_Ar(nums, i * 2 + 1, n); // leftchild;
		PreOrder_Ar(nums, i * 2 + 2, n); // rightchild;
	}

4.后序遍历

后序遍历二叉树：1.访问左孩子2.访问右孩子3.打印根节点（用递归算法实现）

//二叉树的顺序存储结构
//后序遍历
void PastOrder(BtNode* ptr) {
	if (ptr != nullptr) {
		PastOrder(ptr->leftchild);
		PastOrder(ptr->rigthchild);
		printf("%c", ptr->data);
	}
}
//二叉树的链式存储结构
//后序遍历二叉树
void PastOrder_Ar(const int* nums, int i, int n)
{
	if (i < n && nums[i] != -1)
	{
		PastOrder_Ar(nums, i * 2 + 1, n); // leftchild;
		PastOrder_Ar(nums, i * 2 + 2, n); // rightchild;
		printf("%5d", nums[i]);
	}
}

三.二叉树的非递归遍历

我们知道递归遍历过程中算法效率不高，空间复杂度过高，所有先对此进行优化，完成非递归遍历的设计。非递归遍历中，我们需要用到栈，来对二叉树中的结点进行存放。

1.中序遍历

先申请一个栈空间，用指针ptr指向根节点；

1）当指针不指向空时，将指针ptr入栈，然后指针ptr指向根节点的左孩子，直到指针ptr指向空退出循环；

2）然后取栈顶元素，出栈；

3）将该数据打印出来，再讲指针ptr指向该节点的右孩子；

4）在指针ptr不指向空或者栈内不为空时，一直进行大循环；

 

//中序非递归遍历
void NiceInOrder(BtNode* ptr)
{
	if (nullptr == ptr) return;
	std::stack<BtNode*> st;
 
	while (ptr != nullptr || !st.empty()) 
	{
		while (ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top(); st.pop();
		printf("%3c", ptr->data);
		ptr = ptr->rigthchild;
	}
	printf("\n");
}

2.先序遍历

现申请一个栈空间，将指针ptr指向根节点入栈；

1）栈不空的情况下去栈顶元素值，出栈，打印根节点数据；

2）如果右孩子不为空，将右孩子入栈，如果左孩子不空将左孩子入栈；

3）栈不空的情况下，取栈顶元素值，出栈，打印；

4）循环上述操作。

注意：先入右孩子   

原因：栈存取方式为先进后出，而遍历二叉树时要先打印左孩子再打印右孩子。

//先序非递归遍历
void NicePerOrder(BtNode* ptr)
{
	if (nullptr == ptr) return;
	stack<BtNode*> st;
	st.push(ptr);
	while (!st.empty())
	{
		ptr = st.top(); st.pop();
		printf("%3c", ptr->data);
		// 0 // error -1  // leaf //
		if (ptr->rigthchild != nullptr)
		{
			st.push(ptr->rigthchild);
		}
		if (ptr->leftchild != nullptr)
		{
			st.push(ptr->leftchild);
		}
	}
	printf("\n");
}

3.后序遍历

根据先序和中序非递归遍历二叉树，我们可以写出后序非递归遍历；后序非递归遍历中我们需要一个“跟屁虫标记（tag）”来确保一个结点没有被访问两次。其余过程和先序遍历相似。

//后序非递归遍历
void NicePastOrder(BtNode* ptr)
{
	if (nullptr == ptr) return;
	std::stack<BtNode*> st;
	BtNode* tag = nullptr;
 
	while (ptr != nullptr || !st.empty()) 
	{
		while (ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top(); st.pop();
		if (ptr->rigthchild == nullptr || ptr->rigthchild == tag)
		{
			printf("%3c", ptr->data);
			tag = ptr;
			ptr = nullptr;
		}
		else
		{
			st.push(ptr);
			ptr = ptr->rigthchild;
		}
	}
	printf("\n");
}

方法2：用出栈的次数进行判断

由于递归算法的算法效率不高，我们对此进行优化，在了解遍历规则的情况之后，我们进行非递归的遍历算法。

非递归的后序遍历  第二种方法
用一个元素出栈的次数来判断   需要用栈来实现
元素作为根节点入栈一次，打印该元素出栈一次，访问该元素的左右孩子各出栈两次
出栈次数到达3次，即该节点本身以及该节点的左右孩子均已访问完成

1）对结构体进行初始化，可以直接用花括号来写

在栈不空的情况下：

2）取栈顶元素值，出栈

3）如果该节点出栈次数+1到达三次（即该节点以及左右孩子均已访问完成），打印栈顶元素值；

4）如果没有到达三次，将刚刚取的栈顶元素值重新入栈；

5）在入栈之后如果出栈次数为1并且左孩子不为空，将左孩子入栈；

6）如果出栈次数为2并且右孩子不为空，将右孩子入栈；

void NicePastOrder_2(BtNode* ptr)
{
	if (nullptr == ptr) return;
	stack<StkNode> st;//栈所放内容
	st.push(StkNode{ ptr,0 });//对结构体进行初始化，可以直接用花括号来写
	while (!st.empty())
	{
		StkNode node = st.top(); st.pop();
		if (++node.popnum == 3) {
			printf("%3c", ptr->data);
		}
		else {
			st.push(node);
			if (node.popnum == 1 && node.pnode ->leftchild != nullptr) {
				st.push(StkNode{node.pnode ->leftchild ,0});
			}
			else if (node.popnum == 2 && node.pnode->rigthchild != nullptr) {
				st.push(StkNode{ node.pnode->rigthchild ,0 });
			}
		}
		
	}
	printf("\n");
}

 根据非递归的后序遍历，我们也可以写出非递归的中序遍历

中序非递归遍历方法和后序非递归方法相似，需要注意的是：中序递归出栈次数到达两次所有元素就会全部访问完成。

//非递归的中序遍历  第二种方法
void NiceInOrder_2(BtNode* ptr)
{
	if (nullptr == ptr) return;
	stack<StkNode> st;
	st.push(StkNode{ ptr,0 });
	while (!st.empty())
	{
		StkNode node = st.top(); st.pop();
		if (++node.popnum == 2)
		{
			printf("%3c", node.pnode->data);
			if (node.pnode->rigthchild != nullptr)
			{
				st.push(StkNode{ node.pnode->rigthchild,0 });
			}
		}
		else
		{
			st.push(node);
			if (node.popnum == 1 && node.pnode->leftchild != nullptr)
			{
				st.push(StkNode{ node.pnode->leftchild,0 });
			}
		}
	}
	printf("\n");
}

四.层次遍历二叉树

前中后遍历二叉树了解之后，我们可以来学习一下层次遍历二叉树。层次遍历二叉树，就是依次打印同一高度的结点。此过程中，我们需要用到队列。

队列的存取方式：先进先出；

 

void LevelOrder(BtNode* ptr)
{
	if (nullptr == ptr) return;
	queue<BtNode*> qu;
	qu.push(ptr); // 入队
	while (!qu.empty())
	{
		ptr = qu.front(); qu.pop();
		printf("%3c", ptr->data);
		if (ptr->leftchild != nullptr)
		{
			qu.push(ptr->leftchild);
		}
		if (ptr->rigthchild != nullptr)
		{
			qu.push(ptr->rigthchild);
		}
	}
	printf("\n");
 
}

参考资料：《大话数据结构——程杰》和《数据结构——严蔚敏》