算法给小码农链式二叉树-----一根草可斩星辰

2024-01-04 21:59
文章标签 算法 二叉树 小码 链式 一根 星辰

本文主要是介绍算法给小码农链式二叉树-----一根草可斩星辰，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

  • 链式二叉树
        • 那么链式二叉树有什么好的地方呢
    • 二叉树的遍历
      • 前序、中序以及后序遍历
      • 按照规则，二叉树的遍历有：前序/中序/后序的递归结构遍历：（上图为例图）（前中后访问根的时机不一样）
      • 分治
    • 二叉树
      • 二叉树节点
      • 我们把上面的树建好
      • 二叉树前序遍历
      • 二叉树中序遍历
      • 二叉树后序遍历
      • 二叉树节点个数
        • 次数用传址的方式
        • 次数用返回值的方式（假如我是代码我必然要嫁给这条代码）
      • 二叉树叶子节点个数
      • 二叉树第k层节点个数
      • 二叉树深度/高度
      • 二叉树查找值为x的节点
      • 二叉树层序遍历
      • 判断二叉树是否是完全二叉树BinaryTreeComplete
      • 二叉树销毁BinaryTreeDestory
    • 代码
      • BinaryTree.h
      • BinaryTree.c
      • test.c

在这里插入图片描述

链式二叉树

我们需要明白一点，就是普通的二叉树增删查改没有什么价值，因为普通二叉树用来存数据复杂且不方便

那么链式二叉树有什么好的地方呢

==价值体现：==在他的基础之上，增加一些性质，才有意义

1.搜索二叉树 ：最多查找高度次—>时间复杂度O(N)—>单链树也就引出平衡二叉树—>AVL树和红黑树

2.Huffman 树（以后再说，反正不是现在了解的）

我们不关注普通二叉树的增删查改，我们关注递归遍历结构

1.为后面学习更有用树打基础

2.很多oj题结构普遍二叉树

二叉树被分成 根 左子树 右子树

二叉树的遍历

前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历。所谓==二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。==访问结点所做的操作依赖于具体的应用问题。遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础。

image-20211112211723351

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

image-20211112213707848

1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。根 左子树 右子树

上图前序遍历的顺序是：A B D NULL NULL NULL C E NULL NULL F NULL NULL只有把空放进去才能真正的知道思想，那些不加 空的就是耍流氓，没错说的就是你们老师，对你们耍流氓

2.中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。左子树 根 右子树

上图中序遍历的顺序是：NULL D NULL B NULL A （这时候想访问C就得访问E）NULL E NULL C NULL F NULL

3.后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。左子树 右子树 根

上图后序遍历的顺序是：NULL NULL D NULL B NULL NULL E NULL NULL F C A

分治

这里我们用的思想是分治的思想，分而治之-----大事化小，小事化了

二叉树

二叉树节点

//二叉树数据类型
typedef char BTDataType;
//二叉树节点
typedef struct BinaryTreeNode
{struct 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;
}

二叉树前序遍历

image-20211113085631295

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

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

二叉树中序遍历

image-20211113152651694

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

image-20211113171127588

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

二叉树后序遍历

image-20211113183048915

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

二叉树节点个数

次数用传址的方式

image-20211113191511501

//二叉树节点个数
void BinaryTreeSize(BTNode* root,int* pn)
{//不断言的原因是可以存在空树if (!root)//空树就直接返回{return;}(*pn)++;BinaryTreeSize(root->left, pn);BinaryTreeSize(root->right, pn);
}
次数用返回值的方式（假如我是代码我必然要嫁给这条代码）

image-20211113193430719

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

二叉树叶子节点个数

image-20211113232154579

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

二叉树第k层节点个数

image-20211114000025087

//二叉树第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);
}

二叉树深度/高度

image-20211114005007897

//二叉树深度/高度
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的节点

image-20211114013914115

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (!root)return NULL;if (root->data == 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;
}

二叉树层序遍历

image-20211117085251571

//二叉树层序遍历   不需要用递归，用队列就可以解决
void BinaryTreeLevelOrder(BTNode* root)
{//空就返回if (!root)return;//创建一个队列Queue q;//队列初始化QueueInit(&q);//把root放进队列QueuePush(&q,root);//队空就跳出来while (!QueueErase(&q)){//把队头取出来放准备拿里面的dataBTNode* 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

image-20211118000032718

// 判断二叉树是否是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);while (!QueueErase(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);//出到空跳出if (!front)break;else{QueuePush(&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

image-20211120002929144

//二叉树销毁
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 BinaryTreeNode
{struct 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 = 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)//空树返回0return 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 == 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)){//把队头取出来放准备拿里面的dataBTNode* 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;else{QueuePush(&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 CountModeint n1 = 0;BinaryTreeSize(root, &n1);printf("%d ",n1);
#elif !CountModeprintf("%d\n",BinaryTreeSize(root));
#endifprintf("%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;
}

这篇关于算法给小码农链式二叉树-----一根草可斩星辰的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/570729。

相关文章

Python中的随机森林算法与实战

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例：使用随机森林预测鸢尾花品种4.1
阅读更多...
不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
秋招最新大模型算法面试，熬夜都要肝完它

秋招最新大模型算法面试，熬夜都要肝完它

💥大家在面试大模型LLM这个板块的时候，不知道面试完会不会复盘、总结，做笔记的习惯，这份大模型算法岗面试八股笔记也帮助不少人拿到过offer ✨对于面试大模型算法工程师会有一定的帮助，都附有完整答案，熬夜也要看完，祝大家一臂之力 这份《大模型算法工程师面试题》已经上传CSDN，还有完整版的大模型 AI 学习资料，朋友们如果需要可以微信扫描下方CSDN官方认证二维码免费领取【保证100%免费
阅读更多...
dp算法练习题【8】

dp算法练习题【8】

不同二叉搜索树 96. 不同的二叉搜索树 给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。 示例 1： 输入：n = 3输出：5 示例 2： 输入：n = 1输出：1 class Solution {public int numTrees(int n) {int[] dp = new int
阅读更多...
Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数，每次操作将其分成2^q份，对于每一份内部的数进行翻转(逆序)，每次操作完后输出操作后新序列的逆序对数。 图一：  划分子问题。 图二： 分而治之，=>  合并 。 图三： 回溯：
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2