数据结构：二叉树(链式结构)

1. 二叉树的链式结构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成：数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链，三叉链在结构上比二叉链多了一个指向父节点的指针域。

在这里先使用二叉链来实现二叉树

2. 二叉树的创建和实现相关功能

2.1 创建二叉树

用链表来实现二叉树，每个链表结点都由一个数据域和左右指针域组成

//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;

接下来我们来实现创建节点的函数：

首先使用malloc函数创建一个节点大小的空间，如果创建失败就打印错误信息，创建成功则把数据存储在新节点的数据域中，再将新节点的左右孩子指针指向空，最后返回新节点即可

//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}

下面我们来创建一棵如图所示的二叉树

BTNode* CreateTree()
{BTNode* node1 = buyNode(1);BTNode* node2 = buyNode(2);BTNode* node3 = buyNode(3);BTNode* node4 = buyNode(4);BTNode* node5 = buyNode(5);BTNode* node6 = buyNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}

2.2 二叉树的前，中，后序遍历

下面来简单介绍一下前，中，后序遍历的规则


下面来根据上面所示的二叉树进行前，中，后序遍历

2.2.1 前序遍历

前序遍历就是先打印根节点的值，再遍历根节点的左子树，最后遍历根节点的右子树，也就是根左右

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

根据以上代码：进入函数先打印根节点存储的值，再递归左子树，左子树递归完后再递归右子树。不要忘了，如果遇到空节点记得要返回。

前序遍历的步骤：

1. 打印根节点的值为1
2. 递归左子树，创建根节点左孩子节点2的函数栈帧
3. 打印节点2的值为2，创建节点2的左孩子节点4的函数栈帧
4. 打印节点4的值为4，创建节点4的左孩子节点的函数栈帧
5. 节点4的左孩子节点为空，返回节点4的函数栈帧
6. 创建节点4的右孩子节点的函数栈帧
7. 节点4的右孩子节点为空，返回节点4的函数栈帧
8. 节点4的函数栈帧被销毁，返回节点2的函数栈帧
9. 创建节点2的右孩子节点5的函数栈帧
10. 打印节点5的值为5，创建节点5的左孩子节点的函数栈帧
11. 节点5的左孩子节点为空，返回节点5的函数栈帧
12. 创建节点5的右孩子节点的函数栈帧
13. 节点5的右孩子节点为空，返回节点5的函数栈帧
14. 节点5的函数栈帧被销毁，返回节点2的函数栈帧
15. 节点2的函数栈帧被销毁，返回根节点的函数栈帧
16. 创建根节点的右孩子节点3的函数栈帧
17. 打印节点3的值为3，创建节点3的左孩子节点6的函数栈帧
18. 打印节点6的值为6，创建节点6的左孩子节点的函数栈帧
19. 节点6的左孩子节点为空，返回节点6的函数栈帧
20. 创建节点6的右孩子节点的函数栈帧
21. 节点6的右孩子节点为空，返回节点6的函数栈帧
22. 节点6的函数栈帧被销毁，返回节点3的函数栈帧
23. 创建节点3的右孩子节点的函数栈帧
24. 节点3的右孩子节点为空，返回节点3的函数栈帧
25. 节点3的函数栈帧被销毁，返回根节点的函数栈帧
26. 根节点的函数栈帧被销毁

所以前序遍历的结果为：1 2 4 5 3 6

中序遍历和后序遍历与前序遍历的思路一样，只是打印节点的值和递归左右子树的顺序不同而已

2.2.2 中序遍历

思路：先遍历根节点的左子树，再打印根节点的值，最后遍历根节点的右子树，也就是左根右

中序遍历的结果：4 2 5 1 6 3

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

2.2.3 后序遍历

思路：先遍历根节点的左子树，再遍历根节点的右子树，最后打印根节点的值，也就是左右根

后序遍历的结果：4 5 2 6 3 1

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

2.3 二叉树节点个数

思路：先递归根节点的左子树，再递归根节点的右子树，如果递归到空节点就返回0，最后返回左子树节点个数和右子树节点个数的和再加一

//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}

2.4 二叉树叶子结点个数

思路：第一种情况：如果递归到的当前节点为空就返回0，第二种情况：如果节点的左右子树为空时说明该节点为叶子节点则返回1，第三种情况：如果递归到的节点既不是空又不是叶子节点，则继续递归该节点的左右子树，即返回该节点左右子树的叶子节点 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right)

//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}

2.5 二叉树第k层结点个数

思路：因为根节点是第一层，所以每次向下遍历时将k减一，当k=1时当前节点就是在第k层，返回1即可，所以只需一直递归节点的左右子树，每次递归节点的左右子树时还要让k减一。当递归到的节点为空时，只需返回0即可，要先判断节点为不为空，如果不为空再判断当前节点是不是在第k层。

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

2.6 二叉树的深度/高度

思路：因为二叉树的左右子树的高度可能不一样，所以要分开递归二叉树的左右子树，然后再取最大值即可。当递归到空节点时返回0，否则继续递归当前节点的左右子树，最后返回左右子树深度的最大值再加一(因为当前的根节点也是一层)

//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}

2.7 二叉树查找值为x的结点

思路：先遍历根节点的左子树，如果找到了值为x的节点就返回该节点的地址，右子树也无需再遍历了，如果没有找到再遍历右子树，如果找到了就返回该节点的地址，没有找到则返回空。再遍历的过程中，先判断节点是否为空，如果为空就返回空，不为空的话再判断该节点的值是不是x，如果是就返回该节点的地址，如果不是就继续遍历该节点的左右子树。

//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftfind = BinaryTreeFind(root->left, x);if (leftfind){return leftfind;}BTNode* rightfind = BinaryTreeFind(root->right, x);if (rightfind){return rightfind;}return NULL;
}

2.8 层序遍历

这里需要借助队列，不熟悉的可以看一下数据结构—队列

层序遍历是指从根节点开始一层一层遍历二叉树，从上至下，从左至右，依次访问节点，如下图，该二叉树的层序遍历结果为：1 2 3 4 5 6

使用队列这个数据结构来实现层序遍历，队列的特点是先进先出。首先将根节点放入队列中，再将根节点出队，最后将根节点的左右孩子节点入队。将根节点的左孩子2出队，然后将根节点的左孩子2的左右孩子节点入队，以此类推……一直到队列为空

//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

2.9 判断二叉树是否为完全二叉树

思路：同样还是借助队列这个数据结构，与层序遍历不同的是，当节点的左右孩子节点为空时也要进行入队操作，当队头为空时，就退出循环，然后还需要判断队列里有没有不为空的节点，如果有说明二叉树不为完全二叉树，如果没有说明二叉树为完全二叉树

//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

2.10 二叉树的销毁

思路：因为要销毁整个二叉树包括根节点，所以这里传递的是二级指针去接收一级指针的地址，这样就实现了形参改变实参。先销毁根节点的左子树和右子树，也就是递归到叶子节点开始销毁，然后往上一层一层地进行销毁，最后再销毁根节点。

//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}

3. 源代码

Tree.h头文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义二叉树的链式结构
//二叉树结点的结构
typedef int BTDataType;
typedef struct BinaryTreeNode {BTDataType data;//存储数据struct BinaryTreeNpde* left;//指向左孩子结点的指针struct BinaryTreeNode* right;//指向右孩子结点的指针
}BTNode;//创建二叉树新节点
BTNode* buyNode(BTDataType x);
//创建一个二叉树
BTNode* CreateTree();
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
//二叉树结点个数
int BinaryTreeSize(BTNode* root);
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root);
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
//二叉树销毁
void BinaryTreeDestory(BTNode** root);
//层序遍历
void LevelOrder(BTNode* root);
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root);

Tree.c源文件

#include "Tree.h"
#include "Queue.h"
//创建二叉树新节点
BTNode* buyNode(BTDataType x)
{BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}newnode->data = x;newnode->left = newnode->right = NULL;return newnode;
}
//前序遍历
void PreOrder(BTNode* root)
{if (root == NULL){return;}printf("%d ", root->data);PreOrder(root->left);PreOrder(root->right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root == NULL){return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}
//后序遍历
void PostOrder(BTNode* root)
{if (root == NULL){return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}
//二叉树结点个数
int BinaryTreeSize(BTNode* root)
{if (root == NULL){return 0;}return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
//二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root == NULL){return 0;}if (root->left == NULL && root->right == NULL){return 1;}return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
//二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root == NULL){return 0;}if (k == 1){return 1;}return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
//二叉树的深度/高度
int BinaryTreeDepth(BTNode* root)
{if (root == NULL){return 0;}int leftDepth = BinaryTreeDepth(root->left);int rightDepth = BinaryTreeDepth(root->right);return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;
}
//二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root == NULL){return NULL;}if (root->data == x){return root;}BTNode* leftfind = BinaryTreeFind(root->left, x);if (leftfind){return leftfind;}BTNode* rightfind = BinaryTreeFind(root->right, x);if (rightfind){return rightfind;}return NULL;
}
//二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (*root == NULL){return;}BinaryTreeDestory(&((*root)->left));BinaryTreeDestory(&((*root)->right));free(*root);*root = NULL;
}
//层序遍历
void LevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);printf("%d ", front->data);QueuePop(&q);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}
//判断二叉树是否为完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front == NULL){break;}QueuePush(&q, front->left);QueuePush(&q, front->right);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

test.c源文件

#include "Tree.h"BTNode* CreateTree()
{BTNode* node1 = buyNode(1);BTNode* node2 = buyNode(2);BTNode* node3 = buyNode(3);BTNode* node4 = buyNode(4);BTNode* node5 = buyNode(5);BTNode* node6 = buyNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}void BinaryTreeTest01()
{BTNode* node1 = CreateTree();PreOrder(node1);printf("\n");InOrder(node1);printf("\n");PostOrder(node1);printf("\n");printf("%d\n", BinaryTreeSize(node1));printf("%d\n", BinaryTreeLeafSize(node1));printf("第%d层结点个数为：%d\n", 3, BinaryTreeLevelKSize(node1, 3));printf("%d\n", BinaryTreeDepth(node1));if (BinaryTreeFind(node1, 10) == NULL){printf("没有找到\n");}else{printf("找到了\n");}LevelOrder(node1);printf("\n");printf("%s\n", BinaryTreeComplete(node1) == true ? "是完全二叉树" : "不是完全二叉树");BinaryTreeDestory(&node1);
}
int main()
{BinaryTreeTest01();return 0;
}

对以上内容有不同看法的欢迎来讨论，希望对大家的学习有帮助，多多支持哦！