这是一颗经过计划生育的树?

news/2024/11/24 9:11:51/

在这里插入图片描述

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:数据结构中有关"二叉树"的知识,用c语言实现,根据前序遍历构建二叉树,前序遍历,中序遍历,后续遍历,以及层序遍历(有点麻烦)等遍历方式.
金句分享:
✨没人爱时专注自己,有人爱时,有能力拥抱彼此!✨

前言

前面,我们在"树的概念"一文中已经介绍过了二叉树的基本概念,二叉树较于线性表(顺序表和链表等),难度有一定提升,主要是要熟练掌握递归,很多有关"二叉树"的操作都需要使用递归算法.

目录

  • 前言
  • 一、"二叉树"的类型声明
  • 二、"二叉树"的遍历
    • 3.1 前序遍历:
    • 3.2 中序遍历:
    • 3.3 后序遍历:
    • 3.4 扩展知识:层序遍历(稍复杂)
  • 三、"二叉树"的构造(根据前序遍历)
  • 四、"二叉树"的销毁
  • 五、总代码:
    • 声明区(tree.h)
    • 队列接口实现区:(Queue.c)
    • "二叉树"接口实现区:(tree.c)
    • 主测试区:(test.c)

一、"二叉树"的类型声明

typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;//数据域//指针域struct BinaryTreeNode* left;//左子树struct BinaryTreeNode* right;//右子树
}BTNode;

二、"二叉树"的遍历

学习二叉树的结构时，最简单的操作是遍历二叉树,所以我们先介绍如何遍历一课二叉树.

二叉树遍历(Traversal):

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

通俗来讲,就是访问一遍二叉树的所有结点.

对于任意一棵二叉树,他都有由根,左子树,右子树组成.
那么就出现了三种常见的遍历二叉树的方式

  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。即:
根 ---> 左(子树) ---> 右(子树)
  1. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。即:
左(子树) ---> 根 ---> 右(右子树)
  1. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。即:
左(子树) ---> 右(子树) ---> 根

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历.

总结:

在 根 左子树 右子树三个中:

前序遍历:根节点第一个被访问.
中序遍历:根节点第中间(二个)个被访问.
后序遍历:根节点最后一个被访问.

3.1 前序遍历:

看见前序遍历,就知道根节点是第一个被访问的.即:

根 —> 左(子树) —> 右(子树)

代码递归展开图:
在这里插入图片描述

代码实现:

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL)//访问到根节点如果是NULL,则打印NULL{printf("NULL ");return;}//先访问根节点printf("%c ", root->data);//再递归访问左右子树BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}

3.2 中序遍历:

有了前序遍历的基础,后面两个应该好理解,如果还是不理解,可以试着画一下代码的递归展开图,帮助大家理解.

// 二叉树中序遍历 
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//先访问左子树BinaryTreePrevOrder(root->left);//中间访问根节点printf("%c ", root->data);//最后访问右子树BinaryTreePrevOrder(root->right);
}

3.3 后序遍历:

// 二叉树后序遍历 
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}//先访问左右子树BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);//最后访问根节点printf("%c ", root->data);
}

3.4 扩展知识:层序遍历(稍复杂)

要去按层来访问二叉树.

这里需要借助队列来实现,而且恶心的是, C语言没有队列的库函数,需要自己实现.
牛牛有关队列的博客,欢迎直接复制.
传送门

代码实现:
打印NULL版本

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);//将二叉树的根节点先入队列while (!QueueEmpty(&q))//只要队列非空则,继续{BTNode* tmp=QueueFront(&q);if (tmp)//非空结点则直接打印数据{printf("%c ", tmp->data);}else{printf("NULL ");}QueuePop(&q);//弹出根节点.将左右子树分别压入队列if (tmp)//只要该结点不是NULL,则将其左右子树都入队{//结点虽然非空,但是左右子树可能是NULL,所以这里NULL也进入队列了.QueuePush(&q, tmp->left);QueuePush(&q, tmp->right);}}
}

不打印NULL版本

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root) 
{Queue q1;QueueInit(&q1);QueuePush(&q1, root);//将根节点存入队列while (!QueueEmpty(&q1)){BTNode* front = QueueFront(&q1);//保存队首结点printf("%c ",front->data );//打印队首数据QueuePop(&q1);//弹出根节点//将刚刚弹出的结点的左右孩子入队列(所以前面要保存头结点)if (front->left)QueuePush(&q1, front->left);if(front->right)QueuePush(&q1,front->right);}
}

三、"二叉树"的构造(根据前序遍历)

前面都是在已经有二叉树的基础上,我们直接遍历二叉树,那二叉树怎么构建呢?

现在,我们给出要构建的二叉树的前序遍历.(#代表NULL)

BTDataType arr[50] = { "ABD##E##CF##G##" };

代码实现:

BTNode* BinaryTreeCreate(BTDataType* a,int* pi)//pi用于遍历这个数组
{//递归的结束条件是,当left和right都是NULL时,(左右子树都为空,则结束递归)if (a[*pi] == '#')//遇到NULL{//注意,即使是遇到NULL,数组也需要继续往后遍历,不然还没有构建完成(*pi)++;return NULL;}//如果不是NULLBTNode* root = (BTNode*)malloc(sizeof(BTNode));//创建树结点//先赋值根节点root->data = a[(*pi)++];//再给左右子树赋值root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a,pi);return root;
}

四、"二叉树"的销毁

二叉树的销毁步骤:

  1. 递归访问左右子树,直到遇到NULl.访问到了最后一层.
  2. 开始释放该结点(从叶子结点开始),回退.

在这里插入图片描述

//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL)//如果走到NULL则直接返回{return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);//这条语句一定要放在前面两条语句的后面,不然无法递归往下走.
}

五、总代码:

声明区(tree.h)

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>typedef char BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;//根据前序遍历构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a,int* pi);// 二叉树销毁
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);//队列
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>typedef BTNode* QDatatype;typedef struct QueueNode
{struct QueueNode* next;QDatatype data;
}QNode;typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDatatype x);
void QueuePop(Queue* pq);
int QueueSize(Queue* pq);
bool QueueEmpty(Queue* pq);
QDatatype QueueFront(Queue* pq);
QDatatype QueueBack(Queue* pq);

队列接口实现区:(Queue.c)

#include "tree.h"
void QueueInit(Queue* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->head;QNode* next = cur;while (next){next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Queue* pq, QDatatype x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));newnode->data = x;newnode->next = NULL;if (newnode == NULL){perror("newnode malloc fail:");return;}//这里忘记了判断head刚开始时if (pq->head == NULL)//第一次插入{assert(pq->tail == NULL);pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;//记住这个放后面
}
bool QueueEmpty(Queue* pq)
{assert(pq);if (pq->head == pq->tail && pq->head == NULL){return true;}return false;
}
void QueuePop(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));if (pq->head->next == NULL)//代表还剩下一个结点{free(pq->head);//释放这个结点.pq->head = pq->tail = NULL;}else{QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
QDatatype QueueFront(Queue* pq)
{assert(pq);assert(pq->head);return pq->head->data;
}QDatatype QueueBack(Queue* pq)
{assert(pq);assert(pq->head);return pq->tail->data;
}

"二叉树"接口实现区:(tree.c)

#include "tree.h"BTNode* BinaryTreeCreate(BTDataType* a,int* pi)//pi用于遍历这个数组
{//递归的结束条件是,当left和right都是NULL时if (a[*pi] == '#')//遇到NULL{(*pi)++;return NULL;}//如果不是NULLBTNode* root = (BTNode*)malloc(sizeof(BTNode));//创建树结点root->data = a[(*pi)++];root->left = BinaryTreeCreate(a, pi);root->right = BinaryTreeCreate(a,pi);return root;
}//二叉树的销毁
void BinaryTreeDestory(BTNode* root)
{if (root == NULL)//如果走到NULL则直接返回{return;}BinaryTreeDestory(root->left);BinaryTreeDestory(root->right);free(root);//这条语句一定要放在前面两条语句的后面,不然无法递归往下走.
}// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}printf("%c ", root->data);BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);
}// 二叉树中序遍历 
void BinaryTreeInOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}BinaryTreePrevOrder(root->left);printf("%c ", root->data);BinaryTreePrevOrder(root->right);
}// 二叉树后序遍历 
void BinaryTreePostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}BinaryTreePrevOrder(root->left);BinaryTreePrevOrder(root->right);printf("%c ", root->data);
}// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue q;QueueInit(&q);QueuePush(&q, root);//将二叉树的根节点先入队列while (!QueueEmpty(&q))//只要队列非空则,继续{BTNode* tmp=QueueFront(&q);if (tmp){printf("%c ", tmp->data);}else{printf("NULL ");}QueuePop(&q);//弹出根节点.将左右子树分别压入队列if (tmp){QueuePush(&q, tmp->left);QueuePush(&q, tmp->right);}}
}

主测试区:(test.c)

#include "tree.h"int main()
{BTDataType arr[50] = { "ABD##E##CF##G##" };int i = 0;BTNode* root = BinaryTreeCreate(arr,&i);//前序遍历printf("前序遍历:");BinaryTreePrevOrder(root);printf("\n");// 二叉树中序遍历 printf("中序遍历:");BinaryTreeInOrder(root);printf("\n");// 二叉树后序遍历 printf("后序遍历:");BinaryTreePostOrder(root);printf("\n");//层序遍历printf("二叉树的层序遍历:");BinaryTreeLevelOrder(root);printf("\n");//二叉树的销毁BinaryTreeDestory(root);return 0;
}

http://www.ppmy.cn/news/448209.html

相关文章

系统架构师-UML相关图

系统架构师-UML相关图

原文合集地址如下&#xff0c;有需要的朋友可以关注 本文地址 合集地址 基本概念 在UML&#xff08;统一建模语言&#xff09;中&#xff0c;常见的九种图包括&#xff1a; 类图&#xff08;Class Diagram&#xff09;&#xff1a;展示系统中的类、接口、关系和属性等静态结…
阅读更多...
Unity删除一个GameObject下的所有子项

Unity删除一个GameObject下的所有子项

结构&#xff1a; Root |---- Child A |---- Child B |---- Child C 需求&#xff1a; 在代码中让Unity删除一个GameObject下的所有子项 思路&#xff1a; Unity中不能对GameObject对象使用GetComponent 所以可以用Transform来代替 解决&#xff1a; Transform[] childs…
阅读更多...
3Dmax已经贴好图的文件如何导入unity3D中

3Dmax已经贴好图的文件如何导入unity3D中

3Dmax已经贴好图的文件如何导入unity3D中&#xff0c;对于初学者而言&#xff0c;有时候在3Dmax中贴好图&#xff0c;配好颜色的模型导入unity3D中会丢失贴图的问题。 解决方法&#xff1a; 1.在3Dmax中建好模型、贴图完成。 2.点击在左上角&#xff1a;文件-导出-导出 3.选择…
阅读更多...
如何清除计算机上游戏记录,如何删除玩游戏后电脑记录

如何清除计算机上游戏记录,如何删除玩游戏后电脑记录

查电脑运行记录&#xff1a;1)C:\DocumentsandSettings\用户名\Cookies---看里面的内容.然后在上方的工具栏中找到”工具”&#xff0d;&#xff0d;&#xff0d;文件夹选项&#xff0d;&#xff0d;&#xff0d;查看&#xff0d;&#xff0d;&#xff0d;在高级设置里面找到”…
阅读更多...
计算机自带游戏如何删除,详细教你系统怎么删除游戏

计算机自带游戏如何删除,详细教你系统怎么删除游戏

很多时候&#xff0c;在我们安装系统就会自带一些游戏软件&#xff0c;但是我们不怎么感兴趣&#xff0c;放在那里有占用内存&#xff0c;只有将它们删除了&#xff0c;如何彻底删除windows系统自带的游戏蜘蛛纸牌呢&#xff1f;下面&#xff0c;就有系统之家小编来给大家讲解系…
阅读更多...
3dmax2019删除不想要的模型部分

3dmax2019删除不想要的模型部分

3dmax2019删除不想要的模型部分 3dmax2019删除不想要的模型部分 打开3dmax,导入模型。 这里导入的是fbx格式的模型文件。 删除多余模型部分 选中模型&#xff0c;右键选择–转换为可编辑多边型。在右侧一栏中选择—面---&#xff0c;点击下方的-----分离----。 按住鼠标左键…
阅读更多...
3dmax如何删除多余的时间帧

3dmax如何删除多余的时间帧

3dmax如何删除多余的时间帧 3dmax如何删除多余的时间帧?在3dmax的使用中&#xff0c;帧数使用的比较少&#xff0c;那么如何去掉时间轴上的帧数呢?这篇文章将教你在时间轴上删除帧单位的方法和步骤。我们来看看! 3dmax如何删除多余的时间帧? 第一步:打开3dmax软件中的时间配…
阅读更多...
【Unity】Destroy方法不是立即删除

【Unity】Destroy方法不是立即删除

问题描述 在做任务列表时&#xff0c;发现任务的排序位置并不正常&#xff0c;有些地方会很空 原因分析&#xff1a; 开始以为是自己设置位置出现了问题&#xff0c;后来一步步看设置位置的代码&#xff0c;发现是使用了NGUI的UITabel组件的Reposition进行的位置排列。于是便…
阅读更多...
最新文章

Copyright @ 2022~2023