前言
引入二叉树——二叉树的独特之处
在学习二叉树之前，我们已经学习了从最开始的顺序表，到后面的栈和队列，再到堆，然后就到了我们现在的二叉树
我们前面学习了堆及其结构所带来的性质
堆：根据其性质（我在【数据结构】二叉树的顺序结构及实现（理论学习篇）这篇博客里详细的讲述了堆的性质，大家可通过此篇来掌握），可得到 min 或 max 值 从而解决TopK问题（此问题也在前面的链接的那篇文章中有讲述）
既然堆结构有这样的作用和意义，那么请大家思考一个问题：二叉树结构真正的意义是什么？
- 在对于数据的存储方面（数据结构的增删查改）：
在二叉树结构中插入数据，倒不如直接用顺序表实现的二叉树结构的本质-顺序表去直接存储数据来的方便 - 但在二分查找数据并删除数据 时：
- 顺序表要先排序成有序（遍历一遍数组，时间复杂度是O(N^2)），且找到想要的数据并且想要实现删插数据的功能时，顺序表的数据需要挪动，时间复杂度是O(N)
- 而链表实现的二叉树 则不用挪动数据，通过堆的性质，构建出有一定性质结构的二叉树，根据这些性质结构，通过中序遍历二叉树，可快速找出想要的数据，时间复杂度是O（N*logN）
由此可见，普通的链式二叉树没有意义
而我们现在学习普通链式二叉树，重点不在于对其数据的增删查改，而是在于通过学习二叉树的结构以及其性质为后面更复杂的 搜索二叉树（AVL，红黑树等） 打下基础。
一、二叉树的结构 的 核心思想
二叉树的结构的核心思想就是 ——" 递归 "
而 递归的本质 就在于 将一个复杂庞大的问题 逐步分解成 模式一样、最小规模 的子问题 （分治：层层分包）
递归代码逻辑运行的理解 ： 函数栈帧的创建和销毁 （建议大家先去了解一下 函数栈帧的创建和销毁的运行机制）
谨记：函数递归返回的不是最外层，而是上一层
树的结构本来就是递归结构，所以更适合用递归来实现
二、二叉树的代码实现
>binary tree.h
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdbool.h> typedef int BTDataType; typedef struct BinaryTreeNode { BTDataType val; struct BinaryTreeNode* left; struct BinaryTreeNode* right; }BTNode; // 二叉树销毁 void BinaryTreeDestory(BTNode* root); // 二叉树节点个数 int BinaryTreeSize(BTNode* root); // 二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root); // 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k); // 二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x); // 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root); // 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root); // 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root); // 层序遍历 void BinaryTreeLevelOrder(BTNode* root);
> binary tree.c
（一）手动构建二叉树 <测试用>
手动构建二叉树 —— 保存成文本文件，记录这段代码，用于下一次检测二叉树代码的正确性的样本，打造自己的 代码库。
自己画二叉树的图顺着图来链接各节点就好。
//创建树节点 BTNode* BuyNode(BTDataType x) { BTNode* node = (BTNode*)malloc(sizeof(BTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->val = x; node->left = NULL; node->right = NULL; return node; } int main() { //手动构建二叉树 —— 保存成文本文件，记录这段代码，用于下一次检测二叉树代码的正确性的样本，打造自己的代码库 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); BTNode* node8 = BuyNode(8); BTNode* node9 = BuyNode(9); node1->left = node2; node1->right = node4; node2->left = node3; node4->left = node5; node4->right = node6; node2->right = node7; node3->left = node8; node6->right = node9； }
（二）二叉树销毁
前序也可以，只是要用两个临时的指针变量去存放root->left 和 root->right 这两个节点的地址，避免释放内存后找不到下一节点的指针了
// 二叉树销毁 —— 后序递归（'递'到最深处，逐层往回'归'释放内存） //前序也可以，只是要用两个临时的指针变量去存放root->left 和 root->right 这两个节点的地址，避免释放内存后找不到下一节点的指针了 void BinaryTreeDestroy(BTNode* root) { //一级指针，形参 不影响实参 if (root == NULL) //递归返回的条件，碰到NULL就开始返回了 return; BinaryTreeDestory(root->left); BinaryTreeDestory(root->right); //'递'到最深处 free(root); //root=NULL; //思考：这里将root节点置空，有用吗 }
- 思考：这里将root节点置空，有用吗？
答：BinaryTreeDestroy用于接收的只是一级指针，接收到的只是root节点里面的内容，所以只是root的一份临时拷贝（形参） ，置空要到外面才能滞空。
（三）节点个数
- 先行版
// 节点个数 int TreeSize(BTNode* root) { int size = 0; //思考：这样 int size会出现什么问题 if (root == NULL) return 0; else ++size; TreeSize(root->left); TreeSize(root->right); return size; }
int size = 0; // 思考：这样 int size会出现什么问题
每次函数调用递归，int size都为0，无法做到记数的作用。
- static局部变量版
//节点个数 int TreeSize(BTNode* root) { static int size = 0; if (root == NULL) return 0; else ++size; TreeSize(root->left); TreeSize(root->right); return size; }
static int size=0; // 局部的静态变量的初始化 只会执行一次（只会在第一次调用时执行，后面就不会再初始化为0了）
【关于static的知识点补充，后在后续补充，到时候会把链接放这里，敬请期待】
也正是因为static有这样的特性
引出问题：下一次再想调用这个函数，会出现什么情况？
下一次再调用时，static修饰的变量并未被销毁，还存放上一次调用函数的数据，并且在作用域外也没有办法对static局部变量进行修改
解决方面如下方版本：改为 定义全局变量，在下一次调用函数之前初始化一下
- 一路记数下去版
int size=0;//定义全局变量 //节点个数 int BinaryTreeSize(BTNode* root) { if (root == NULL) return 0; else size++; BinaryTreeSize(root->left); BinaryTreeSize(root->right); return size; }
- 递归版
// 二叉树节点个数 int size=0;//定义全局变量 int BinaryTreeSize(BTNode* root) { if (root == NULL) return 0; return BinaryTreeSize(root->left) + BinaryTreeSize(root->right)+1; }
更优化的写法
int BinaryTreeSize(BTNode* root) { // 若根节点为空，空则返回0，否则返回 BinaryTreeSize(root->left) + BinaryTreeSize(root->right)+1 return root==NULL?0:BinaryTreeSize(root->left) + BinaryTreeSize(root->right)+1; }
（四）二叉树第k层节点个数
核心思想： root的第k层，相对与root->left,root->right的第k-1层。
// 二叉树第k层节点个数 int BinaryTreeLevelKSize(BTNode* root, int k) { assert(k > 0); if (root == 0) return 0; if (k == 1) //当k=1时，到第k层了 return 1; //root的第k层，相对与root->left,root->right的第k-1层 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1); }
（五） 二叉树查找值为x的节点 — 前序遍历
思路就是先遍历左子树，左子树找不到再去找右子树。
// 二叉树查找值为x的节点 前序遍历 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) //空树 递归返回的条件 return NULL; if (root->val == x) return root; BTNode* ret = NULL; //用一个指针变量来保存返回的指针 ret= BinaryTreeFind(root->left, x); if (ret) //如果ret不为空，则返回ret return ret; ret= BinaryTreeFind(root->right, x); //ret为空则继续遍历右子树 if (ret) return ret; return NULL; }
也是根据这样的思路，有的同学可能会出现这样的错误
// 二叉树查找值为x的节点 前序遍历 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) //空树 递归返回的条件 return NULL; if (root->val == x) return root; return BinaryTreeFind(root->left, x) || BinaryTreeFind(root->right, x) //如果左子树找到了，就不用再遍历右子树了 }
思考一下，这样会导致什么问题。
解析：逻辑运算符：|| 逻辑或 。确实是能做到 判断左边若为true，则结束判断。
但判断完了，其返回的是数（C语言中，判断真假，非0为真，0则为假），而不是 函数返回类型 BTNode* BinaryTreeFind (BTNode* root, BTDataType x) 中的BTNode* 。返回的就不是指针了。
【关于 逻辑或 || 运算符 的知识点补充，后在后续补充，到时候会把链接放这里，敬请期待】
(六) 二叉树前序遍历
// 二叉树前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } printf("%d", root->val); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); }
(七) 二叉树中序遍历
// 二叉树中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } BinaryTreeInOrder(root->left); printf("%d", root->val); BinaryTreeInOrder(root->right); }
(八) 二叉树后序遍历
// 二叉树后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL"); return; } BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%d", root->val); }
(九) 层序遍历—— 队列实现
队列：先进先出
- 核心思路：上一层带下一层
（需要包含Queue.h Queue.c 文件）
// 层序遍历—— 队列实现 void BinaryTreeLevelOrder(BTNode* root) { Que q; QueueInit(&q); if(root) QueuePush(&q, root); //存放头节点的地址，QNode里的data存放地址值 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); //取出用BTNode*来保存 //取头节点，读取printf头节点 printf("%d",front->val); if (front->left) //再顺带把其下一层带上 QueuePush(&q, front->left); if (front->right) QueuePush(&q,front->right); QueuePop(&q); //再排出其左节点 } printf("\n"); QueueDestroy(&q); }
- 学习完 二叉树的 前、中、后序遍历 以及 层序遍历 ，我们来介绍两个概念
深度优先遍历 和 广度优先遍历
深度优先遍历（DFS）
- 广义：前、中、后序遍历都是（都往深走，只是访问节点的时机不同）
- 严格：前序（先递归到最深处，才往回走）
广度优先遍历（BFS）
层序遍历 [ 队列配合 ] （非递归）
（十）判断二叉树是否是完全二叉树
完全二叉树：前n-1层都是满的，最后一层不满，但是连续的
非完全二叉树：非空节点不连续，中间有空节点，=> 要录空，不然看不出来
核心判断条件：层序遍历，录到空后，若后面还有节点（剩下的若不为空），则说明是非二叉树。
// 层序遍历进阶应用——判断二叉树是否是完全二叉树 int BinaryTreeComplete(BTNode* root) { Que q; QueueInit(&q); if (root != NULL) QueuePush(&q,root); while(!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); //因为传入的是BTNode的地址，从队列中取出也需要BTNode* if (front == NULL) //遇空开始判断，后面是否还有节点 break; QueuePush(&q, front->left); QueuePush(&q, front->right); QueuePop(&q); } // 已经遇到空节点，如果队列中后面的节点还有非空，就不是完全二叉树 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); //挨个判断剩下的节点是否都为空，都为空则为完全二叉树 QueuePop(&q); if (front != NULL) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }
（十一）树的高度
核心思路：对比左树和右树的高度，大的那一棵的高度+1 。
- 先行版
//树的高度 int TreeHeight(BTNode* root) { if (root == NULL) return 0; return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1; }
这样会存在什么问题，是否高效？
虽然使用的是三目运算符，使代码更简洁，但代码运行是否高效并不是看你代码简不简洁，而是要看你计算机到底要跑多久多少次。你人是爽了，但你电脑也快跑死了。
☆★存在的问题：
return TreeHeight(root->left) > TreeHeight(root->right) ? TreeHeight(root->left) + 1 : TreeHeight(root->right) + 1;
前半部分 TreeHeight(root->left) > TreeHeight(root->right) ,递归计算出 leftTreeHeight 和 rightTreeHeight 。
但由于递归计算完后，并没有变量将其递归结果进行保存 ，判断出来结果后，再进行 TreeHeight(root->left) + 1 的运算，又展开一次深度递归进行运算 。
这样进行了大量的重复计算，本来递归要进行的计算就多了，计算还要重复的。
- 改良版
根据这个问题，进行改良：将递归结果用变量进行保存 。
//树的高度 —— 优化版 int TreeHeight(BTNode* root) { if (root == NULL) return 0; int leftHeight = TreeHeight(root->left); int rightHeight = TreeHeight(root->right); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; }
- fmax 版本
int fmax(int x,int y) { if (x > y) return x; else return y; } //树的高度 —— 终版 int TreeHeight(BTNode* root) { if (root == NULL) return 0; return fmax(TreeHeight(root->left), TreeHeight(root->right)) + 1; //TreeHeight(root->left)在传过去之前就已经计算出结果，并将结果用int x（形参）接收储存。 }
运行结果
手动构建的二叉树
（十二）前序遍历 构建二叉树
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树 BTNode* BinaryTreeCreate(char* str, int* pi) { if (str[*pi]=='#') { (*pi)++; return NULL; } BTNode* root = (BTNode*)BuyNode(str[(*pi) ++]); root->left = BinaryTreeCreate(str, pi); root->right = BinaryTreeCreate(str, pi); } int main() { char a[] = "ABD##E#H##CF##G##"; int i = 0; int size = sizeof(a) / sizeof(a[0]); BinaryTreeCreate(&a,&i); }
> test.c
int main() { // 手动构建 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 = node4; node2->left = node3; node4->left = node5; node4->right = node6; PrevOrder(node1); printf("\n"); InOrder(node1); printf("\n"); PostOrder(node1); printf("\n"); printf("%d\n", TreeSize(node1)); //size = 0; printf("%d\n", TreeSize(node1)); TreeDestroy(node1); node1 = NULL; return 0; }
