5.1.数据结构-c/c++二叉树详解(上篇)（遍历，几种二叉树）

本章所有代码请见：5.3.数据结构-c/c++二叉树代码-CSDN博客

目录

一. 二叉树的基本介绍

1.2 满二叉树

1.3 完全二叉树

1.4 搜索二叉树

1.5 平衡二叉搜索树

二. 二叉树的常用操作

2.1 二叉树的定义

2.2 创建一个新的节点

2.3 构建一颗树

2.5 销毁一棵树

三.二叉树的前序，中序，后序，层序遍历方法

3.1 前序遍历

3.2 中序遍历

3.3 后序遍历

3.4 层序遍历

四.下篇内容（算法面试题）

一. 二叉树的基本介绍

        二叉树是一种每一个节点最多只有两个子树的树结构。

树的5种基本结构如下图

几种特殊的二叉树结构

1.2 满二叉树

        二叉树的每一层是满的，节点数量为2*h-1        h为树的高度

下图两种树都为满二叉树

1.3 完全二叉树

        在一颗二叉树中，只有最后两层节点的度小于2，且所有的叶子节点都依次集中在左侧

1.4 搜索二叉树

在一颗二叉树中，该树可以为空。如果不为空，则要满足下列条件

1.树中的每一个子树的左子树都小于其根节点

2.树中每一颗子树的右子树都大于其根节点

3.所有子树都是二叉搜索树

1.5 平衡二叉搜索树

       1. 二叉搜索树的左右子树高度差不超过1

       2.左右子树都是二叉搜索树

       3.节点中包含平衡因子

满足以上三点的二叉搜索树就是平衡二叉搜索树

二. 二叉树的常用操作

2.1 二叉树的定义

//定义节点
typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

2.2 创建一个新的节点

//创建一个新节点
BTNode* CreatNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	assert(node);

	//更新节点的值，并将左右指针置空
	node->data = x;
	node->left = nullptr;
	node->right = nullptr;
	return node;
}

2.3 构建一颗树

	//根据需求依次构建节点并连接即可
    BTNode* A = CreatNode('A');
	BTNode* B = CreatNode('B');
	BTNode* C = CreatNode('C');
	BTNode* D = CreatNode('D');
	BTNode* E = CreatNode('E');
	BTNode* F = CreatNode('F');
	BTNode* G = CreatNode('G');


	A->left = B;
	A->right = C;
	B->left = D;
	B->right = E;
	C->left = F;
	C->right= G;

2.5 销毁一棵树

利用前序遍历，依次释放每一个节点即可

//销毁一棵树//使用后续销毁
void TreeDestory(BTNode* root)
{
	if (root == NULL)
		return;

	TreeDestory(root->left);
	TreeDestory(root->right);
	free(root);
} 

三.二叉树的前序，中序，后序，层序遍历方法

3.1 前序遍历

利用递归思想，要访问一棵树的所有节点，访问根节点后，访问子树的节点

//前序遍历
void PrevOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "NULL ";
		return;
	}

	cout << root->data << " ";	//访问根节点
	PrevOrder(root->left);		//访问左子树
	PrevOrder(root->right);		//访问右子树
}

3.2 中序遍历

//中序遍历
void InOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "NULL ";
		return;
	}
	
	//中序遍历前访问左子树，再访问根节点，最后访问右子树
	InOrder(root->left);		//访问左子树
	cout << (char)root->data << " ";	//访问根节点
	InOrder(root->right);		//访问右子树
}

3.3 后序遍历

//后序遍历
void NextOrder(BTNode* root)
{
	if (root == nullptr)
	{
		cout << "NULL ";
		return;
	}

	//后序遍历先访问左子树，在访问右子树。最后访问根节点
	NextOrder(root->left);		//访问左子树
	NextOrder(root->right);		//访问右子树
	cout << (char)root->data << " ";	//访问根节点
}

3.4 层序遍历

利用队列的先进先出特点。

将一层的节点都放入队列中，然后依次访问队首的数据并将其左右子节点放入队列中

如下图

代码 

//层序遍历(广度优先遍历)，该遍历需要我们使用到队列先进先出的特点
void TreeLeverOrder(BTNode* root)
{
	if (root == nullptr)
	{
		return;
	}

	queue<BTNode*> q;
	q.push(root);
	while (!q.empty())
	{
		BTNode* front = q.front();
		if (front->left)
		{
			q.push(front->left);
		}

		if (front->right)
		{
			q.push(front->right);
		}

		cout << (char)q.front()->data << " ";
		q.pop();
	}
	cout << endl;
}

四.下篇内容（算法面试题）

求二叉树 第k层的节点

查找一个节点是否在二叉树中

求二叉树节点的个数

求二叉树叶子节点的个数

求树的深度

判断一棵树是否为完全二叉树