文章目录 树的三种遍历方式 层序遍历 二叉树节点个数 二叉树叶子结点个数 二叉树第k层结点个数 二叉树查找值为X的结点 树的高度 前序遍历数组构建二叉树 二叉树的销毁 判断是否为完全二叉树二叉树的性质对任何一棵二叉树如果度为0的叶结点个数为n 0 n_0n0​度为2的分支结点个数为n 2 n_2n2​则有n 0 n 2 1 \boldsymbol{n_0 n_2 1}n0​n2​1有时候树并不是 完全二叉树 or 满二叉树 , 此时就不适合用数组进行存储,由此应运而生了链式结构的二叉树存储递归最重要的是 单层递归逻辑 和 递归出口以这棵二叉树为模板,自己来手搓一棵树 先定义树节点的结构体这个结构体包含3个数据 :结点本身存储的数值左孩子结点的地址右孩子结点的地址// 先定义树节点typedefintBTDataType;typedefstructBinaryTreeNode{BTDataType data;structBinaryTreeNode*left;structBinaryTreeNode*right;}BTNode; 再封装生成树节点的函数动态开辟树节点的空间,将树节点初始化后,返回开辟的树节点的地址// 手搓一个结点生成函数BTNode*BuyNode(intx){BTNode*node(BTNode*)malloc(sizeof(BTNode));if(nodeNULL){perror(malloc fail);returnNULL;}node-datax;node-leftNULL;node-rightNULL;returnnode;} 最后将各个结点按照模型连接成树先开辟出所有的结点,再将这些结点按照模型连接起来,返回头结点 ( 根 ) 的地址// 手搓一个树BTNode*CreatBinaryTree(){BTNode*node1BuyNode(1);BTNode*node2BuyNode(2);BTNode*node3BuyNode(3);BTNode*node4BuyNode(4);BTNode*node5BuyNode(5);BTNode*node6BuyNode(6);node1-leftnode2;node1-rightnode4;node2-leftnode3;node4-leftnode5;node4-rightnode6;returnnode1;} 树的遍历树的遍历本质是 与根的访问顺序有关,分为 前序 , 中序 , 后序 中序遍历递归核心思想把每一棵子树都当成独立二叉树重复遵循 左→根→右 流程先指向1,1作为根,ta的左子树不为空,所以指向ta的左子树22作为根,ta的左子树不为空,所以指向ta的左子树33作为根,ta的左子树为空,所以第一个访问的为空 ( 用 N 表示 )接着返回,指向3,3的左子树访问过了,于是访问ta自己,则有 N–3然后再指向3的右子树,3的右子树为空,所以有 N—3—N接着往回走,到2,2的左子树访问过了,于是访问ta自己 有 N—3—N—2指向2的右子树,2的右子树为空,则有 N—3—N—2—N接着往回走,到1,1的左子树访问过了,于是访问ta自己, 有 N—3—N—2—N—1然后指向1的右子树,先指向4,4作为根,ta的左子树不为空,于是指向ta的左子树55的左子树为空,于是有 N—3—N—2—N—1—N5的左子树访问完了,接着访问ta自己,有 N—3—N—2—N—1—N—5然后指向5的右子树,为空,则有 N—3—N—2—N—1—N—5—N然后往回走,指向4,4的左子树访问完了,于是访问ta自己,有 N—3—N—2—N—1—N—5—N—4然后指向4的右子树6,6作为根,ta的左子树为空 则有 N—3—N—2—N—1—N—5—N—4—N往回指向6,ta的左子树已经访问完了,于是指访问ta自己,有 N—3—N—2—N—1—N—5—N—4—N—6接着指向6的右子树,为空,则有 N—3—N—2—N—1—N—5—N—4—N—6—N故中序遍历的访问顺序为 N—3—N—2—N—1—N—5—N—4—N—6—N总结 : 一开始箭头指向谁,就把谁作为根,看看ta有没有左子树.如果有,箭头指向ta的左子树,然后再将ta作为根,看看ta有没有左子树…不断循环往复,直到箭头指向到没有左子树的根为止.然后再逆着来,按照顺序 左 根 右 来访问对应结点三种遍历方式的单层递归逻辑前序遍历 : 先打印根节点数值,然后递归访问左子树,再递归访问右子树中序遍历 : 先递归访问左子树,然后打印根节点数值,再递归访问右子树后序遍历 : 先递归访问左子树,然后递归访问右子树,再打印根节点数值⬆ 返回顶部 二叉树的前序遍历// 前序遍历voidPrevOrder(BTNode*root){if(rootNULL){printf(N );return;}// 先打印根结点坐标printf(%d ,root-data);// 递归访问左子树PrevOrder(root-left);// 递归访问右子树PrevOrder(root-right);}递归函数每一层调用执行完毕就会回到调用它的上一层继续执行剩余代码这个递归函数有两个返回出口,一个是遇到空返回上一层,一个是调用的函数语句全部执行完返回上一层 二叉树的中序遍历// 中序遍历voidInOrder(BTNode*root){if(rootNULL){printf(N );return;}// 递归访问左子树InOrder(root-left);// 再打印根结点数值printf(%d ,root-data);// 递归访问右子树InOrder(root-right);} 二叉树的后序遍历// 二叉树的后序遍历voidPostorder(BTNode*root){if(rootNULL){return;}// 先遍历左子树Postorder(root-left);// 再遍历右子树Postorder(root-right);// 打印根节点printf(%d ,root-data);} 二叉树的层序遍历 借助队列将根节点存进队列先将队头结点取出,再将这个结点的左右孩子 ( 如果存在 ) 放进队列重复过程2,直到队列为空,即完成遍历⬆ 返回顶部// 二叉树的层序遍历// 每次将队头结点弹出队列,就顺便将队头结点的孩子加入进队列voidTreeLevelOrder(BTNode*root){// 借助队列实现层序遍历Queue q;QueueInit(q);// 初始化队列if(root)// 根节点不为空,放进队列QueuePush(q,root);// 当队列不为空时while(!QueueEmpty(q)){// 存下队头地址,弹出队头BTNode*frontQueueFront(q);QueuePop(q);printf(%d ,front-data);// 当队头有左孩子时,将左孩子放进队列if(front-left)QueuePush(q,front-left);// 当队头有右孩子时,将右孩子放进队列if(front-right)QueuePush(q,front-right);}QueueDestroy(q);// 销毁队列} 求树结点个数 整棵树节点数 左子树节点数 右子树节点数 1 ( 根节点 ) 单层递归逻辑对于当前非空节点递归算出左子树一共有多少节点TreeSize(root-left)递归算出右子树一共有多少节点TreeSize(root-right)1加上当前这个根节点本身把三者相加就是以当前 root 为根的整棵树总节点数⬆ 返回顶部// 求树结点个数intTreeSize(BTNode*root){returnrootNULL?0:TreeSize(root-left)TreeSize(root-right)1;} 求叶子结点个数 整棵树叶子数 左子树叶子数 右子树叶子数 单层递归逻辑如果当前节点不是叶子有左或右子树不去管当前节点只分别统计左子树全部叶子、右子树全部叶子两者相加就是当前树的叶子总数 两个递归出口root NULL空节点返回 0没有叶子root 左右都空找到 1 个叶子返回 1⬆ 返回顶部 代码展示// 求叶子结点个数intTreeLeafSize(BTNode*root){if(rootNULL)return0;if(root-leftNULLroot-rightNULL)return1;returnTreeLeafSize(root-left)TreeLeafSize(root-right);} 求二叉树第 k 层结点个数 核心递归思想根节点的第k层 左子树的第 k-1 层 右子树的第 k-1 层 递归出口降到1层时,就只有一个结点 核心思路因为每棵树的第一层都只有一个结点,所以无论求多少层的结点个数,全部利用左右子树来降层数,降到1层再开始往回统计个数⬆ 返回顶部 代码展示// 二叉树第k层结点个数// 求root为根第k层节点总数intGetKLevelNodeNum(BTNode*root,intk){// 出口1空节点无节点if(rootNULL)return0;// 出口2k1到达目标层当前算1个if(k1)return1;// 递归左右子树求第 k-1 层相加returnGetKLevelNodeNum(root-left,k-1)GetKLevelNodeNum(root-right,k-1);} 在二叉树中查找值为 x 的结点 遍历顺序采用先序遍历当前结点 → 左子树 → 右子树 完整执行逻辑流程先判结点先判断当前结点是否为空,如果为空,直接返回空指针再判断当前结点的数值是否与查找值匹配,如果匹配,返回结点地址再判左子树递归调用查找函数,创建变量接收返回值如果返回值不为空,代表找到对应结点,直接返回这个返回值如果返回值为空…接着判右子树递归调用查找函数,创建变量接收返回值如果返回值不为空,代表找到对应结点,直接返回这个返回值如果返回值为空…整体返回空,代表这棵树没有对应的数值⬆ 返回顶部 代码展示// 在二叉树中查找值为 x 的结点BTNode*TreeFind(BTNode*root,BTDataType x){// 1.递归终止条件当前走到空结点这条分支找不到目标if(rootNULL)returnNULL;// 2.判断当前结点是不是目标结点if(root-datax)returnroot;// 找到直接返回当前结点指针// 3.优先去左子树递归查找BTNode*ret1TreeFind(root-left,x);if(ret1!NULL)// 左子树找到了目标returnret1;// 直接向上返回结果不用再搜右树// 4.左子树没找到再去右子树递归查找BTNode*ret2TreeFind(root-right,x);if(ret2!NULL)returnret2;// 5.当前结点、左子树、右子树全都没有xreturnNULL;} 求树高度 当前树高度 max ( 左子树高度右子树高度 ) 1自下而上,一层层累加上去算高度 单层处理逻辑先求出左子树高度再求右子树高度两棵子树对比选更高的一侧1 ( 1 代表当前根节点自己这一层叠加到子树高度上 ) 递归出口if(rootNULL)return0;叶子节点不会提前 return依然会递归左右左右都是 NULL 返回 0再计算max(0,0)11计算高度里所有的数值,都是由这个式子一层层累加得到的 递归流程图递归代码看不懂,就去画这个递归的流程图,自己过一遍整个递归流程,然后就能懂了⬆ 返回顶部 代码展示// 求树的深度intTreeHeight(BTNode*root){if(rootNULL)return0;intleftHeightTreeHeight(root-left);intrightHeightTreeHeight(root-right);returnleftHeightrightHeight?leftHeight1:rightHeight1;} 前序遍历数组递归构建二叉树如果觉得不理解,就结合着代码自己画图构建一遍二叉树 递归出口 : 遇到空标记,返回NULL 单层递归逻辑 : 先动态开辟根节点,对根节点赋值;再动态开辟左孩子和右孩子⬆ 返回顶部// 先定义树节点typedefstructBTNode{charval;structBTNode*left;structBTNode*right;}Node;// 递归建树Node*CreatTree(char*arr,int*p){// 递归出口if(arr[*p]#){(*p);returnNULL;}// 动态开辟结点,对其赋值Node*root(Node*)malloc(sizeof(Node));root-valarr[(*p)];// 开辟根节点的左孩子与右孩子root-leftCreatTree(arr,p);root-rightCreatTree(arr,p);returnroot;} 二叉树的销毁 后序遍历销毁二叉树把每一棵二叉树都视为 根左子树右子树 来进行销毁 递归出口 : 根为空 单层递归逻辑 : 先销毁根的左子树,再销毁根的右子树,最后free掉根⬆ 返回顶部// 二叉树销毁voidTreeDestory(BTNode*root){if(rootNULL)return;TreeDestory(root-left);TreeDestory(root-right);free(root);} 判断二叉树是否为完全二叉树完全二叉树规则从上到下、从左到右排列所有空位只能出现在最后一层最右侧一旦出现空结点后面不能再有任何有效结点 核心原理代码借助层序遍历队列实现判断分两大阶段第一阶段正常层序入队直到取出空指针初始化队列根节点非空则入队循环取出队首节点如果取出的节点 front NULL直接跳出第一层循环代表第一次碰到空位如果节点不为空强制把它的左孩子、右孩子全部入队哪怕孩子是 NULL 也要入队重点不管左右孩子存不存在都统一入队把空节点也放进队列标记空缺第二阶段校验队列剩余所有元素用一个循环不断地将队列中结点取出来 :如果队列中结点全是空结点,就是完全二叉树如果队列中出现非空结点,就不是完全二叉树⬆ 返回顶部// 判断二叉树是否是完全二叉树boolTreeComplete(BTNode*root){// 建立一个队列,将根节点放进去Queue q;QueueInit(q);if(root)QueuePush(q,root);// 第一个循环,开始不断往外取结点,再将孩子节点放进队列的过程// 直到取到第一个空停止while(!QueueEmpty(q)){BTNode*frontQueueFront(q);QueuePop(q);// 如果遇到第一个空就跳出循环对队列中剩余元素进行判断if(frontNULL){break;}// 将左右孩子放进队列QueuePush(q,front-left);QueuePush(q,front-right);}// 第二个循环,开始不断将队列中结点取出来// 如果全是空结点,就是完全二叉树// 如果出现非空结点,就是不完全二叉树while(!QueueEmpty(q)){BTNode*frontQueueFront(q);QueuePop(q);// 如果有非空就不是完全二叉树if(front){QueueDestroy(q);returnfalse;}}QueueDestroy(q);returntrue;}