😽PREFACE
🎁欢迎各位→点赞👍 + 收藏⭐ + 评论📝
📢系列专栏：数据结构
🔊本专栏主要更新的是数据结构部分知识点
💪种一棵树最好是十年前其次是现在

目录

1.二叉树的顺序结构

2.二叉树的链式结构

3.创建结构和树

4.二叉树的遍历

4.1 前序遍历

4.2 中序遍历

4.3 后序遍历

4.4 层序遍历

5.二叉树常见玩法

5.1 节点个数

5.2 第k层叶节点个数

5.3 树的高度

5.4 查找值为x的节点

---

1.二叉树的顺序结构

普通的二叉树是不适合用数组来存储的，因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆 ( 一种二叉树 ) 使用顺序结构的数组来存储，需要注意的是这里的堆和操作系统 虚拟进程地址空间中的堆是两回事，一个是数据结构，一个是操作系统中管理内存的一块区域分段。

其实二叉树的顺序结构最典型的代表就是堆，关于可参见之前写过的博客： http://t.csdn.cn/UQ8Br

2.二叉树的链式结构

大体来说，二叉树的链式结构可分为而二叉链与三叉链。

//二叉链
typedef struct BinaryTreeNode
{
	BTDataType data;//当前节点的值域
	struct BinaryTreeNode* left;//指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

//三叉链
typedef struct BinaryTreeNode
{
	BTDataType data;//当前节点的值域
	struct BinaryTreeNode* left;//指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
	struct BinaryTreeNode* parent;//指向当前节点的双亲
}BTNode;

但通常情况下，我们使用的都是二叉链的结构。我们不妨回顾一下之前学过的数据结构，什么顺序表啊，链表啊，栈和队列等等，在初学这些结构的同时，我们都会关注其增删查改，但这些对于二叉树而言是没有什么意义的，我们在这里也不展开讨论。

3.创建结构和树

有了上面的铺垫，创建一个二叉链结构就会容易很多，代码如下：
 

//创建二叉链结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;//当前节点的值域
	struct BinaryTreeNode* left;//指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

有了结构，接下来就可以构造树了。光有结构还不行，我们还需要创建出节点，代码如下：
 

//创建二叉链结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;//当前节点的值域
	struct BinaryTreeNode* left;//指向当前节点左孩子
	struct BinaryTreeNode* right;//指向当前节点右孩子
}BTNode;

//创建节点
BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

//构造树
BTNode* CreatTree()
{
	//创建7个节点
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);
	//手动连接各节点之间的关系(根据具体树来定)
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->right = node6;
	node3->right = node7;
	//返回根节点
	return node1;
}

int main()
{
	BTNode* root = CreatTree();
    return 0;
}

4.二叉树的遍历

以这颗二叉树为例：

 首先遍历分为四种：分别是前序遍历，中序遍历，后序遍历，层次遍历

4.1 前序遍历

1.前序遍历 (Preorder Traversal）， 亦称先序遍历

2.遍历顺序： 根->左->右

3.图示结构：

 4.代码演示：

void PreOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	printf("%d ", root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

 

4.2 中序遍历

1.中序遍历(Inorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之中（间）。

2.遍历顺序： 左->根->右

3.图示结构：

 

4.代码演示：

void InOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

4.3 后序遍历

1.后序遍历 (Postorder Traversal)—— 访问根结点的操作发生在遍历其左右子树之后。

2.遍历顺序： 左->右->根

3.图示结构：

4.代码演示：

void PostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

4.4 层序遍历

1.层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。

2.遍历顺序：一层一层的遍历打印

3.图示结构：

4.代码展示：

void LevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);
	if (root)
	{
		QueuePush(&q, root);//根节点先入队列
	}
	while (!QueueEmpty(&q))
	{
		BTNode* front = QueueFront(&q);//取队头
		QueuePop(&q);//出队头
		printf("%d ", front->data);//打印队头数据
		if (front->left)
		{
			QueuePush(&q, front->left);
		}
		if (front->right)
		{
			QueuePush(&q, front->right);
		}
	}
	printf("\n");
	QueueDestory(&q);
}

5.二叉树常见玩法

5.1 节点个数

• 代码演示：

int TreeSize(BTNode* root)
{
	return root == NULL ? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

5.2 第k层叶节点个数

• 思路：如果一开始根节点为空，那么直接返回0，如果左右子树均为0，则该节点为叶节点，此时返回1 即可，如果不是这两种情况，那么就一直递归下去。
• 代码演示：

int TreeKLevel(BTNode* root, int k)
{
	if (root == NULL)
		return 0;
	if (k == 1)
		return 1;
	int leftk = TreeKLevel(root->left, k - 1);
	int rightk = TreeKLevel(root->right, k - 1);
	return leftk + rightk;
}

5.3 树的高度

• 思路：如果root节点为空，直接返回0，如果root==1，则返回1，如果不是这两种情况，就依次递归，分别定义左右高度变量来保存，最后还要比较一下，大的高度还要加一得到最终答案。
• 代码演示：

  int TreeHeight(BTNode* root)
  {
  	if (root == NULL)
  	{
  		return 0;
  	}
  
  	int leftHeight = TreeHeight(root->left);
  	int rightHeight = TreeHeight(root->right);
  	return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
  
  }

5.4 查找值为x的节点

• 思路：先去找根，看看根节点是否等于x，等于直接返回根，不等于先去左子树里面找，再去右子树里面找，如果左右子树都找不到则返回NULL
• 代码演示：

  BTNode* TreeFind(BTNode* root, BTDataType x)
  {
  	if (root == NULL)
  	{
  		return NULL;
  	}
  	if (root->data == x)
  	{
  		return root;
  	}
  	//去左子树找
  	BTNode* ret1 = TreeFind(root->left, x);
  	if (ret1)
  	{
  		return ret1;
  	}
  	//去右子树找
  	BTNode* ret2 = TreeFind(root->right, x);
  	if (ret2)
  	{
  		return ret2;
  	}
  	//都没找到返回NULL
  	return NULL;
  }