我们在前两篇博客中主要介绍了堆及其应用，针对的对象堆是完全二叉树，存储方式采用顺序结构存储的方式。
那么好的，这篇博客我们浅谈二叉树的链式存储，针对的对象是二叉树，并不局限于完全二叉树了！
我们先来回顾以下二叉树的定义：
一棵二叉树是结点的一个有限集合，该集合:
1. 或者为空（就是说空树也是二叉树）。
2. 不是空树：由一个根节点加上两棵别称为左子树和右子树的二叉树组成。
说简单点呢，二叉树是一颗特殊的树，这颗树的度最大为2，就像是对这颗树的节点进行了计划生育，最多只能生两个节点宝宝。
从图可以看出：
1. 二叉树不存在度大于2的结点。
2. 二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。3.二叉树的子树也都是二叉树，既然是二叉树就可以为空树。
从概念中可以看出，二叉树定义是递归式的：二叉树被拆成根节点、左子树和右子树，子树又被拆成根节点、左子树和右子树……直到拆成空树停止。因此后序基本操作中基本都是按照该概念实现的。
讲二叉树的链式存储，鼠鼠我需要构建一颗链式二叉树，鼠鼠先用硬编码的方式构建一颗二叉树，真正的链式二叉树构建是用递归构建的，鼠鼠后面讲：
typedef char BTDataType;
typedef struct BTNode
{
BTDataType data;
struct BTNode* leftchild;
struct BTNode* rightchild;
}BTNode;
//动态申请二叉树节点
BTNode* CreateBinaryTreeNode(BTDataType data)
{
BTNode* tmp = (BTNode*)malloc(sizeof(BTNode));
if (tmp == NULL)
{
perror("malloc fail");
exit(-1);
}
tmp->data = data;
tmp->leftchild = NULL;
tmp->rightchild = NULL;
return tmp;
}
int main()
{
BTNode* node1 = CreateBinaryTreeNode('A');
BTNode* node2 = CreateBinaryTreeNode('B');
BTNode* node3 = CreateBinaryTreeNode('C');
BTNode* node4 = CreateBinaryTreeNode('D');
BTNode* node5 = CreateBinaryTreeNode('E');
BTNode* node6 = CreateBinaryTreeNode('F');
BTNode* node7 = CreateBinaryTreeNode('G');
BTNode* node8 = CreateBinaryTreeNode('H');
BTNode* node9 = CreateBinaryTreeNode('I');
node1->leftchild = node2;
node1->rightchild = node6;
node2->leftchild = node3;
node3->leftchild = node4;
node4->rightchild = node5;
node6->leftchild = node7;
node7->leftchild = node8;
node8->rightchild = node9;
return 0;
}对于链式二叉树来说是由一个个节点构成的，我们定义节点如BTNode所示，很简单就不解释了。用也是很简单的逻辑我们写出了动态申请二叉树节点这个函数，在main函数上我们就可以调用该函数构建任意我们想要的链式二叉树，如代码所示我们构建的链式二叉树想象图为：
我们构建的这棵二叉树就用来测试下面实现接口的可行性！
1.二叉树的遍历
学习二叉树结构，最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。
1.1.前序遍历、中序遍历和后序遍历
二叉树的递归结构遍历有：前序/中序/后序的递归结构遍历：
1. 前序遍历(Preorder Traversal 亦称先序遍历)：访问根结点的操作发生在遍历其左右子树之前。
2. 中序遍历(Inorder Traversal)：访问根结点的操作发生在遍历其左右子树之中（间）。
3. 后序遍历(Postorder Traversal)：访问根结点的操作发生在遍历其左右子树之后。
就拿上面我们构建的二叉树来说：
前序遍历依次访问的节点是：ABCD#E####FGH#I#### 。
前序遍历划分层次为：
中序遍历依次访问的节点是：#D#E#C#B#A#H#I#G#F#。
中序遍历划分层次为：
后序遍历依次访问的节点是：###ED#C#B#H##I#G#FA。
后序遍历划分层次为：
其实并不是很复杂，拿前序遍历来说，我们知道二叉树是递归式定义的，每棵二叉树都可以拆成根节点、左子树和右子树……这样子一直拆，知道拆到空树为止。只要保证每棵二叉树访问顺序都是根节点——左子树——右子树。
注：这里的#表示访问到了空节点。
那么我们用递归实现的代码如下，我们通过前序/中序/后序遍历访问节点用于打印节点数据，这样我们可以很好的证实我们访问的顺序是符合上面分析的：
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //根节点 printf("%c ", root->data); //左子树 BinaryTreePrevOrder(root->leftchild); //右子树 BinaryTreePrevOrder(root->rightchild); } //二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //左子树 BinaryTreeInOrder(root->leftchild); //根节点 printf("%c ", root->data); //右子树 BinaryTreeInOrder(root->rightchild); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //左子树 BinaryTreePostOrder(root->leftchild); //右子树 BinaryTreePostOrder(root->rightchild); //根节点 printf("%c ", root->data); }
完整代码如下，将下面三个文件放到一个工程下面运行即可出结果：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); //二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root);2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //根节点 printf("%c ", root->data); //左子树 BinaryTreePrevOrder(root->leftchild); //右子树 BinaryTreePrevOrder(root->rightchild); } //二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //左子树 BinaryTreeInOrder(root->leftchild); //根节点 printf("%c ", root->data); //右子树 BinaryTreeInOrder(root->rightchild); } // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //左子树 BinaryTreePostOrder(root->leftchild); //右子树 BinaryTreePostOrder(root->rightchild); //根节点 printf("%c ", root->data); }3.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; // 二叉树前序遍历 BinaryTreePrevOrder(node1); printf("\n"); //二叉树中序遍历 BinaryTreeInOrder(node1); printf("\n"); // 二叉树后序遍历 BinaryTreePostOrder(node1); printf("\n"); return 0; }
运行结果：
我们看跟分析的结果一模一样。不过一般访问到空树的时候我们是不对其进行操作的，因为空树没有存储数据，没有操作的必要，这里遇到空树的时候打印'#'是为了更好验证分析！
鼠鼠在这里顺便提一嘴，前序遍历是一种深度优先遍历（dfs）。
1.2.层序遍历
层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。
拿这棵二叉树来说，层序遍历访问节点的顺序是ABFCGDHEI。
问题来了，我们如何实现层序遍历？
其实不难，这里我们不用递归实现，借用之前实现的队列即可。主要思想是 先将节点A的地址入队列，这样节点A地址就在对头了，再读取对头数据（即节点A地址）并将节点A地址出队列，通过读取的对头数据（即节点A地址）将A节点的左右子节点地址依次入队列（若为空指针就不入队列）。这样节点B的地址就在对头了，再读取对头数据（即节点B地址）并将节点B地址出队列，通过读取的对头数据（即节点B地址）将B节点的左右子节点地址依次入队列（若为空指针就不入队列）。这样节点F地址就在对头了，再……循环直到队列为空就停止这样就实现了层序遍历。
说通俗点就是A带B和F，B带C，F带G，C带D，G带H，D带E，H带I，当I出队列时队列就空了，那么就遍历完了！
层序遍历的代码如下，按照层序遍历访问节点打印出数据：
// 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front->leftchild) { QueuePush(&q, front->leftchild); } if (front->rightchild) { QueuePush(&q, front->rightchild); } } QueueDestroy(&q); }
我们用到了队列，只要将先前实现好的队列头文件和源文件复制粘贴到当前工程下，再包含队列头文件即可使用队列。当然因为我们在队列中存储的数据是节点的指针，所以头文件中的QDatatype要有所更改。完整代码如下，将下面五个文件放到一个工程下面就可以运行出结果：
1.queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> #include"BinaryTree.h" typedef BTNode* QDatatype; typedef struct QNode { QDatatype _data; struct QNode* _next; }QNode; typedef struct Queue { int k; QNode* head; QNode* tail; }Queue; //初始化队列 void QueueInit(Queue* q); //队尾入数据 void QueuePush(Queue* q, QDatatype data); //对头出数据 void QueuePop(Queue* q); //获取队列对头元素 QDatatype QueueFront(Queue* q); //获取队列队尾元素 QDatatype QueueBack(Queue* q); //获取队列中有效元素个数 int QueueSize(Queue* q); //检测队列是否为空，如果为空返回非零结果，非空返回0 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestroy(Queue* q);2.queue.c
#define _CRT_SECURE_NO_WARNINGS #include"queue.h" void QueueInit(Queue* q) { assert(q); q->head = q->tail = NULL; q->k = 0; } void QueuePush(Queue* q, QDatatype data) { assert(q); QNode* tmp = (QNode*)malloc(sizeof(QNode)); if (tmp == NULL) { perror("malloc fail"); return; } tmp->_data = data; tmp->_next = NULL; if (q->tail == NULL) { q->head = q->tail = tmp; } else { q->tail->_next = tmp; q->tail = tmp; } q->k++; } void QueuePop(Queue* q) { assert(q); assert(q->k > 0); QNode* next = q->head->_next; free(q->head); q->head = next; if (q->head == NULL) { q->tail = NULL; } q->k--; } QDatatype QueueFront(Queue* q) { assert(q); assert(q->k > 0); return q->head->_data; } QDatatype QueueBack(Queue* q) { assert(q); assert(q->k > 0); return q->tail->_data; } int QueueSize(Queue* q) { assert(q); return q->k; } bool QueueEmpty(Queue* q) { assert(q); return q->tail == NULL; } void QueueDestroy(Queue* q) { assert(q); QNode* tmp = q->head; while (tmp) { QNode* next = tmp->_next; free(tmp); tmp = next; } q->k = 0; q->head = q->tail = NULL; }3.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root);4.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" #include"queue.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } // 层序遍历 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); printf("%c ", front->data); if (front->leftchild) { QueuePush(&q, front->leftchild); } if (front->rightchild) { QueuePush(&q, front->rightchild); } } QueueDestroy(&q); }5.test.c
#include"queue.h" #include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; //层序遍历 BinaryTreeLevelOrder(node1); return 0; }
运行结果如下：
结果确实如我们分析所料，一层一层遍历访问节点并打印出节点存储的数据。
我们看上面运行结果来说是将所有节点数据全部打印到一行上了，那我们如何将所有节点数据分层打印出来呢？就是说第一行打印A；第二行打印B、F ；第三行打印C、G；第四行打印D、H；第五行打印E、I。
这个本质也是层序遍历，自是要控制好打印换行的时机罢了，我们看看代码：
//分层的层序遍历 void _BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q, root); int size = 1; while (!QueueEmpty(&q)) { while (size--) { BTNode* front = QueueFront(&q); printf("%c ", front->data); QueuePop(&q); if (front->leftchild) { QueuePush(&q, front->leftchild); } if (front->rightchild) { QueuePush(&q, front->rightchild); } } printf("\n"); size = QueueSize(&q); } QueueDestroy(&q); }这是其中一种办法，用一个size变量来记录每层的数据个数，那么每当size减到0就打印换行即可。
完整代码如下，将下面5个文件放到同一个工程下面运行即可得出结果：
1.queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> #include"BinaryTree.h" typedef BTNode* QDatatype; typedef struct QNode { QDatatype _data; struct QNode* _next; }QNode; typedef struct Queue { int k; QNode* head; QNode* tail; }Queue; //初始化队列 void QueueInit(Queue* q); //队尾入数据 void QueuePush(Queue* q, QDatatype data); //对头出数据 void QueuePop(Queue* q); //获取队列对头元素 QDatatype QueueFront(Queue* q); //获取队列队尾元素 QDatatype QueueBack(Queue* q); //获取队列中有效元素个数 int QueueSize(Queue* q); //检测队列是否为空，如果为空返回非零结果，非空返回0 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestroy(Queue* q);2.queue.c
#define _CRT_SECURE_NO_WARNINGS #include"queue.h" void QueueInit(Queue* q) { assert(q); q->head = q->tail = NULL; q->k = 0; } void QueuePush(Queue* q, QDatatype data) { assert(q); QNode* tmp = (QNode*)malloc(sizeof(QNode)); if (tmp == NULL) { perror("malloc fail"); return; } tmp->_data = data; tmp->_next = NULL; if (q->tail == NULL) { q->head = q->tail = tmp; } else { q->tail->_next = tmp; q->tail = tmp; } q->k++; } void QueuePop(Queue* q) { assert(q); assert(q->k > 0); QNode* next = q->head->_next; free(q->head); q->head = next; if (q->head == NULL) { q->tail = NULL; } q->k--; } QDatatype QueueFront(Queue* q) { assert(q); assert(q->k > 0); return q->head->_data; } QDatatype QueueBack(Queue* q) { assert(q); assert(q->k > 0); return q->tail->_data; } int QueueSize(Queue* q) { assert(q); return q->k; } bool QueueEmpty(Queue* q) { assert(q); return q->tail == NULL; } void QueueDestroy(Queue* q) { assert(q); QNode* tmp = q->head; while (tmp) { QNode* next = tmp->_next; free(tmp); tmp = next; } q->k = 0; q->head = q->tail = NULL; }3.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); //分层的层序遍历 void _BinaryTreeLevelOrder(BTNode* root);4.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" #include"queue.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } //分层的层序遍历 void _BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q, root); int size = 1; while (!QueueEmpty(&q)) { while (size--) { BTNode* front = QueueFront(&q); printf("%c ", front->data); QueuePop(&q); if (front->leftchild) { QueuePush(&q, front->leftchild); } if (front->rightchild) { QueuePush(&q, front->rightchild); } } printf("\n"); size = QueueSize(&q); } QueueDestroy(&q); }5.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; //分层的层序遍历 _BinaryTreeLevelOrder(node1); return 0; }
运行结果是没问题的：
鼠鼠在这里顺便提一嘴，层序遍历是一种广度优先遍历（bfs）。
2.二叉树节点个数
拿这棵树来说，节点个数是9个：
那我们该如何求呢？
当然我们可以用层序遍历，每出一个数据就计数一次，但是鼠鼠这里用的是递归的写法，思想是：当传入空树（就是传入节点指针为空指针）就返回0；不为空树就返回左子树节点个数+右子树节点个数+1即可。
我们看代码来体会一下：
//二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->leftchild) + BinaryTreeSize(root->rightchild) + 1; }
我们看看完整代码，3个文件放入同一个工程运行可出结果：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); //二叉树节点个数 int BinaryTreeSize(BTNode* root);2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } //二叉树节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) { return 0; } return BinaryTreeSize(root->leftchild) + BinaryTreeSize(root->rightchild) + 1; }3.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; //二叉树节点个数 printf("%d\n", BinaryTreeSize(node1)); return 0; }
看看运行结果，拿捏了：
3.二叉树叶子节点个数
还是用这棵树来说，这棵树的叶子节点是节点E、I，个数是2。
递归的方法很简单，如果传入空树（就是传入的节点指针是空指针）就返回0；如果传入的树没有左右子节点那么返回1；返回左子树叶子节点个数+右子树叶子节点个数即可。基于这个思想，代码如下：
//二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
if (root == NULL)
{
return 0;
}
if (root->leftchild == NULL && root->rightchild == NULL)
{
return 1;
}
return BinaryTreeLeafSize(root->leftchild) + BinaryTreeLeafSize(root->rightchild);
}完整代码是三个文件，将三个文件放入同一个工程下面运行可得结果：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); //二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root);2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } //二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->leftchild == NULL && root->rightchild == NULL) { return 1; } return BinaryTreeLeafSize(root->leftchild) + BinaryTreeLeafSize(root->rightchild); }3.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; //二叉树叶子节点个数 printf("%d\n", BinaryTreeLeafSize(node1)); return 0; }
运行结果也是轻松拿捏啊：
4.二叉树第k层节点个数
同样的，我们拿这棵树来说，第1层有1个节点，其他层都有2个节点；
拿以B节点为根节点的树来说，全部层都只有1个节点。
递归的思想也很简单：如果传入的是空树（也就是传入的节点地址为空指针），我们返回0；如果不为空树我们分两种情况：第一种找第1层节点个数的话我们返回1（第1层只有一个根节点必然节点数为1），第二种找第K层节点个数的话相当于找左子树第K-1层节点个数+右子树第K-1层节点个数。好捏，看代码：
// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BinaryTreeLevelKSize(root->leftchild, k - 1) + BinaryTreeLevelKSize(root->rightchild, k - 1); }
那么完整代码如下，放入同一个工程中哦：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k);2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BinaryTreeLevelKSize(root->leftchild, k - 1) + BinaryTreeLevelKSize(root->rightchild, k - 1); }3.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; // 二叉树第k层节点个数 printf("%d %d\n", BinaryTreeLevelKSize(node1, 1), BinaryTreeLevelKSize(node1, 3)); printf("%d\n", BinaryTreeLevelKSize(node2, 3)); return 0; }
看看运行结果：
5.二叉树高度
还是拿这颗二叉树来说，高度为5。
递归实现来说思想就是如果传入的是空树，我们返回0，不为空树的话我们返回左右子树高度中较大者+1（+1是为了加上根节点那层）。
//二叉树高度 int BinaryTreeHeight(BTNode* root) { if (root == NULL) { return 0; } return (int)fmax(BinaryTreeHeight(root->leftchild), BinaryTreeHeight(root->rightchild)) + 1; }
完整代码看一看，放入同一个工程可看结果哦：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<math.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); //二叉树高度 int BinaryTreeHeight(BTNode* root);这里要注意需要包含头文件<math.h>，因为我们用到了fmax这个函数。
2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } //二叉树高度 int BinaryTreeHeight(BTNode* root) { if (root == NULL) { return 0; } return (int)fmax(BinaryTreeHeight(root->leftchild), BinaryTreeHeight(root->rightchild)) + 1; }3.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; // 二叉树高度 printf("%d\n", BinaryTreeHeight(node1)); return 0; }
看好了，运行结果我只展示一次：
6.二叉树查找值为x的节点
找值为x的节点很简单，递归写法来说就是：如果传入空树，返回空指针：如果根节点就是值为x的节点，我们返回这个节点的地址；如果根节点的值不是x，我们在左子树找，找到返回，找不到就去右子树找，找到返回，找不到就返回空指针。
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
if (root == NULL)
{
return NULL;
}
if (root->data == x)
{
return root;
}
BTNode* find1 = BinaryTreeFind(root->leftchild, x);
if (find1)
{
return find1;
}
BTNode* find2 = BinaryTreeFind(root->rightchild, x);
if (find2)
{
return find2;
}
return NULL;
}
我们还是用这颗树来试试：
完整代码如下：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x);2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" //动态申请二叉树节点 BTNode* CreateBinaryTreeNode(BTDataType data) { BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("malloc fail"); exit(-1); } tmp->data = data; tmp->leftchild = NULL; tmp->rightchild = NULL; return tmp; } // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* find1 = BinaryTreeFind(root->leftchild, x); if (find1) { return find1; } BTNode* find2 = BinaryTreeFind(root->rightchild, x); if (find2) { return find2; } return NULL; }3.test.c
#include"BinaryTree.h" int main() { BTNode* node1 = CreateBinaryTreeNode('A'); BTNode* node2 = CreateBinaryTreeNode('B'); BTNode* node3 = CreateBinaryTreeNode('C'); BTNode* node4 = CreateBinaryTreeNode('D'); BTNode* node5 = CreateBinaryTreeNode('E'); BTNode* node6 = CreateBinaryTreeNode('F'); BTNode* node7 = CreateBinaryTreeNode('G'); BTNode* node8 = CreateBinaryTreeNode('H'); BTNode* node9 = CreateBinaryTreeNode('I'); node1->leftchild = node2; node1->rightchild = node6; node2->leftchild = node3; node3->leftchild = node4; node4->rightchild = node5; node6->leftchild = node7; node7->leftchild = node8; node8->rightchild = node9; // 二叉树查找值为x的节点 if (BinaryTreeFind(node1, 'H')) { printf("%c\n", BinaryTreeFind(node1, 'H')->data); } else { printf("找不到\n"); } return 0; }
运行结果也是预料之中：
7.通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"
好的呀，我们前面讲过链式二叉树一般不用硬编码的方式构建，一般用递归构建，那么鼠鼠现在就来浅浅介绍一下！
这里的意思就是写一个用递归实现的函数，该函数能实现输入一组二叉树前序遍历得到的数组就能将这棵二叉树构建出来并返回二叉树指针。
用递归实现的思想就是遍历数组元素，若为‘#’就返回空指针；若不为'#'就动态申请一个节点的空间并将该元素存入申请的空间当中，这个空间就是根节点，接着构建左子树和右子树就行。
/*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ BTNode* BinaryTreeCreate(BTDataType* a, int* pi) { if (*(a + *pi) == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->data = a[*pi]; (*pi)++; root->leftchild = BinaryTreeCreate(a, pi); root->rightchild = BinaryTreeCreate(a, pi); return root; }
为了印证我们确实是构建出来了这棵树，鼠鼠构建出来后用前序遍历依次访问节点并打印出来，那么完整代码如下三个文件：
1.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; /*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ BTNode* BinaryTreeCreate(BTDataType* a, int* pi); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root);2.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" /*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ BTNode* BinaryTreeCreate(BTDataType* a, int* pi) { if (*(a + *pi) == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->data = a[*pi]; (*pi)++; root->leftchild = BinaryTreeCreate(a, pi); root->rightchild = BinaryTreeCreate(a, pi); return root; } // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("# "); return; } //根节点 printf("%c ", root->data); //左子树 BinaryTreePrevOrder(root->leftchild); //右子树 BinaryTreePrevOrder(root->rightchild); }3.test.c
#include"BinaryTree.h" int main() { /*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ char a[] = "ABD##E#H##CF##G##"; int i = 0; BTNode* root = BinaryTreeCreate(a, &i); BinaryTreePrevOrder(root); return 0; }
运行结果表明确实是将这棵二叉树构建出来了：
那么这棵二叉树的想象图我给读者老爷画一画呀：
8. 判断二叉树是否是完全二叉树
我们判断二叉树是否是完全二叉树可以有很多方法，鼠鼠这里利用到了层序遍历的思想，但不同的是当左孩子节点或右孩子节点地址为空指针也一样入队列，当出队列遇到空指针就停止。此时若队列中还有非空指针就不是完全二叉树，反之就是完全二叉树。
// 判断二叉树是否是完全二叉树 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->leftchild); QueuePush(&q, front->rightchild); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { return false; } } return true; QueueDestroy(&q); }
我们拿上面递归构建的二叉树来试试这个代码，可以看出这棵二叉树不是完全二叉树：
那么试验这棵二叉树所需5个文件如下，有兴趣的老爷可以试试：
1.queue.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> #include"BinaryTree.h" typedef BTNode* QDatatype; typedef struct QNode { QDatatype _data; struct QNode* _next; }QNode; typedef struct Queue { int k; QNode* head; QNode* tail; }Queue; //初始化队列 void QueueInit(Queue* q); //队尾入数据 void QueuePush(Queue* q, QDatatype data); //对头出数据 void QueuePop(Queue* q); //获取队列对头元素 QDatatype QueueFront(Queue* q); //获取队列队尾元素 QDatatype QueueBack(Queue* q); //获取队列中有效元素个数 int QueueSize(Queue* q); //检测队列是否为空，如果为空返回非零结果，非空返回0 bool QueueEmpty(Queue* q); //销毁队列 void QueueDestroy(Queue* q);2.queue.c
#define _CRT_SECURE_NO_WARNINGS #include"queue.h" void QueueInit(Queue* q) { assert(q); q->head = q->tail = NULL; q->k = 0; } void QueuePush(Queue* q, QDatatype data) { assert(q); QNode* tmp = (QNode*)malloc(sizeof(QNode)); if (tmp == NULL) { perror("malloc fail"); return; } tmp->_data = data; tmp->_next = NULL; if (q->tail == NULL) { q->head = q->tail = tmp; } else { q->tail->_next = tmp; q->tail = tmp; } q->k++; } void QueuePop(Queue* q) { assert(q); assert(q->k > 0); QNode* next = q->head->_next; free(q->head); q->head = next; if (q->head == NULL) { q->tail = NULL; } q->k--; } QDatatype QueueFront(Queue* q) { assert(q); assert(q->k > 0); return q->head->_data; } QDatatype QueueBack(Queue* q) { assert(q); assert(q->k > 0); return q->tail->_data; } int QueueSize(Queue* q) { assert(q); return q->k; } bool QueueEmpty(Queue* q) { assert(q); return q->tail == NULL; } void QueueDestroy(Queue* q) { assert(q); QNode* tmp = q->head; while (tmp) { QNode* next = tmp->_next; free(tmp); tmp = next; } q->k = 0; q->head = q->tail = NULL; }3.BinaryTree.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> typedef char BTDataType; typedef struct BTNode { BTDataType data; struct BTNode* leftchild; struct BTNode* rightchild; }BTNode; /*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ BTNode* BinaryTreeCreate(BTDataType* a, int* pi); // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root);4.BinaryTree.c
#define _CRT_SECURE_NO_WARNINGS #include"BinaryTree.h" #include"queue.h" /*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ BTNode* BinaryTreeCreate(BTDataType* a, int* pi) { if (*(a + *pi) == '#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc fail"); exit(-1); } root->data = a[*pi]; (*pi)++; root->leftchild = BinaryTreeCreate(a, pi); root->rightchild = BinaryTreeCreate(a, pi); return root; } // 判断二叉树是否是完全二叉树 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->leftchild); QueuePush(&q, front->rightchild); } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); if (front) { return false; } } return true; QueueDestroy(&q); }5.test.c
#include"BinaryTree.h" #include"queue.h" int main() { /*通过前序遍历的数组构建二叉树, 叶节点子节点用'#'表示，如"ABD##E#H##CF##G##"*/ char a[] = "ABD##E#H##CF##G##"; int i = 0; BTNode* root = BinaryTreeCreate(a, &i); if (BinaryTreeComplete(root)) { printf("是完全二叉树\n"); } else { printf("不是完全二叉树\n"); } return 0; }
运行结果确实如我们所料：
当我们换一棵完全二叉树来测试时结果也没问题，代码只要更改main函数的数组a，将数组a改成完全二叉树前序遍历的数组即可，我们来看看：
没问题的！
9.二叉树销毁
二叉树销毁也用递归来完成，最好的办法时采用后续，因为根节点最后销毁的话方便我们找到左右子树，那么思想就是：先销毁左子树，再销毁右子树，最后销毁根节点即可。
//二叉树销毁 void BinaryTreeDestroy(BTNode* root) { if (root == NULL) { return; } //左子树 BinaryTreeDestroy(root->leftchild); //右子树 BinaryTreeDestroy(root->rightchild); //根节点 free(root); }这个我们就不测试了！
10.二叉树的性质
最后鼠鼠介绍一个二叉树的性质，挺重要的：对任何一棵二叉树, 如果度为0其叶结点个数为n， 度为2的分支结点个数为k，则有n=k+1。
比如这道题就用到了这个性质：
3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n
B n+1
C n-1
D n/2
答案是：A
因为是二叉树，那么二叉树节点的度只可能为0、1和2。那么设度为0的节点（即叶子节点）个数为X，设度为1的节点个数为Y，设度为2的节点个数为Z，那么X+Y+Z=X+Y+(X-1)=2X+Y-1=2n。
又因为是完全二叉树，那么度为1的节点个数要么是0个，要么是1个。当Y=0时，不可能满足2Z+Y+1=2n，因为2n时偶数；所有Y肯定为1，那么代入2X+1-1=2n即可得出X=n。
感谢阅读，欢迎斧正！