二叉树链式结构的实现

1. 二叉树链式结构介绍

二叉树链式结构是一种用于表示二叉树的计算机数据结构。在这种结构中，每个节点都包含三个字段：一个数据字段和两个链接字段，分别指向该节点的左子节点和右子节点。

2. 二叉树的节点定义

在链式结构中，二叉树的节点通常被定义为一个结构体或类，其中包含：

数据字段：用于存储节点的值或数据。
左链接字段：指向节点的左子节点的指针或引用。
右链接字段：指向节点的右子节点的指针或引用。

typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;//左链struct BinaryTreeNode* right;//右链
}BTNode;

3. 创建节点

首先得先创建一个个的节点，再通过链式结构链接起来。

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

4. 构建数的结构

这就是构建数的结构，7个节点链接起来，形成一个二叉树。

在这里插入图片描述

//构建数
BTNode* CreatBinaryTree()
{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->left = node5;node4->right = node6;node5->left = node7;return node1;
}

5. 二叉树的遍历

学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉
树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。遍历
是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

在这里插入图片描述
由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

链式结构的二叉树支持多种遍历方式，包括：

前序遍历：先访问根节点，然后遍历左子树，最后遍历右子树。

//前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);}

前序图解
在这里插入图片描述

效果图：
在这里插入图片描述

中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。这种遍历方式常用于二叉搜索树。

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

效果图：
在这里插入图片描述

后序遍历：先遍历左子树，然后遍历右子树，最后访问根节点。

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

效果图：
在这里插入图片描述

6. 二叉树节点的个数

方法1：采用遍历计算法

定义一个全局变量然后依次加

//方法1：遍历计算法
//二叉树节点的个数
int size = 0;void BTreeSize(BTNode* root)
{if (root == NULL)return;size++;BTreeSize(root->left);BTreeSize(root->right);
}

方法2：分治算法

分治算法是一种将复杂问题分解为更小的子问题，然后递归地解决这些子问题，并将它们的解合并起来以得到原问题解的算法策略。

将一个规模为N的问题分解为K个规模较小的子问题。
这些子问题相互独立且与原问题性质相同。
递归地解决这些子问题，直到子问题规模足够小，可以直接求解。
将子问题的解合并起来，形成原问题的解。

//方法2：分治算法
//二叉树节点的个数
int BTreeSize(BTNode* root)
{if (root == NULL)return 0;return BTreeSize(root->left)+ BTreeSize(root->right) + 1;
}

7. 求叶子节点的个数

叶子节点是那些没有子节点的节点，即它们的左子节点和右子节点都是空的。

//求叶子节点的个数
int BTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL&& root->right == NULL)return 1;return BTreeLeafSize(root->left)+ BTreeLeafSize(root->right);
}

8. 求二叉树的高度

我们通常需要遍历整个二叉树。在遍历的过程中，我们可以特别检查每个节点是否为叶子节点（即该节点没有左子节点和右子节点）

//求二叉树的高度
int BTreeHight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = BTreeHight(root->left);int rightHeight = BTreeHight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}

9. 二叉树第k层节点个数

子问题：转换成左子树的第k-1层和右子树的k-1层。
结束条件：

k==1 且节点不为空
节点为空

//二叉树第k层节点个数
int BTreeLevelSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return BTreeLevelSize(root->left, k - 1)+ BTreeLevelSize(root->right, k - 1);
}

10. test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>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("BuyNode");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}//构建数
BTNode* CreatBinaryTree()
{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->left = node5;node4->right = node6;node5->left = node7;return node1;
}//前序遍历
void PrevOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}printf("%d ", root->data);PrevOrder(root->left);PrevOrder(root->right);}//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);}//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){printf("N ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);}//方法1：遍历计算法
//二叉树节点的个数//int size = 0;
//
//void BTreeSize(BTNode* root)
//{
//	if (root == NULL)
//		return;
//
//	size++;
//	BTreeSize(root->left);
//	BTreeSize(root->right);
//}//方法2：分治算法
//二叉树节点的个数
int BTreeSize(BTNode* root)
{if (root == NULL)return 0;return BTreeSize(root->left)+ BTreeSize(root->right) + 1;
}//求叶子节点的个数
int BTreeLeafSize(BTNode* root)
{if (root == NULL)return 0;if (root->left == NULL&& root->right == NULL)return 1;return BTreeLeafSize(root->left)+ BTreeLeafSize(root->right);
}//求二叉树的高度
int BTreeHight(BTNode* root)
{if (root == NULL)return 0;int leftHeight = BTreeHight(root->left);int rightHeight = BTreeHight(root->right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}//二叉树第k层节点个数
int BTreeLevelSize(BTNode* root, int k)
{assert(k > 0);if (root == NULL)return 0;if (k == 1)return 1;return BTreeLevelSize(root->left, k - 1)+ BTreeLevelSize(root->right, k - 1);
}//二叉树查找值为x的节点
BTNode* BTreeFind(BTNode* root, BTDataType x)
{if (root == NULL)return NULL;if (root->data == x)return root;int str1 = BTreeFind(root->left, x);if (str1)return str1;int str2 = BTreeFind(root->right, x);if (str2)return str2;return NULL;
}int main()
{BTNode* root = CreatBinaryTree();PrevOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");BTreeSize(root);printf("BTreeSize：%d\n", BTreeSize(root));printf("BTreeLeafSize:%d\n", BTreeLeafSize(root));printf("BTreeHight:%d\n", BTreeHight(root));printf("BTreeLevelSize:%d\n", BTreeLevelSize(root, 3));printf("BTreeLevelSize:%d\n", BTreeLevelSize(root, 4));return 0;
}