C++算法和数据结构之《二叉树》_c++数据结构二叉树算法

一：树的定义

树是由 n (n>= 0)个结点组成的有限集合。 如果 n = 0，称为空树；如果 n > 0，则
① 有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；
②除根以外的其它结点划分为 m (m >= 0)个互不相交的有限集合 T0, T1, …, Tm-1，每个集合又是一棵树，并且称
之为根的子树(subTree)。每棵子树的根结点有且仅有一个直接前驱，但可以有 0 个或多个直接后继。

1. 节点的度：一个节点含有的子树的个数称为该节点的度；
2. 树的度：一棵树中，最大的节点的度称为树的度；
3. 叶节点或终端节点：度为零的节点；
4. 非终端节点或分支节点：度不为零的节点；
5. 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
6. 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
7. 兄弟节点：具有相同父节点的节点互称为兄弟节点；
8. 节点的层次：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推；
9. 深度：对于任意节点 n,n 的深度为从根到 n 的唯一路径长，根的深度为 0；
10. 高度：对于任意节点 n,n 的高度为从 n 到一片树叶的最长路径长，所有树叶的高度为 0；
11. 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
12. 节点的祖先：从根到该节点所经分支上的所有节点；
13. 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
14. 森林：由 m（m>=0）棵互不相交的树的集合称为森林；
15. 树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树。反之是有序树。

二：二叉树的设计：

一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。

1、二叉树的结构设计

#include<iostream>
#include<queue>
#include<stack>
using namespace std;

typedef char ElemType;
typedef struct BtNode  //Binary Tree
{
	BtNode* leftchild;
	BtNode* rightchild;
	ElemType data;
}BtNode , *BinaryTree;
1
2
3
4
5
6
7
8
9
10
11
12

2、创建一个节点

BtNode* BuyNode()
{
	BtNode* s = (BtNode*)malloc(sizeof(BtNode));//
	if (s == nullptr)
		exit(1);
	memset(s, 0, sizeof(BtNode));
	return s;
}
1
2
3
4
5
6
7
8

3、返回所找值的下标

int FindIs(const char* is, int n, ElemType val)
{
	int pos = -1;
	for (int i = 0; i < n; ++i)
	{
		if (is[i] == val)
		{
			pos = i;
			break;
		}
	}
	return pos;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

4、前序遍历二叉树

首先遍历根节点，再遍历左子树（遍历左子树的时候仍然先遍历根节点，再遍历左子树，最后遍历右子树），最后遍历右子树（遍历右子树的时候仍然先遍历根节点，再遍历左子树，最后遍历右子树）

递归实现前序遍历：

void Recursive_PreOrder(BtNode* ptr)
{
	if (ptr != nullptr)
	{
		cout << ptr->data << " ";
		Recursive_PreOrder(ptr->leftchild);
		Recursive_PreOrder(ptr->rightchild);
	}
}
1
2
3
4
5
6
7
8
9

非递归实现前序遍历：
首先创建一个栈，将根节点入栈，然后判断右左孩子是否为空，右边孩子先入栈，再左孩子入栈（注意栈是先进后出）,然后按照这个步骤依次入栈出栈。

void PreOrder(BtNode* ptr)
{
	if (ptr == nullptr)return;
	std::stack<BtNode*>st;
	st.push(ptr);
	while (!st.empty())
	{
		ptr = st.top();
		st.pop();
		cout << ptr->data << " ";
		if (ptr->rightchild != nullptr)
		{
			st.push(ptr->rightchild);
		}
		if (ptr->leftchild != nullptr)
		{
			st.push(ptr->leftchild);
		}
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

5、中序遍历二叉树

首先遍历左子树（遍历左子树的时候也先遍历左子树，然后遍历根节点，再遍历右子树），然后遍历根节点，最后遍历右子树（遍历右子树的时候仍然先遍历左子树，然后遍历根节点，最后再遍历右子树）

递归实现中序遍历：

void Recursive_InOrder(BtNode* ptr)
{
	if (ptr != nullptr)
	{
		Recursive_InOrder(ptr->leftchild);
		cout << ptr->data << " ";
		Recursive_InOrder(ptr->rightchild);
	}
}
1
2
3
4
5
6
7
8
9

非递归实现中序遍历：
首先根节点和根节点的左孩子依次入栈，直到左孩子为空停止，然后出栈，再把指针指向该节点的右孩子，以此类推

void InOrder(BtNode* ptr)
{
	if (ptr == nullptr) return;
	std::stack<BtNode*>st;
	while (ptr != nullptr || !st.empty())
	{
		while(ptr != nullptr)
		{
			st.push(ptr);
			ptr = ptr->leftchild;
		}
		ptr = st.top();
		st.pop();
		cout << ptr->data << " ";
		ptr = ptr->rightchild;
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

6、后序遍历二叉树

首先遍历左子树（遍历左子树的时候也先遍历左子树，然后遍历右子树，最后遍历根节点），然后遍历右子树（遍历右子树的时候仍然先遍历左子树，然后遍历右子树，最后再遍历根节点），最后遍历根节点

递归实现后序遍历：

void Recursive_PastOrder(BtNode* ptr)
{
	if (ptr != nullptr)
	{
		Recursive_PastOrder(ptr->leftchild);
		Recursive_PastOrder(ptr->rightchild);
		cout << ptr->data << " ";
	}
}
1
2
3
4
5
6
7
8
9

非递归实现后序遍历：

首先根节点和根节点的左孩子依次入栈，直到左孩子为空停止，然后出栈，再定义一个标志指针tag（该标志是当一个节点的左右孩子都为空时，把该节点出栈，将该节点赋给该标志）以此类推。

void PastOrder(BtNode* ptr)
{
	if (ptr == nullptr)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->rightchild == nullptr || ptr->rightchild == tag)
		{
			cout << ptr->data << " ";
			tag = ptr;
			ptr = nullptr;
		}
		else
		{
			st.push(ptr);
			ptr = ptr->rightchild;
		}
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

7、前序和中序创建二叉树

首先知道前序遍历中第一个节点为根节点，然后通过FindIs()函数找到中序遍历中与此节点值相同的节点，并以此节点左右分为左子树和右子树，然后左子树和右子树又看成是一颗树，以上述规律进行下去。

BtNode* CreatePRI(const char* pr, const char* is, int n)
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = BuyNode();
		s->data = pr[0];
		int pos = FindIs(is, n, pr[0]);
		if (pos == -1) exit(1);
		s->leftchild = CreatePRI(pr + 1, is, pos);
		s->rightchild = CreatePRI(pr + pos + 1, is + pos + 1, n - pos - 1);
	}
	return s;
}

BtNode* CreateTreePRI(const char* pr, const char* is)
{
	if (pr == nullptr || is == nullptr)
	{
		return nullptr;
	}
	int pn = strlen(pr);
	int in = strlen(is);
	if (pn != in)
	{
		return nullptr;
	}
	return CreatePRI(pr, is, pn);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

8、后序和中序创建二叉树

首先知道后序遍历中最后一个节点为根节点，然后通过FindIs()函数找到中序遍历中与此节点值相同的节点，并以此节点左右分为左子树和右子树，然后左子树和右子树又看成是一颗树，以上述规律进行下去。

BtNode* CreateIPA(const char* is, const char* ps,int n)
{
	BtNode* s = nullptr;
	if (n > 0)
	{
		s = BuyNode();
		s->data = ps[n - 1];
		int pos = FindIs(is, n, ps[n - 1]);
		if (pos == -1)exit(1);
		s->leftchild = CreateIPA(is, ps, pos);
		s->rightchild = CreateIPA(is + pos + 1, ps + pos, n - pos - 1);
	}
	return s;
}
BtNode* CreateTreeIPA(const char* is, const char* ps)
{
	if (is == nullptr || ps == nullptr)
	{
		return nullptr;
	}
	int ilen = strlen(is);
	int plen = strlen(ps);
	if (ilen != plen)return nullptr;
	return CreateIPA(is, ps, ilen);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

9、层次遍历

所谓层次遍历就是依次遍历二叉树的第一层、第二层、第三层…
我们这里用一个队列：

void LevelOrder(BtNode* ptr)
{
	if (ptr == nullptr)
	{
		return;
	}
	std::queue<BtNode*>qu;
	qu.push(ptr);
	while (!qu.empty())
	{
		ptr = qu.front();
		qu.pop();
		cout << ptr->data << " ";
		if (ptr->leftchild != nullptr)
		{
			qu.push(ptr->leftchild);
		}
		if (ptr->rightchild != nullptr)
		{
			qu.push(ptr->rightchild);
		}
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

10、Z字形层次打印二叉树

我们这里用了两个栈，两个栈来回颠倒，依次打印每一层，首先第一个栈左孩子先进，右孩子后进，第二个站右孩子先进，左孩子后进。

void ZLevelOrder(BtNode* ptr)
{
	if (ptr == nullptr)return ;
	std::stack<BtNode*>qua, qub;
	qua.push(ptr);
	while (!qua.empty() || !qub.empty())
	{
		while (!qua.empty())
		{
			ptr = qua.top();
			qua.pop();
			cout << ptr->data << " ";
			if (ptr->leftchild != nullptr)
			{
				qub.push(ptr->leftchild);
			}
			if (ptr->rightchild != nullptr)
			{
				qub.push(ptr->rightchild);
			}
		}
		while (!qub.empty())
		{
			ptr = qub.top();
			qub.pop();
			cout << ptr->data << " ";
			if (ptr->rightchild != nullptr)
			{
				qua.push(ptr->rightchild);
			}
			if (ptr->leftchild != nullptr)
			{
				qua.push(ptr->leftchild);
			}
		}
	}
	cout << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

11、获取二叉树结点的个数

int GetSize(BtNode* ptr)
{
	if (ptr == nullptr)return 0;
	else
	{
		return GetSize(ptr->leftchild) + GetSize(ptr->rightchild) + 1;
	}
}
1
2
3
4
5
6
7
8

12、获取二叉树的深度

递归获取深度：

int Recursive_GetDeepth(BtNode* ptr)
{
	if (ptr == nullptr)
		return 0;
	else
	{
		return std::max(Recursive_GetDeepth(ptr->leftchild), Recursive_GetDeepth(ptr->rightchild));
	}
}
1
2
3
4
5
6
7
8
9

非递归获取：
这里在每一层次用了循环，直到每一层的下一层的节点都入队才结束。

int GetDeepth(BtNode* ptr)
{
	int sum = 0;
	if (ptr == nullptr)return sum;
	std::queue<BtNode*>qu;
	qu.push(ptr);
	while (!qu.empty())
	{
		int n = qu.size();
		while (n--)
		{
			ptr = qu.front();
			qu.pop();
			if (ptr->leftchild != nullptr)
			{
				qu.push(ptr->leftchild);
			}
			if (ptr->rightchild != nullptr)
			{
				qu.push(ptr->rightchild);
			}
		}
		sum += 1;
	}
	return sum;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

13、判断二叉树是否为满二叉树

这里我们用循环判断当前层次的节点数量是否为前一层次节点数量的两倍。

bool Is_Full(BtNode* ptr)
{
	int sum = 1;
	bool res = true;
	if (ptr == nullptr)
		return res;
	std::queue<BtNode*>qu;
	qu.push(ptr);
	while (!qu.empty())
	{
		int n = qu.size();
		if (n != sum)
		{
			res = false;
			return res;
		}
		while (n--)
		{
			ptr = qu.front();
			qu.pop();
			if (ptr->leftchild != nullptr)
			{
				qu.push(ptr->leftchild);
			}
			if (ptr->rightchild != nullptr)
			{
				qu.push(ptr->rightchild);
			}
		}
		sum += sum;
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

13、判断二叉树是否为完全二叉树

这里我们将二叉树不断入队列，出队列，如果是完全二叉树，则在后续的判断时，出的全是nullptr，如果出的不是空，则不是完全二叉树。

bool Is_Complete(BtNode* ptr)
{
	bool res = true;
	if (ptr == nullptr)return res;
	std::queue<BtNode*>qu;
	qu.push(ptr);
	while (!qu.empty())
	{
		ptr = qu.front();
		qu.pop();
		if (ptr == nullptr)break;
		qu.push(ptr->leftchild);
		qu.push(ptr->rightchild);
	}
	while (!qu.empty())
	{
		ptr = qu.front();
		qu.pop();
		if (ptr != nullptr)
		{
			res = false;
			return res;
		}
	}
	return res;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26