#yyds干货盘点#算法给小码农链式二叉树-----一根草可斩星辰 _链式

从来好事天生俭，自古瓜儿苦后甜。这篇文章主要讲述#yyds干货盘点#算法给小码农链式二叉树-----一根草可斩星辰相关的知识，希望能为你提供帮助。
链式二叉树那么链式二叉树有什么好的地方呢我们不关注普通二叉树的增删查改，我们关注递归遍历结构
==二叉树被分成根左子树右子树==
二叉树的遍历前序、中序以及后序遍历
学习二叉树结构，最简单的方式就是遍历。所谓==二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。==访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

文章图片

按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：（上图为例图）（前中后访问根的时机不一样）

文章图片

分治
二叉树二叉树节点

//二叉树数据类型 typedef char BTDataType; //二叉树节点 typedef struct BinaryTreeNodestruct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; BTNode;

我们把上面的树建好

//创建树我们不学二叉树的增删查改原因就在这，我们想要啥树自己链一个就行，没必要增删查改 BTNode* CreatBinaryTree()BTNode* nodeA = BuyNode(A); BTNode* nodeB = BuyNode(B); BTNode* nodeC = BuyNode(C); BTNode* nodeD = BuyNode(D); BTNode* nodeE = BuyNode(E); BTNode* nodeF = BuyNode(F); nodeA-> left = nodeB; nodeA-> right = nodeC; nodeB-> left = nodeD; nodeC-> left = nodeE; nodeC-> right = nodeF; return nodeA;

二叉树前序遍历

文章图片

==这张图我实际上是想通过左右与上下滚动联合操作来截图的，然后我就找几个小时，基本能找的都找了，全网没有左右滚动截图的软件基本全是截图后窗口亮，不可以操作外面的滚动条，就算能操作也不可以左右滚动截图==

文章图片

//二叉树前序遍历 void PreOrder(BTNode* root)//不断言的原因是可以存在空树 if (!root)//空树就直接返回return; printf("%c ",root-> data); //递归左树 PreOrder(root-> left); //递归右树 PreOrder(root-> right);

二叉树中序遍历

文章图片

==我故意写成一个窗口的宽度，不然会很麻烦==

文章图片

//二叉树中序遍历 void InOrder(BTNode* root)//不断言的原因是可以存在空树 if (!root)//空树就直接返回//想打印空也可以 printf("NULL "); return; //不为空递归左树 InOrder(root-> left); //打印数据 printf("%c ",root-> data); //递归右树 InOrder(root-> right);

二叉树后序遍历

文章图片

//二叉树后序遍历 void PostOrder(BTNode* root)//不断言的原因是可以存在空树 if (!root)//空树就直接返回//想打印空也可以 printf("NULL "); return; //不为空递归左树 PostOrder(root-> left); //递归右树 PostOrder(root-> right); //打印数据 printf("%c ", root-> data);

二叉树节点个数
次数用传址的方式

文章图片

//二叉树节点个数 void BinaryTreeSize(BTNode* root,int* pn)//不断言的原因是可以存在空树 if (!root)//空树就直接返回return; (*pn)++; BinaryTreeSize(root-> left, pn); BinaryTreeSize(root-> right, pn);

次数用返回值的方式（假如我是代码我必然要嫁给这条代码）

文章图片

//二叉树节点个数 int BinaryTreeSize(BTNode* root)return root == NULL ? 0 : BinaryTreeSize(root-> left) + BinaryTreeSize(root-> right)+1;

二叉树叶子节点个数

文章图片

//二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root)if (!root)//空树返回0 return 0; if (!(root-> left) & & !(root-> right)) return 1; return BinaryTreeLeafSize(root-> left) + BinaryTreeLeafSize(root-> right);

二叉树第k层节点个数

文章图片

//二叉树第k层节点个数 int BinaryTreeLevelSize(BTNode* root, int k)if (!root) return 0; if (1 == k) return 1; //root不等于空，k也不等于1，说明root这棵树的第k层节点在子树里面 //转换成求左右子树的第k-1层节点数量 return BinaryTreeLevelSize(root-> left, k - 1) + BinaryTreeLevelSize(root-> right, k - 1);

二叉树深度/高度

文章图片

//二叉树深度/高度 int BinaryTreeDepth(BTNode* root)if (!root) return 0; //把递归的数用变量保存起来，减少资源的消耗 int leftDepth = BinaryTreeDepth(root-> left); int rightDepth = BinaryTreeDepth(root-> right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;

二叉树查找值为x的节点

文章图片

//二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x)if (!root) return NULL; if (root-> data =https://www.songbingjia.com/android/= x) return root; BTNode* leftRet = BinaryTreeFind(root-> left, x); if (leftRet) return leftRet; BTNode* rightRet = BinaryTreeFind(root-> right, x); if (rightRet) return rightRet; //上面都没进就打印空 return NULL;

二叉树层序遍历

文章图片

//二叉树层序遍历不需要用递归，用队列就可以解决 void BinaryTreeLevelOrder(BTNode* root)//空就返回 if (!root) return; //创建一个队列 Queue q; //队列初始化 QueueInit(& q); //把root放进队列 QueuePush(& q,root); //队空就跳出来 while (!QueueErase(& q))//把队头取出来放准备拿里面的data BTNode* front = QueueFront(& q); //再出队 QueuePop(& q); //打印 printf("%c ", front-> data); //带左孩子进队 if (front-> left) QueuePush(& q,front-> left); //带右孩子进队 if (front-> right) QueuePush(& q, front-> right); printf("\\n"); //和队列初始化的队列销毁 QueueDestroy(& q);

判断二叉树是否是完全二叉树BinaryTreeComplete

文章图片

// 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root)Queue q; QueueInit(& q); QueuePush(& q, root); while (!QueueErase(& q))BTNode* front = QueueFront(& q); QueuePop(& q); //出到空跳出 if (!front) break; elseQueuePush(& q, front-> left); QueuePush(& q, front-> right); //遇到空了以后，检查队列中剩下的节点 //1.剩下全是空，则是完全二叉树 //2.剩下的存在非空，则不是完全二叉树 while (!QueueErase(& q))BTNode* front = QueueFront(& q); QueuePop(& q); //出到非空就不是完全二叉树 if (front)//这里最容易忘记return之前要对销毁 QueueDestroy(& q); return false; QueueDestroy(& q); return true;

二叉树销毁BinaryTreeDestory
【#yyds干货盘点#算法给小码农链式二叉树-----一根草可斩星辰】

文章图片

//二叉树销毁 void BinaryTreeDestory(BTNode* root)if (!root) return; BinaryTreeDestory(root-> left); BinaryTreeDestory(root-> right); free(root);

代码 BinaryTree.h

#pragma once#include < stdio.h> #include < stdlib.h> #include < assert.h> #include < stdbool.h> #define CountMode 0//二叉树数据类型 typedef char BTDataType; //二叉树节点 typedef struct BinaryTreeNodestruct BinaryTreeNode* left; struct BinaryTreeNode* right; BTDataType data; BTNode; //二叉树前序遍历 extern void PreOrder(BTNode* root); //二叉树中序遍历 extern void InOrder(BTNode* root); //二叉树后序遍历 extern void PostOrder(BTNode* root); //获得节点函数 extern BTNode* BuyNode(BTDataType x); #if CountMode //二叉树节点个数 extern void BinaryTreeSize(BTNode* root, int* pn); #elif !CountMode //二叉树节点个数 extern int BinaryTreeSize(BTNode* root); #endif //二叉树叶子节点个数 extern int BinaryTreeLeafSize(BTNode* root); //二叉树第k层节点个数 extern int BinaryTreeLevelSize(BTNode* root,int k); //二叉树深度/高度 extern int BinaryTreeDepth(BTNode* root); //二叉树查找值为x的节点 extern BTNode* BinaryTreeFind(BTNode* root, BTDataType x); //二叉树层序遍历 extern void BinaryTreeLevelOrder(BTNode* root); // 判断二叉树是否是完全二叉树 extern bool BinaryTreeComplete(BTNode* root); //二叉树销毁 extern void BinaryTreeDestory(BTNode* root);

BinaryTree.c

#define _CRT_SECURE_NO_WARNINGS 1#include"BinaryTree.h" #include"Queue.h"//获得节点函数 BTNode* BuyNode(BTDataType x)//创建二叉树节点 BTNode* node = (BTNode*)malloc(sizeof(BTNode)); //检查是否成功创建 assert(node); //把数据放到节点里 node-> data = https://www.songbingjia.com/android/x; //左右子树先空树 node-> left = node-> right = NULL; return node; //二叉树前序遍历 void PreOrder(BTNode* root)//不断言的原因是可以存在空树 if (!root)//空树就直接返回//想打印空也可以 printf("NULL "); return; printf("%c ",root-> data); //递归左树 PreOrder(root-> left); //递归右树 PreOrder(root-> right); //二叉树中序遍历 void InOrder(BTNode* root)//不断言的原因是可以存在空树 if (!root)//空树就直接返回//想打印空也可以 printf("NULL "); return; //不为空递归左树 InOrder(root-> left); //打印数据 printf("%c ",root-> data); //递归右树 InOrder(root-> right); //二叉树后序遍历 void PostOrder(BTNode* root)//不断言的原因是可以存在空树 if (!root)//空树就直接返回//想打印空也可以 printf("NULL "); return; //不为空递归左树 PostOrder(root-> left); //递归右树 PostOrder(root-> right); //打印数据 printf("%c ", root-> data); #if CountMode //二叉树节点个数 void BinaryTreeSize(BTNode* root,int* pn)//不断言的原因是可以存在空树 if (!root)//空树就直接返回return; (*pn)++; BinaryTreeSize(root-> left, pn); BinaryTreeSize(root-> right, pn); #elif !CountMode //二叉树节点个数 int BinaryTreeSize(BTNode* root)return root == NULL ? 0 : BinaryTreeSize(root-> left) + BinaryTreeSize(root-> right)+1; #endif //二叉树叶子节点个数 int BinaryTreeLeafSize(BTNode* root)if (!root)//空树返回0 return 0; if (!(root-> left) & & !(root-> right)) return 1; return BinaryTreeLeafSize(root-> left) + BinaryTreeLeafSize(root-> right); //二叉树第k层节点个数 int BinaryTreeLevelSize(BTNode* root, int k)//k小于等于零直接断言因为都是从第一层开始的 assert(k > 0); if (!root) return 0; if (1 == k) return 1; //root不等于空，k也不等于1，说明root这棵树的第k层节点在子树里面 //转换成求左右子树的第k-1层节点数量 return BinaryTreeLevelSize(root-> left, k - 1) + BinaryTreeLevelSize(root-> right, k - 1); //二叉树深度/高度 int BinaryTreeDepth(BTNode* root)if (!root) return 0; //把递归的数用变量保存起来，减少资源的消耗 int leftDepth = BinaryTreeDepth(root-> left); int rightDepth = BinaryTreeDepth(root-> right); return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1; //二叉树查找值为x的节点 BTNode* BinaryTreeFind(BTNode* root, BTDataType x)if (!root) return NULL; if (root-> data =https://www.songbingjia.com/android/= x) return root; BTNode* leftRet = BinaryTreeFind(root-> left, x); if (leftRet) return leftRet; BTNode* rightRet = BinaryTreeFind(root-> right, x); if (rightRet) return rightRet; //上面都没进就打印空 return NULL; //二叉树层序遍历不需要用递归，用队列就可以解决 void BinaryTreeLevelOrder(BTNode* root)//空就返回 if (!root) return; //创建一个队列 Queue q; //队列初始化 QueueInit(& q); //把root放进队列 QueuePush(& q,root); //队空就跳出来 while (!QueueErase(& q))//把队头取出来放准备拿里面的data BTNode* front = QueueFront(& q); //再出队 QueuePop(& q); //打印 printf("%c ", front-> data); //带左孩子进队 if (front-> left) QueuePush(& q,front-> left); //带右孩子进队 if (front-> right) QueuePush(& q, front-> right); printf("\\n"); //和队列初始化的队列销毁 QueueDestroy(& q); // 判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root)Queue q; QueueInit(& q); QueuePush(& q, root); while (!QueueErase(& q))BTNode* front = QueueFront(& q); QueuePop(& q); //出到空跳出 if (!front) break; elseQueuePush(& q, front-> left); QueuePush(& q, front-> right); //遇到空了以后，检查队列中剩下的节点 //1.剩下全是空，则是完全二叉树 //2.剩下的存在非空，则不是完全二叉树 while (!QueueErase(& q))BTNode* front = QueueFront(& q); QueuePop(& q); //出到非空就不是完全二叉树 if (front)//这里最容易忘记return之前要对销毁 QueueDestroy(& q); return false; QueueDestroy(& q); return true; //二叉树销毁 void BinaryTreeDestory(BTNode* root)if (!root) return; BinaryTreeDestory(root-> left); BinaryTreeDestory(root-> right); free(root);

test.c

#define _CRT_SECURE_NO_WARNINGS 1#include"BinaryTree.h" #include"Queue.h"//创建树我们不学二叉树的增删查改原因就在这，我们想要啥树自己链一个就行，没必要增删查改 BTNode* CreatBinaryTree()BTNode* nodeA = BuyNode(A); BTNode* nodeB = BuyNode(B); BTNode* nodeC = BuyNode(C); BTNode* nodeD = BuyNode(D); BTNode* nodeE = BuyNode(E); BTNode* nodeF = BuyNode(F); nodeA-> left = nodeB; nodeA-> right = nodeC; nodeB-> left = nodeD; nodeC-> left = nodeE; nodeC-> right = nodeF; return nodeA; int main()BTNode* root = CreatBinaryTree(); //PreOrder(root); //InOrder(root); PostOrder(root); printf("\\n"); #if CountMode int n1 = 0; BinaryTreeSize(root, & n1); printf("%d ",n1); #elif !CountModeprintf("%d\\n",BinaryTreeSize(root)); #endif printf("%d\\n", BinaryTreeLeafSize(root)); printf("%d\\n", BinaryTreeLevelSize(root,3)); printf("%d\\n", BinaryTreeDepth(root)); BTNode* ret1 = BinaryTreeFind(root,C); printf("%p\\n", ret1); BTNode* ret2 = BinaryTreeFind(root, H); printf("%p\\n", ret2); BinaryTreeLevelOrder(root); printf("%d\\n", BinaryTreeComplete(root)); BinaryTreeDestory(root); root = NULL; return 0;