<你想看的我这里都有😎 >
二叉树的创建
#include <stdio.h> #include <assert.h> #include <stdlib.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }TreeNode; TreeNode* BuyTreeNode(int x) { TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); assert(node); node->data = x; node->left = NULL; node->right = NULL; return node; } TreeNode* CreatTree() { TreeNode* node1 = BuyTreeNode(1); TreeNode* node2 = BuyTreeNode(2); TreeNode* node3 = BuyTreeNode(3); TreeNode* node4 = BuyTreeNode(4); TreeNode* node5 = BuyTreeNode(5); TreeNode* node6 = BuyTreeNode(6); node1->left = node2; node1->right = node4; node2->left = node3; //node2->right = NULL; //node3->left = NULL; //node3->right = NULL; node4->left = node5; node4->right = node6; //node5->left = NULL; //node5->right = NULL; //node6->left = NULL; //node6->right= NULL; return node1; } int main() { TreeNode* root = CreatTree(); return 0; }
二叉树的销毁
//二叉树的销毁 void DestoryTree(TreeNode* root) { //当结点为空时，开始返回 if (root == NULL) return; //销毁左子树 DestoryTree(root->left); //销毁右子树 DestoryTree(root->right); //释放当前结点 free(root); }
层序遍历
概念：层序遍历即从二叉树根节点出发，自上而下，自左至右逐层访问树的结点
注意事项：在进行二叉树的层序遍历过程中我们要使用队列的性质
关于队列的文章：队列的实现和OJ练习（c语言）
解释：借助队列先进先出的特点，先将根结点入队，然后获取此时的队头结点并将队头结点出队最后打印队头结点打印，将当前节点的左右非空的孩子入队。然后获取此时的队头结点并将队头结点出队最后打印队头结点打印，直到队列为空为止
队列的头文件
注意事项：因为我们要在队列中存放的是二叉树的结点而非结点中的值，所以原来队列实现中的typedef int QDataType需要改变为typedef struct BinaryTreeNode* QDataType，必须要写为struct BinaryTreeNode*而不是TreeNode*，这是因为typedef是预处理命令，我们将二叉树的结构体重命名命名为TreeNode的编译器在执行typedef TreeNode* QDataType时检测不到（后面讲述队头的时候会用到）
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> //链式结构：表示队列 typedef struct BinaryTreeNode* QDataType; typedef struct QueueNode { QDataType val; struct QueueNode* next; }QNode; //队列的结构（使用结构体避免了二级指针的使用） typedef struct Queue { QNode* phead; QNode* ptail; int size; }Queue; //初始化队列 void QueueInit(Queue* pq); //队尾入队列 void QueueDestroy(Queue* pq); //队头出队列 void QueuePush(Queue* pq, QDataType x); //获取队头元素 void QueuePop(Queue* pq); //获取队尾元素 QDataType QueueFront(Queue* pq); //获取队列中有效元素个数 QDataType QueueBack(Queue* pq); //检测队列是否为空 bool QueueEmpty(Queue* pq); //销毁队列 int QueueSize(Queue* pq);
队列的函数实现
#include"Queue.h" //初始化队列 void QueueInit(Queue* pq) { assert(pq); pq->phead = pq->ptail = NULL; pq->size = 0; } //销毁队列 void QueueDestroy(Queue* pq) { assert(pq); QNode* cur = pq->phead; while (cur) { QNode* next = cur->next; free(cur); cur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; } //队尾入队列 void QueuePush(Queue* pq, QDataType x) { assert(pq); QNode* newnode = (QNode*)malloc(sizeof(QNode)); if (newnode == NULL) { perror("malloc fail"); return; } newnode->val = x; newnode->next = NULL; if (pq->ptail == NULL) { pq->ptail = pq->phead = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } // 对头出队列 void QueuePop(Queue* pq) { assert(pq); // assert(pq->phead); QNode* del = pq->phead; pq->phead = pq->phead->next; free(del); del = NULL; if (pq->phead == NULL) pq->ptail = NULL; pq->size--; } //获取队头元素 QDataType QueueFront(Queue* pq) { assert(pq); // assert(pq->phead); return pq->phead->val; } //获取队尾元素 QDataType QueueBack(Queue* pq) { assert(pq); // assert(pq->ptail); return pq->ptail->val; } //检测队列是否为空 bool QueueEmpty(Queue* pq) { assert(pq); return pq->phead == NULL; } //获取队列中有效元素个数 int QueueSize(Queue* pq) { assert(pq); return pq->size; }
层序遍历的实现
//二叉树的层序遍历 void LevelOrder(TreeNode* root) { //创建队列 Queue q; //初始化队列 QueueInit(&q); //如果当前结点不为空，就将当前结点入队 if (root) QueuePush(&q, root); //只要队列不为空，就打印入队 while (!QueueEmpty(&q)) { //获取队头结点 TreeNode* 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"); //最后销毁队列 QueueDestroy(&q); }
画图解释部分过程：
由于是先让当前结点的左孩子入队，然后再让当前结点的右孩子入队，当结点2作为队头的时候，它的左孩子和右孩子肯定会比结点4的左孩子和右孩子入队，当结点2出队，结点4变为队头时，结点4的左右孩子才会入队，这样刚好就可以满足我们层序遍历的需求了
关于"QueuePop(&q)后front为什么还能使用"的解释：front是TreeNode*类型，QueuePop释放掉的是QNode*类型的del，删除后者对前者无影响，此外QueueFront获取队头元素的类型为：BinaryTreeNode*，虽然队列返回的是pq->phead->val，但是val里面存放的其实是结点的地址，整个过程就相当于front把val中的内容拷贝了一份，然后删除了val而已：
层序遍历的进阶
//二叉树的层序遍历 void LevelOrder(TreeNode* root) { //创建队列 Queue q; //初始化队列 QueueInit(&q); //如果当前结点不为空，就将当前结点入队 if (root) QueuePush(&q, root); //初始化levelsize int levelsize = 1; //只要队列不为空，就打印入队 while (!QueueEmpty(&q)) { while(levelsize--) { //获取队头结点 TreeNode* front = QueueFront(&q); //将删除队头结点 QueuePop(&q); //打印队头结点的值 printf("%d ", front->data); //如果当前结点的左孩子不为空，则将左孩子结点入队 if (front->left) QueuePush(&q, front->left); //如果当前结点的右孩子不为空，则将右孩子结点入队 if (front->right) QueuePush(&q, front->right); } //获取此时队列中的元素个数 levelsize = QueueSize(&q); } printf("\n"); //最后销毁队列 QueueDestroy(&q); }
我们引入了一个变量 levelsize 来记录每一层的节点数量。这个变量在内部循环中被初始化为 1，并且每次循环结束后更新为当前队列的大小（即下一层节点的数量）。这样做的目的是确保内部循环只处理当前层级上已经入队但尚未处理完毕的节点。
结论：前者和后者的代码效果相同，但从理解代码逻辑和算法执行过程的角度来看，使用 levelsize 变量可以提供更好的可读性和可理解性。
判断二叉树是否是完全二叉树
// 判断二叉树是否是完全二叉树 bool TreeComplete(TreeNode* root) { Queue q; QueueInit(&q); if (root) QueuePush(&q, root); int levelSize = 1; while (!QueueEmpty(&q)) { TreeNode* front = QueueFront(&q); QueuePop(&q); if (front == NULL) break; QueuePush(&q, front->left); QueuePush(&q, front->right); } // 前面遇到空以后，后面还有非空就不是完全二叉树 while (!QueueEmpty(&q)) { TreeNode* front = QueueFront(&q); QueuePop(&q); if (front) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
解释：不再解释
~over~
