数据结构-二叉树

news/2024/11/9 4:41:35/

数据结构-二叉树

    • 二叉树的概念
    • 二叉树的遍历分类
  • 建立二叉树，并遍历
    • 二叉树的最小单元
    • 二叉树的最小单元初始化
    • 初始化二叉树
    • 前序遍历的实现
    • 中序遍历的实现
    • 后序遍历的实现
    • 计算节点的个数
    • 计算树的深度
    • 求第k层的个数
    • 查找二叉树的元素
    • 分层遍历
  • 全部代码如下

二叉树的概念

在这里插入图片描述

二叉树的遍历分类

有前序遍历，中序遍历，后序遍历和层序遍历
在这里插入图片描述

规则：

1.遇到根可以直接访问根
2.遇到左子树，右子树，不可以直接访问，要将其看作一颗新的二叉树，按遍历规则，再次循环，直至左子树或右子树为空，则可访问空。

前序遍历
在这里插入图片描述
中序遍历和后序遍历
中序遍历：
三者访问根的时机不同

层序遍历：一层一层的进行

1 2 4 3 5 6

建立二叉树，并遍历

二叉树的最小单元

根，左子树和右子树

typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;

二叉树的最小单元初始化

BTNode* BuyNode(BTDataType x)
{BTNode* node=(BTNode*)malloc(sizeof(BTNode));if (node==NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}

初始化二叉树

BTNode* CreatTree()
{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;return node1;
}

前序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：根，左子树，右子树

void PreOrder(BTNode* root)
{if (root==NULL){printf("NULL ");return;}//root,left,rightprintf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}

递归调用展开图
在这里插入图片描述

结果如下：
在这里插入图片描述

中序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：左子树，根，右子树

void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

后序遍历的实现

函数的回归条件为root为空，或者函数正常结束
按照顺序依次为：左子树，右子树，根

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}

计算节点的个数

利用分治法求节点的个数，只有节点存在时，才会+1，并返回下层的统计个数
在这里插入图片描述

int TreeSize(BTNode* root)
{if (root==NULL){return 0;}else{return TreeSize(root->left) + TreeSize(root->right)+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;
}

代码执行结果如下：
在这里插入图片描述

求第k层的个数

在这里插入图片描述

int TreeLevel(BTNode* root,int k)
{if (root==NULL){return 0;}if (k==1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}

运行结果如下:
在这里插入图片描述

查找二叉树的元素

在这里插入图片描述

BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root==NULL){return NULL;}if (root->data==x){return root;}BTNode* lret = TreeFind(root->left, x);if (lret){return lret;}BTNode* rret = TreeFind(root->right, x);if (rret){return rret;}return NULL;
}

结果如下：
在这里插入图片描述

分层遍历

利用队列，先将根push，进入循环，可pop，再将层子节点push，依次循环。安照队列先进先出的原则，可实现分层打印

void LevelOrder(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q,root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ",front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}

结果如下：

在这里插入图片描述
判断是否为完全二叉树

bool TreeComplete(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front==NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}

全部代码如下

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include "Queue.h"typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node=(BTNode*)malloc(sizeof(BTNode));if (node==NULL){perror("malloc fail");return NULL;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{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;node1->left = node2;node1->right = node3;node2->left = node4;//node4->left = node5;node3->right = node5;return node1;
}void PreOrder(BTNode* root)
{if (root==NULL){printf("NULL ");return;}//root,left,rightprintf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}void InOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}//分治法求节点的个数
int TreeSize(BTNode* root)
{if (root==NULL){return 0;}else{return TreeSize(root->left) + TreeSize(root->right)+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;
}int TreeLevel(BTNode* root,int k)
{if (root==NULL){return 0;}if (k==1){return 1;}return TreeLevel(root->left, k - 1) + TreeLevel(root->right, k - 1);
}//查找元素
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root==NULL){return NULL;}if (root->data==x){return root;}BTNode* lret = TreeFind(root->left, x);if (lret){return lret;}BTNode* rret = TreeFind(root->right, x);if (rret){return rret;}return NULL;
}//分层遍历
void LevelOrder(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q,root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);printf("%d ",front->data);if (front->left){QueuePush(&q, front->left);}if (front->right){QueuePush(&q, front->right);}}QueueDestroy(&q);
}//判断是不是完全二叉树
bool TreeComplete(BTNode* root)
{Quene q;QueueInit(&q);if (root){QueuePush(&q, root);}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front==NULL){break;}else{QueuePush(&q, front->left);QueuePush(&q, front->right);}}while (!QueueEmpty(&q)){BTNode* front = QueueFront(&q);QueuePop(&q);if (front){QueueDestroy(&q);return false;}}QueueDestroy(&q);return true;
}
int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");InOrder(root);printf("\n");PostOrder(root);printf("\n");printf("%d",TreeSize(root));printf("\n");printf("%d ", TreeHeight(root));printf("\n");printf("%d ", TreeLevel(root,3));printf("\n");printf("%p ", TreeFind(root, 5));printf("\n");printf("%p ", TreeFind(root, 60));printf("\n");LevelOrder(root);printf("TreeComplete: %d", TreeComplete(root));//二维数组return 0;
}

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include "Queue.h"void QueueInit(Quene* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}void QueueDestroy(Quene* pq)
{assert(pq);QNode* cur = pq->head;while(cur){QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}void QueuePush(Quene* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode==NULL){perror("malloc fail");return;}newnode->next = NULL;newnode->data = x;//需要判断队列中是否有元素if (pq->head==NULL){pq->head = pq->tail = newnode;}else{pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}void QueuePop(Quene* pq)
{assert(pq);//确保有队列assert(pq->head != NULL);//确保队列不为空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(Quene* pq)
{assert(pq);return pq->size;
}bool QueueEmpty(Quene* pq)
{assert(pq);return pq->size==0;
}QDataType QueueFront(Quene* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}QDataType QueueBack(Quene* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef struct BinaryTreeNode* QDataType;//单个节点
typedef struct QueneNode
{struct QueneNode* next;QDataType data;
}QNode;//整个队列
typedef struct Quene
{QNode* head;QNode* tail;int size;
}Quene;//初始化
void QueueInit(Quene* pq);
//销毁
void QueueDestroy(Quene* pq);//入队
void QueuePush(Quene* pq, QDataType x);
//出队
void QueuePop(Quene* pq);//计算队列中元素的个数
int QueueSize(Quene* pq);
//判断队列是否为空
bool QueueEmpty(Quene* pq);//队列中的队头元素
QDataType QueueFront(Quene* pq);
//队列中的队尾元素
QDataType QueueBack(Quene* pq);

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

相关文章

rancher证书过期，更新操作

rancher证书过期，更新操作

看着比其他的都靠谱&#xff0c;我这里转载一下&#xff0c;以变下次找不到了 http://t.csdn.cn/p1QLU
阅读更多...
SpringBoot中Redis报错：NOAUTH Authentication required

SpringBoot中Redis报错：NOAUTH Authentication required

1、问题 org.springframework.dao.InvalidDataAccessApiUsageException: NOAUTH Authentication required.; nested exception is redis.clients.jedis.exceptions.JedisDataException: NOAUTH Authentication required. … 2、解决 如果提供了密码还没解决&#xff0c;那可能是…
阅读更多...
前端需要注意哪些 SEO

前端需要注意哪些 SEO

前端需要注意哪些 SEO 语义化 多使用语义化标签&#xff0c;让正确的标签对应正确的内容。 重要内容前置 可以利用弹性盒布局中的 order 属性&#xff0c;将核心、重要的内容尽量放到文档的前面。 服务端渲染 由于目前的搜索引擎对客户端渲染并不友好&#xff0c;因此使用服务…
阅读更多...
涨姿势了，有意思的气泡 Loading 效果

涨姿势了，有意思的气泡 Loading 效果

今日&#xff0c;群友提问&#xff0c;如何实现这么一个 Loading 效果&#xff1a; 这个确实有点意思&#xff0c;但是这是 CSS 能够完成的&#xff1f; 没错&#xff0c;这个效果中的核心气泡效果&#xff0c;其实借助 CSS 中的滤镜&#xff0c;能够比较轻松的实现&#xff0…
阅读更多...
【nlp pytorch】基于标注信息从句子中提取命名实体内容

【nlp pytorch】基于标注信息从句子中提取命名实体内容

基于标注信息从句子中提取实体内容 1 需求2 代码实现3 代码封装1 需求 给定一个句子和已经通过模型训练标注好的信息，从而提取出句子中的实体内容，如下 输入： （1）句子信息 每个糖尿病患者,无论是病情轻重,不论是注射胰岛素,还是口服降糖药,都必须合理地控制饮食。（2）…
阅读更多...
Docker实战-操作Docker容器实战(二)

Docker实战-操作Docker容器实战(二)

导语   上篇分享中，我们介绍了关于如何创建容器、如何启动容器、如何停止容器。这篇我们来分享一下如何操作容器。 如何进入容器 可以通过使用-d参数启动容器后会进入后台运行，用户无法查看容器中的信息，无法对容器中的信息进行操作。 这个时候如果我们需要进入容器对容器…
阅读更多...
项目实战 — 消息队列（3）{数据库操作}

项目实战 — 消息队列（3）{数据库操作}

目录 一、SQLite &#x1f345; 1、添加依赖 &#x1f345; 2、修改配置文件后缀&#xff08;properties -> yaml&#xff09; &#x1f345; 3、编写配置文件 二、建立数据表 三、添加插入和删除方法 四、整合数据库操作&#xff08;DataBaseManger类&#xff09; &a…
阅读更多...
码题集oj赛（第八次）——MT2180 进制查询

码题集oj赛（第八次）——MT2180 进制查询

一、题目 二、格式 三、样例 //输入&#xff1a; 10 //输出&#xff1a; 3/1四、代码实现 #include<bits/stdc.h> using namespace std; int n, fenzi, fenmu;// 约分 /*int gcd(int a, int b) {return b 0 ? a : gcd(b, a % b); } */int gcd(int a, int b) {if (b …
阅读更多...
最新文章

Copyright @ 2022~2023