6.层序遍历：
执行操作前需进行非空判断，防止对空指针进行操作。
层序遍历操作原理示意图：
层序遍历就是一层一层的遍历，在链式储存中，我们一般借助队列来实现层序遍历。
利用的是队列的先进先出的性质。先让根入队，然后出队头数据，再让队头数据的左右孩子入队。每从队头删除掉一个元素，就让这个元素的两个孩子入队，直到队列为空为止。
首先创建队列，并对队列进行初始化。接着让二叉树的根入队
注意 记得修改队列元素的类型 typedef BinaryTreeNode* QDataType; //结构体指针。
判断队列是否为空，如果队列为空，说明遍历已经结束，应当换行并销毁队列。若队列不为空，就将队头的节点拷贝出来，然后删除队头节点，把拷贝的队头节点数据进行打印，最后让拷贝接节点的左右孩子先后入队。如果孩子没有子节点，相当于使空 NULL 入队，并不影响访问结果。
void TreeLevelOrder(BNode* root) { Q q; QInit(&q);//初始化队列 if (root)//不是空树 { QPush(&q, root);//push root } while (!QEmpty(&q))//队列不为空 { BNode* front = QFront(&q);//取对头数据 QPop(&q);//这里只是pop了队列的头节点，但值被局部变量front保存下来了 //树的节点也依然存在 printf("%c ", front->data);//所以可以打印这个值 if (front->left)//不为空，入左树 { QPush(&q, front->left); } if (front->right)//不为空，入右树 { QPush(&q, front->right); } } printf("\n"); QDestroy(&q);//及时销毁 }
7.二叉树节点个数：
执行操作前需进行非空判断，防止对空指针进行操作。
对于二叉树节点数量的统计，采用的方式是任意选择一种遍历顺序（只依照遍历顺序，不访问节点），遍历整个树结构，每找到一个节点让计数变量加一即可。
思路1 ：使用前序 /中序 /后序遍历，全局变量记录
但是以下代码有 Bug ：如果采用前序重复遍历 2 次
主要问题出在全局变量上，这里只需要在第 2 次遍历时置 0 即可(size=0)
学习了以后的知识，会发现这种操作还有线程安全的问题
思路 2：函数使用带返回值的方式，其内部的递归本质上是一个后序遍厉
//不能直接用size 线程安全问题 void TreeSize(BNode* root, int* size) { if (root == NULL) { printf("TreeSize Get Error!\n"); return; } (*size)++; TreeSize(root->left, size); TreeSize(root->right, size); } //分治-分而治之 //其实这种就是递归的思想，在现实生活中也经常使用到 //比如 1 位校长要统计学校的人数，他不可能亲自去挨个数 //一般是通过院长、系主任、辅导员、班长、舍长的层层反馈才得到结果的 int BinaryTreeSize(BNode* root) { return root==NULL ? 0:TreeSize(root->left)+TreeSize(root->right)+1; }
8.求树的高度/深度
核心思想 ：当前树的深度 = max (左子树的深度，右子树的深度) + 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; }
9.第 K 层节点个数：
执行操作前需进行非空判断，防止对空指针进行操作。
若根节点为空，则节点的个数为0。如果我们要计算第 K 层的元素（节点）个数，首先从根节点开始统计，假设我们每向下一层 K 就减 1，那么当 K = 1 时，表示我们来到了第 K 层，然后计算 K = 1 时的节点个数返回值相加的结果即可。
核心思想 ：求当前树的第 k 层 = 左子树的第 k - 1 层 + 右子树的第 k - 1 层 (当 k = 1 时，说明此层就是目标层)
int TreeKLevelSize(BNode* root, int k) { assert(k>0); if (root == NULL) { printf("TreeKLevelSize Get Error!\n"); return 0; } if (k == 1) { return 1; } int leftk=TreeKLevelSize(root->left, k - 1); //要及时存储递归后的值，不然忘了又要算一遍，浪费时间 int rightk=TreeKLevelSize(root->right, k - 1); return leftk + rightk; }
8.叶节点个数：
执行操作前需进行非空判断，防止对空指针进行操作。
叶节点就是度为0的节点，即没有子树，我们同样使用递归进行统计。
根节点进入函数后，应当首先判断根节点是否为叶节点，如果一个节点的左子树和右子树同时为空，说明这是一个叶节点；如果不是，其左子树的叶节点和右子树的叶节点之和就是当前节点以下的所以叶节点，形成递归。
核心思想 ：以 left 和 right 为标志，如果都为 NULL，则累加
int TreeLeafSize(BNode* root) { if (root == NULL) { printf("TreeLeafSize Get Error!\n"); return 0; } else { return (root->left) == NULL && (root->right) == NULL ? 1 : TreeLeafSize(root->left) + TreeLeafSize(root->right); } }
10.查找值为x的节点：
执行操作前需进行非空判断，防止对空指针进行操作。
若节点为空，就返回空。若节点的值等于要查找的值，就返回该节点。
若节点不为空，但节点的值不是我们要查找的值，就查找节点的左子树，如果查找的结果不为空，就返回该节点。若左子树的查找结果为空，就以同样的方式处理右子树。如果都找不到，就返回空。
核心思想 ：
1、先判断是不是当前节点，是就返回，不是就继续找；
2、先去左树找，找到就返回
3、左树没找到，再找右树
BNode* TreeFind(BNode* root, BDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BNode* lret = TreeFind(root->left, x); if (lret) { return lret; } BNode* rret = TreeFind(root->right, x); if (rret) { return rret; } return NULL; } //简化版本 BNode* TreeFind(BNode* root, BDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BNode* lret = TreeFind(root->left, x); if (lret) { return lret; } returnTreeFind(root->right, x); }
11.完全二叉树判断：
执行操作前需进行非空判断，防止对空指针进行操作。
判断是否为完全二叉树需要用到层序遍历的思想。
若一个二叉树不是完全二叉树时，那么当我们对它进行层序遍历时，其中的部分节点就会是 NULL，于是我们可以通过这一点来判断一个二叉树是否为完全二叉树。
前半部分与二叉树的层序遍历一样，建队列，根入队，队列不为空，进入while循环，在循环中删队头节点，然后让该节点的左右孩子入队。
注意 这里循环停止的条件还要加上一个即堆顶的元素为空。
在跳出循环后存在两种情况，第一种是队列已空，节点之间没有空，表明是完全二叉树，返回true；而第二种情况是队列不为空，但在访问队头节点时访问到了 NULL，这时我们需要再次进行循环，若队列不为空，就进入循环逐个查找并删除队头的节点，若发现不为空的节点，说明节点间有 NULL 相隔，即该二叉树不是完全二叉树，返回false。
步骤：
给一个辅助队列。
如果 root 非空，则将 root 入队。
然后给定循环队列为空则停止，取队头元素，并出队头；这时将取出元素的左右子树都放入，一旦出元素出到 NULL 这时结束循环。
完全二叉树是连续的，一旦出现 NULL ，那么后面的元素都应该是空。如果空指针后还有非空元素，那么一定不是完全二叉树。
这时继续出队列，如果出队列过程中遇到非空元素，则销毁队列返回假；否则不断出队列元素。
如果循环结束还没有返回，说明后面都是空指针，这时销毁队列，返回真。
bool BinaryTreeComplete(BTNode* root) { // 使用层序遍历思想 Q q; QueueInit(&q); // 如果非空，则入队列 if (root) QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); // 一旦出队列到空，就出去判断 if (front == NULL) { break; } else { QueuePush(&q, front->left); QueuePush(&q, front->right); } } while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); if (front != NULL) { QueueDestroy(&q); return false; } else { QueuePop(&q); } } QueueDestroy(&q); return true; }
12.二叉树销毁：
执行操作前需进行非空判断，防止对空指针进行操作。
销毁二叉树需要把二叉树的每个节点都销毁，故采用后序遍历的顺序进行销毁。
注意：节点里存放的是左右孩子的指针，若我们在传参时仅传递节点的指针类型，则函数中的左右孩子地址就是一份临时拷贝，将导致无法对每个节点的指针进行置空，故我们在销毁二叉树时，函数参数应当传递二级指针。
先销毁左树，再销毁右树，最后销毁根
注意pproot是t的拷贝，应该传二级指针（或C++引用取别名）
void BinaryTreeDestory(BNode** pproot)//*& C++引用取别名 { if (*pproot == NULL) { printf("BinaryTreeDestroy Error!\n"); return NULL; } BinaryTreeDestory(&(*pproot)->left); BinaryTreeDestory(&(*pproot)->right); free(*pproot); pproot = NULL; }
四、链式存储结构完整代码：
1.Heap.h：
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> //队列（为层序遍历做准备）： typedef BinaryTreeNode* QDataType;//结构体指针 typedef struct QueueNode { QDataType data; struct QNode* next; }QNode; typedef struct Queue { QNode* head; QNode* tail; }Q; void QInit(Q* p); //初始化队列 void QPush(Q* p, QDataType x); //入队 void QPop(Q* p); //出队 QDataType QFront(Q* p); //查看队头 bool QEmpty(Q* p); //查看队列容量 void QDestroy(Q* p); //队列的销毁 //二叉树的链式结构： typedef char BDataType; typedef struct BinaryTreeNode { struct BinaryTreeNode* left; // 指向当前节点左孩子 struct BinaryTreeNode* right; // 指向当前节点右孩子 BDataType data; // 当前节点值域 }BNode; BNode* BuyNode(BDataType x); //二叉树节点创建 void PrevOrder(BNode* root); // 前序遍历 void InOrder(BNode* root); // 中序遍历 void PostOrder(BNode* root); // 后序遍历 void TreeLevelOrder(BNode* root); //层序遍历 void TreeSize(BNode* root, int* size); // 统计二叉树节点个数 int BinaryTreeSize(BTNode* root);// 二叉树节点个数 int BinaryTreeDepth(BTNode* root)//二叉树深度/高度 int TreeLeafSize(BNode* root); // 计算二叉树叶节点个数 int TreeKLevelSize(BNode* root, int k); // 计算第 K 层的节点个数 BNode* TreeFind(BNode* root, BDataType x); // 查找元素（节点） bool BinaryTreeComplete(BNode* root); // 完全二叉树判断
2.Heap.c：
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" //队列部分接口（为层序遍历做准备）： //初始化队列 void QInit(Q* p) { if (p == NULL) { printf("QueueINit fail\n"); return; } p->head = NULL; p->tail = NULL; } //入队： void QPush(Q* p, QDataType x) { if (p == NULL) { printf("QueuePush fail\n"); return; } //申请新节点： QNode* newnode = (QNode*)malloc(sizeof(QNode)); newnode->data = x; newnode->next = NULL; //分情况插入： if (p->head == NULL) { p->head = p->tail = newnode; } else { //将新节点连接在队尾： p->tail->next = newnode; //更新队尾： p->tail = newnode; } } //出队： void QPop(Q* p) { if (p == NULL) { printf("QueuePop fail\n"); exit; } if (QEMpty(p)) { printf("Queue is NUll\n"); return; } else { QNode* next = p->head->next; //记录第二数据 free(p->head); //释放原头节点 p->head = next; //更新头节点 //注意对删空队列的情况应进行区分处理 if (p->head == NULL) { p->tail = NULL; } } } //查看队头 QDataType QFront(Q* p) { if (p == NULL) { printf("QueueFront get fail\n"); return; } if (QEmpty(p)) { printf("The Queue is NULl\n"); return; } return p->head->data; } //查看队列容量 bool QEmpty(Q* p) { if (p == NULL) { printf("QueueEmpty fail\n"); return; } return p->head == NULL; } //队列的销毁： void QDestroy(Q* p) { if (p == NULL) { printf("QueueNodeDestroy fail\n"); exit; } QNode* cur = p->head; while (cur != NULL) { QNode* next = cur->next; free(cur); cur = next; } p->head = p->tail = NULL; } //二叉树节点创建： BNode* BuyNode(BDataType x) { BNode* node = (BNode*)malloc(sizeof(BNode)); if (node == NULL) { printf("malloc Error!\n"); return; } node->data = x; node->left = NULL; node->right = NULL; return node; } //前序遍历： void PrevOrder(BNode* root) { if (root == NULL) { printf("PrevOrder Error!\n"); return; } printf("%c ", root->data); // 访问当前节点的值 PrevOrder(root->left); // 先递归访问当前节点的左子树 PrevOrder(root->right); // 再递归访问当中前节点的右子树 } //中序遍历： void InOrder(BNode* root) { if (root == NULL) { printf("InOrder Error!\n"); return; } InOrder(root->left); // 递归访问当前节点的左树 printf("%c ", root->data); // 访问当前节点的值 InOrder(root->right); // 最后递归访问当前节点的右树 } //后序遍历： void PostOrder(BNode* root) { if (root == NULL) { printf("PostQrder Error!\n"); return; } PostOrder(root->left); // 先递归访问左子树 PostOrder(root->right); // 再递归访问右子树 printf("%c ", root->data); // 最后访问当前节点的值 } //层序遍历： void TreeLevelOrder(BNode* root) { Q q; QInit(&q);//初始化队列 if (root)//不是空树 { QPush(&q, root);//push root } while (!QEmpty(&q))//队列不为空 { BNode* front = QFront(&q);//取对头数据 QPop(&q);//这里只是pop了队列的头节点，但值被局部变量front保存下来了 //树的节点也依然存在 printf("%c ", front->data);//所以可以打印这个值 if (front->left)//不为空，入左树 { QPush(&q, front->left); } if (front->right)//不为空，入右树 { QPush(&q, front->right); } } printf("\n"); QDestroy(&q);//及时销毁 } //统计二叉树元素个数： void TreeSize(BNode* root, int* size) { if (root == NULL) { printf("TreeSize Get Error!\n"); return; } (*size)++; TreeSize(root->left, size); TreeSize(root->right, size); } //计算叶节点个数： int TreeLeafSize(BNode* root) { if (root == NULL) { printf("TreeLeafSize Get Error!\n"); return 0; } else { return (root->left) == NULL && (root->right) == NULL ? 1 : TreeLeafSize(root->left) + TreeLeafSize(root->right); } } //计算第 K 层的节点个数： int TreeKLevelSize(BNode* root, int k) { if (root == NULL) { printf("TreeKLevelSize Get Error!\n"); return 0; } if (k == 1) { return 1; } return TreeKLevelSize(root->left, k - 1) + TreeKLevelSize(root->right, k - 1); } //查找元素（节点）： BNode* TreeFind(BNode* root, BDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BNode* lret = TreeFind(root->left, x); if (lret) { return lret; } BNode* rret = TreeFind(root->right, x); if (rret) { return rret; } return NULL; } //完全二叉树判断： bool BinaryTreeComplete(BNode* root) { Q q; QInit(&q); if (root) { QPush(&q, root); } while (!QEmpty(&q)) { BNode* front = QFront(&q); QPop(&q); if (front == NULL) { break; } QPush(&q, front->left); QPush(&q, front->right); } while (!QEmpty(&q)) { BNode* front = QFront(&q); QPop(&q); if (front) { return false; } } QDestroy(&q); return true; } //二叉树销毁： void BinaryTreeDestory(BNode** pproot) { if (*pproot == NULL) { printf("BinaryTreeDestroy Error!\n"); return NULL; } BinaryTreeDestory(&(*pproot)->left); BinaryTreeDestory(&(*pproot)->right); free(*pproot); pproot = NULL; }
3.Test.c：
#define _CRT_SECURE_NO_WARNINGS 1 #include"Heap.h" BTNode* CreatBinaryTree() { BTNode* node1 = BuyNode('A'); BTNode* node2 = BuyNode('B'); BTNode* node3 = BuyNode('C'); BTNode* node4 = BuyNode('D'); BTNode* node5 = BuyNode('E'); BTNode* node6 = BuyNode('F'); node1->_left = node2; node1->_right = node3; node2->_left = node4; node3->_left = node5; node3->_right = node6; return node1; } int main() { int size=0; BTNode* root = CreatBinaryTree(); //遍厉前中后序输出二叉树节点的个数 PrevOrder(root); InOrder(root); PostOrder(root); printf("-----------------cur-----------------\n"); //优化二叉树节点的个数 printf("BinaryTreeSize:%d\n", TreeSize(root)); printf("-----------------cur-----------------\n"); //二叉树叶子节点个数 printf("BinaryTreeLeaSize:%d\n", TreeLeafSize(root)); printf("-----------------cur-----------------\n"); //二叉树第k层节点个数 printf("BinaryTreeLeveLKSize:%d\n", TreeLeveLKSize(root, 3)); printf("-----------------cur-----------------\n"); //二叉树的深度/高度 printf("BinaryTreeDepth:%d\n", BinaryTreeDepth(root)); printf("-----------------cur-----------------\n"); // 二叉树查找值为x的节点 BTNode* ret = TreeFind(root, 'D'); if(ret) { printf("找到了\n"); } else { printf("没找到\n"); } BinaryTreeDestory(root); return 0; }
3.总结：
今天我们认识并学习了二叉树链式结构的相关概念，并且对各接口功能进行了实现。到现在我们完成了二叉树的链式结构和顺序结构的学习。下一篇博客我们将完成一些二叉树基础OJ练习。希望我的文章和讲解能对大家的学习提供一些帮助。
当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~
