C++实现二叉树的创建删除，dfslfs,求叶子结点个数，求叶子结点个数，求树的高度

C++实现二叉树的创建删除，dfs/lfs,求叶子结点个数，求树的高度

基本算法：

用链栈建立二叉树，通过递归实现深度优先的三种遍历，用队列实现广度优先层次遍历。借助递归思想求解叶子结点个数和树的深度。

tree.h定义基本的框架，包括结点的定义，创建树时用的栈，lfs遍历用到的队列等。

在教材上经常出现用数组实现栈，这里不妨用链表实现。

例子

A(B(D(,G)),C(E,F))
在这里插入图片描述

//tree.h
#pragma once
typedef char BTNodeDataType;
struct 	BTNode
{BTNodeDataType data;struct BTNode* lchild;struct BTNode* rchild;struct BTNode* parent;};struct TreeStackNode
{BTNode* treenode;TreeStackNode* next;
};struct BTQueueNode
{BTNode* data;BTQueueNode* next;
};struct BTQueue
{BTQueueNode* front;BTQueueNode* rear;
};TreeStackNode* InitTreeStackNode();//全局变量ts,便于多文件调用
extern TreeStackNode* ts = InitTreeStackNode();void PushStack(TreeStackNode*& root,TreeStackNode*& decendent);void DestroyStack(TreeStackNode*& s);
void PopStack(TreeStackNode*& root);BTNode* InitBTNode();
void InsertBT(BTNode*& n, BTNodeDataType d, int i);
void DispBT(BTNode*& root);string GetBTString(BTNode*& root);
BTQueueNode* InitBTQueueNode();BTQueue* InitBTQueue();
void EnQueue(BTQueue*& queue, BTNode* data);
void DeQueue(BTQueue*& queue);
BTQueueNode* GetQueueFront(BTQueue*& queue);void PreOrder(BTNode*& root);
void InOrder(BTNode*& root);
void PostOrder(BTNode*& root);int CountLeaf(BTNode* root);
int GetHeight(BTNode* root);

定义组成元素为结点的队列

//BTNodeQueue.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"tree.h"
BTQueue* InitBTQueue()
{BTQueue* queue= (BTQueue*)malloc(sizeof(BTQueue*));queue->front = NULL;queue->rear = NULL;return queue;}void EnQueue(BTQueue*& queue,BTNode* data)
{BTQueueNode* newnode;newnode =(BTQueueNode*)malloc(sizeof(BTQueueNode*));newnode->data = data;newnode->next = NULL;if (queue->front == NULL && queue->rear == NULL){queue->front = queue->rear = newnode;}else{queue->rear->next = newnode;queue->rear = queue->rear->next;}}
void DeQueue(BTQueue*& queue)
{if (queue->front == NULL){cout << "Queue is empty" << endl;return;}if (queue->front == queue->rear ){queue->front = queue->rear = NULL;return;}BTQueueNode* q = queue->front;queue->front = queue->front->next;q->data = NULL;free(q->data);q->next = NULL;free(q->next);q->next = NULL;q = NULL;}BTQueueNode* GetQueueFront(BTQueue*& queue)
{return queue->front;
}

插入结点过程：

先构建根结点，用left_value判断是否有左节点，如果有就退栈；(x,x)插入右节点前先退栈，之后新节点入栈，(,x)插入右节点，之后新节点入栈。k判断下一个要插入的是左节点还是右节点。

1是左，2是右。

画图理解：G的插入：插入G,然后G入栈、

在这里插入图片描述

C的插入，G,D,B依次退栈，然后C插入后入栈。

在这里插入图片描述

E,F插入：插入E,然后E入栈,遇到逗号，E退栈，插入F,然后F入栈

在这里插入图片描述

	//main.cppBTNode* root = InitBTNode();//树的根节点root从ts_next开始TreeStackNode* n = InitTreeStackNode();ts->next = n;ts->next->treenode = root;string s = "A(B(D(,G)),C(E,F))";char* c = &s[0]; int k = 1; //用left_value判断是否有左节点，如果有就退栈//(_,_)插入右节点先退栈，(,_)插入右节点不退栈bool left_value=false;for (int i = 0; i < s.length(); i++){if (*c == '('){left_value = false;k = 1;}else if (*c == ')'){PopStack(ts);}else if (*c == ','){if (left_value){PopStack(ts);	}k = 2;}else{InsertBT(ts->next->treenode, *c, k);left_value = true;}c++;}

链栈对应的push，pop操作

void PushStack(TreeStackNode*& root,TreeStackNode*& decendent)
{//头插法进栈,带头结点if (root->next == NULL){root->next = decendent;}else{TreeStackNode* q = root->next;root->next = decendent;decendent->next = q;}
}void PopStack(TreeStackNode*& root)
{//退栈if (root->next == NULL){cout << "Stack is Empty" << endl;return ;}else if (root->next->next == NULL){TreeStackNode* p = root->next;root->next = NULL;//这里不能随便free掉，毕竟结点已经加进去二叉树了//free(p);//p = NULL;}else{TreeStackNode* p = root->next;TreeStackNode* q = p->next;root->next = q;//free(p);//p = NULL;}
}

在二叉树中插入结点的过程，k判断下一个要插入的是左节点还是右节点。1是左，2是右。

//tree.cpp
void InsertBT(BTNode*& n, BTNodeDataType d, int i)
{TreeStackNode* newstacknode =InitTreeStackNode();if (n->data == NULL){n->data = d;newstacknode->treenode = n;}else{BTNode* new_node = InitBTNode();new_node->data = d;//new_node->parent = n;switch (i){case 1:n->lchild = new_node;break;case 2:n->rchild = new_node;break;}newstacknode->treenode = new_node;}//新插入的结点进栈PushStack(ts,newstacknode);}

从一个结点获得二叉树的字符串表示,

利用递归的思想，如果有孩子，先加左括号，然后如果有左节点，递归到左节点；如果有右节点，加逗号，递归到右节点，加括号：

void DispBT(BTNode*& root)
{if(root==nullptr) return;cout << root->data;if (root->lchild != NULL || root->rchild != NULL){cout << "(";if (root->lchild != NULL)DispBT(root->lchild);if (root->rchild != NULL){cout << ",";DispBT(root->rchild);}cout << ")";}}string GetBTString(BTNode*& root)
{static string s= "";s+= root->data;if (root->lchild != NULL || root->rchild != NULL){s += "(";if (root->lchild != NULL)GetBTString(root->lchild);if (root->rchild != NULL){s += ",";GetBTString(root->rchild);}s += ")";}return s;
}

层次遍历

如果有孩子，就加入队列；然后自己退出队列。

cout << "层次遍历：";BTQueue* queue = InitBTQueue();BTNode* p = root;EnQueue(queue, p);while (queue->front != NULL){cout << p->data;DeQueue(queue);if(p->lchild!=NULL)EnQueue(queue, p->lchild);if (p->rchild != NULL)EnQueue(queue, p->rchild);if (queue->front != NULL){p = queue->front->data;}}cout << endl;

完整代码

//tree.cpp
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"tree.h"
#include<math.h>BTNode* InitBTNode()
{BTNode* n = (BTNode*)malloc(sizeof(BTNode*));n->data = NULL;n->lchild = NULL;//n->parent = NULL;n->rchild = NULL;return n;}void InsertBT(BTNode*& n, BTNodeDataType d, int i)
{TreeStackNode* newstacknode =InitTreeStackNode();if (n->data == NULL){n->data = d;newstacknode->treenode = n;}else{BTNode* new_node = InitBTNode();new_node->data = d;//new_node->parent = n;switch (i){case 1:n->lchild = new_node;break;case 2:n->rchild = new_node;break;}newstacknode->treenode = new_node;}//新插入的结点进栈PushStack(ts,newstacknode);}void DispBT(BTNode*& root)
{if(root==nullptr) return;cout << root->data;if (root->lchild != NULL || root->rchild != NULL){cout << "(";if (root->lchild != NULL)DispBT(root->lchild);if (root->rchild != NULL){cout << ",";DispBT(root->rchild);}cout << ")";}}string GetBTString(BTNode*& root)
{static string s= "";s+= root->data;if (root->lchild != NULL || root->rchild != NULL){s += "(";if (root->lchild != NULL)GetBTString(root->lchild);if (root->rchild != NULL){s += ",";GetBTString(root->rchild);}s += ")";}return s;
}void PreOrder(BTNode*& root)
{if (root == NULL){return;}cout << root->data;PreOrder(root->lchild);PreOrder(root->rchild);}void InOrder(BTNode*& root)
{if (root == NULL){return;}InOrder(root->lchild);cout << root->data;InOrder(root->rchild);}
void PostOrder(BTNode*& root)
{if (root == NULL){return;}PostOrder(root->lchild);PostOrder(root->rchild);cout << root->data;}int CountLeaf(BTNode* root)
{if (root == NULL){return 0;}if (root->lchild == NULL && root->lchild == NULL)return 1;return CountLeaf(root->lchild) + CountLeaf(root->rchild);
}int GetHeight(BTNode* root)
{if (root == NULL){return 0;}return max(GetHeight(root->lchild), GetHeight(root->rchild)) + 1;
}TreeStackNode* InitTreeStackNode()
{TreeStackNode* s;s=(TreeStackNode*)malloc(sizeof(TreeStackNode*));s->treenode = (BTNode*)malloc(sizeof(BTNode*));s->treenode = NULL;s->next = NULL;return s;
}void PushStack(TreeStackNode*& root,TreeStackNode*& decendent)
{//头插法进栈,带头结点if (root->next == NULL){root->next = decendent;}else{TreeStackNode* q = root->next;root->next = decendent;decendent->next = q;}
}void PopStack(TreeStackNode*& root)
{//退栈if (root->next == NULL){cout << "Stack is Empty" << endl;return ;}else if (root->next->next == NULL){TreeStackNode* p = root->next;root->next = NULL;free(p);p = NULL;}else{TreeStackNode* p = root->next;TreeStackNode* q = p->next;root->next = q;free(p);p = NULL;}
}
//main.cpp文件
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
#include"tree.h"
void test1()
{BTNode* root = InitBTNode();//树的根节点root从ts_next开始TreeStackNode* n = InitTreeStackNode();ts->next = n;ts->next->treenode = root;string s = "A(B(D(,G)),C(E,F))";char* c = &s[0]; int k = 1; //用left_value判断是否有左节点，如果有就退栈//(_,_)插入右节点先退栈，(,_)插入右节点不退栈bool left_value=false;for (int i = 0; i < s.length(); i++){if (*c == '('){left_value = false;k = 1;}else if (*c == ')'){PopStack(ts);}else if (*c == ','){if (left_value){PopStack(ts);	}k = 2;}else{InsertBT(ts->next->treenode, *c, k);left_value = true;}c++;}string  BTString = GetBTString(root);cout << BTString << endl;cout << "层次遍历：";BTQueue* queue = InitBTQueue();BTNode* p = root;EnQueue(queue, p);while (queue->front != NULL){cout << p->data;DeQueue(queue);if(p->lchild!=NULL)EnQueue(queue, p->lchild);if (p->rchild != NULL)EnQueue(queue, p->rchild);if (queue->front != NULL){p = queue->front->data;}}cout << endl;//DLRcout << "DLR:";PreOrder(root);cout<<endl;//LDRcout << "LDR:";InOrder(root);cout << endl;//LRDcout << "LRD:";PostOrder(root);cout << endl;int Count =CountLeaf(root);cout << "叶子结点有" << Count << "个" << endl;int height = GetHeight(root);cout << "树的高度是：" << height << endl;
}int main()
{test1();return 0;
}

结果展示

在这里插入图片描述

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/1547596.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

TMR技术的发展及其应用技术的介绍

TMR技术的发展及其应用技术的介绍

目录 概述 1 TMR传感器介绍 1.1 原理介绍 1.2 技术演进历史 2 TMR技术的应用 2.1 电阻特性 2.2 技术比较 2.3 磁道特性 3 多维科技的芯片&#xff08;TMR1202&#xff09; 3.1 芯片介绍 3.2 特性 ​3.3 典型应用 参考文献 概述 本文主要介绍TMR技术的发展及其技术…
阅读更多...
PyTorch构建卷积神经网络（CNN）训练模型：分步指南

PyTorch构建卷积神经网络（CNN）训练模型：分步指南

《博主简介》 小伙伴们好&#xff0c;我是阿旭。专注于人工智能、AIGC、python、计算机视觉相关分享研究。 ✌更多学习资源&#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】&#xff0c;共同学习交流~ &#x1f44d;感谢小伙伴们点赞、关注&#xff01; 《------往期经典推…
阅读更多...
基于卷积神经网络的体育运动项目分类识别系统

基于卷积神经网络的体育运动项目分类识别系统

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长 QQ 名片 :) 1. 项目简介 随着计算机视觉和深度学习技术的快速发展&#xff0c;利用先进的图像处理技术对体育运动进行智能分类与识别已成为研究热点。传统的运动分析方法通常依赖于人工观察和记录&#xff0c;耗时耗力且容…
阅读更多...
Golang | Leetcode Golang题解之第440题字典序的第K小数字

Golang | Leetcode Golang题解之第440题字典序的第K小数字

题目&#xff1a; 题解&#xff1a; func getSteps(cur, n int) (steps int) {first, last : cur, curfor first < n {steps min(last, n) - first 1first * 10last last*10 9}return }func findKthNumber(n, k int) int {cur : 1k--for k > 0 {steps : getSteps(cu…
阅读更多...
基于SSM+小程序的在线课堂微信管理系统（在线课堂1）（源码+sql脚本+视频导入教程+文档）

基于SSM+小程序的在线课堂微信管理系统（在线课堂1）（源码+sql脚本+视频导入教程+文档）

&#x1f449;文末查看项目功能视频演示获取源码sql脚本视频导入教程视频 1 、功能描述 &emsp1、管理员实现了首页、个人中心、用户管理、课程分类管理、课程信息管理、课程订阅管理、课程视频管理、公告栏管理、留言板管理、系统管理。 2、用户实现了首页、课程信息、公…
阅读更多...
Windows系统下批量重命名文件的两种实现方法

Windows系统下批量重命名文件的两种实现方法

我们如果有一批文件&#xff0c;想要大批的重命名文件。例如&#xff0c;将下面的这些图片重命名为boot_itc_00001.jpg、boot_itc_00002.jpg、……、boot_itc_01000.jpg。总不能一个一个改吧&#xff1f; 第一种方法&#xff08;也是最灵活的一种&#xff09;&#xff1a; 借助…
阅读更多...
机器学习-KNN分类算法

机器学习-KNN分类算法

1.1 KNN分类 KNN分类算法&#xff08;K-Nearest-Neighbors Classification&#xff09;&#xff0c;又叫K近邻算法。它是概念极其简单&#xff0c;而效果又很优秀的分类算法。1967年由Cover T和Hart P提出。 KNN分类算法的核心思想&#xff1a;如果一个样本在特征空间中的k个最…
阅读更多...
IIs站点发布ERR_UNSAFE_PORT

IIs站点发布ERR_UNSAFE_PORT

换个端口&#xff0c;谢谢&#xff01; nice 浏览器对部分端口有特定的保护机制&#xff0c;如果你的应用使用了这些端口&#xff0c;浏览器在发送请求时会触发保护机制&#xff0c;拒绝发送请求&#xff0c;于是&#xff0c;你的服务器应用自然就收不到请求了。 1, // …
阅读更多...
树莓派基础命令

树莓派基础命令

目录 1.树莓派简介 2.树莓派使用命令 3.树莓派包管理 4.关于远程连接树莓派的思路&#xff1a; 5.总结 1.树莓派简介 树莓派&#xff08;Raspberry Pi&#xff09;是一款由英国非营利组织树莓派基金会开发的小型、低成本的单板计算机&#xff0c;最初设计目的是为了让学生…
阅读更多...
好看的首页展示

好看的首页展示

代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title><style>/* RESET…
阅读更多...
【BUG】静读天下｜静读天下无法设置段间距解决方案

【BUG】静读天下｜静读天下无法设置段间距解决方案

【BUG】静读天下&#xff5c;静读天下无法设置段间距解决方案 文章目录 【BUG】静读天下&#xff5c;静读天下无法设置段间距解决方案前言解决办法 凑质量分静读天下的特点与优势功能布局与使用技巧个人使用心得结语 前言 03-23 求助&#xff5c;关于排版的问题【静读天下吧】_…
阅读更多...
数字孪生平台，助力制造设备迈入超感知与智控新时代！

数字孪生平台，助力制造设备迈入超感知与智控新时代！

痛点剖析 当前&#xff0c;制造业面临系统分散导致的数据孤岛问题&#xff0c;严重阻碍了有效监管与统计分析&#xff1b;同时&#xff0c;设备多样化且兼容性不足&#xff0c;增加了管理难度&#xff1b;台账记录方式混乱&#xff0c;工单审批流程繁琐且效率低下&#xff1b;…
阅读更多...
Stable Diffusion零基础学习

Stable Diffusion零基础学习

Stable Diffusion学习笔记TOP11 _插件篇之ControlNet功能篇 ControlNet目前支持的10多种预处理器&#xff0c;根据数据检测种类可分为两种类型&#xff1a; 1、功能型&#xff1a;拥有着不同的能力 2、构图型&#xff1a;控制着SD扩散图形的构图规则 Shuffle洗牌/转换&#…
阅读更多...
基于Ubuntu 20.04 LTS上部署MicroK8s(最小生产的 Kubernetes)

基于Ubuntu 20.04 LTS上部署MicroK8s(最小生产的 Kubernetes)

目录 文章目录 目录简介Kubernetes简介MicroK8s简介Ubuntu系统MicroK8s的优势安装环境基本要求执行安装命令加入群组(使用非 root 用户访问)开启 dashboard 仪表盘查看服务名称查看仪表盘开放的端口打开浏览器检查状态打开你想要的服务(使用附加组件)开始使用 microk8s访问 Kub…
阅读更多...
【【通信协议之ICMP协议的FPGA实现】】

【【通信协议之ICMP协议的FPGA实现】】

通信协议之ICMP协议的FPGA实现 整体的实现框图如下所示 arp_rx.v module arp_rx#(//开发板MAC地址 00-11-22-33-44-55parameter BOARD_MAC 48h00_11_22_33_44_55, //开发板IP地址 192.168.1.10 parameter BOARD_IP {8d192,8d168,8d1,8d10} )(input …
阅读更多...
RFID手持机——物联网时代的核心工具

RFID手持机——物联网时代的核心工具

一、行业背景 在当今物联网技术高速发展的时代&#xff0c;RFID技术作为核心的数据采集与识别手段&#xff0c;在物流、仓储、资产管理等众多领域发挥着至关重要的作用。以物流行业为例&#xff0c;利用RFID技术能够对货物进行全程精准跟踪&#xff0c;从入库、存储、搬运到出…
阅读更多...
Keepalived+Nginx 高可用集群（双主模式）

Keepalived+Nginx 高可用集群（双主模式）

1.基础环境配置 [rootlb1 ~]# systemctl stop firewalld # 关闭防火墙 [rootlb1 ~]# sed -i s/^SELINUX.*/SELINUXdisabled/ /etc/sysconfig/selinux # 关闭selinux&#xff0c;重启生效 [rootlb1 ~]# setenforce 0 　　　　　　　　 …
阅读更多...
从Elasticsearch到RedisSearch：探索更快的搜索引擎解决方案

从Elasticsearch到RedisSearch：探索更快的搜索引擎解决方案

文章目录 RedisSearch 的关键功能与 ElasticSearch 对比性能对比产品对比 如何使用 Docker 安装 RedisSearch1. 获取 RedisSearch Docker 镜像2. 启动 RedisSearch 容器3. 验证安装 RedisSearch 使用示例1. 连接到 RedisSearch2. 创建索引3. 添加文档4. 执行搜索搜索所有包含 &…
阅读更多...
C++ | Leetcode C++题解之第440题字典序的第K小数字

C++ | Leetcode C++题解之第440题字典序的第K小数字

题目&#xff1a; 题解&#xff1a; class Solution { public:int getSteps(int curr, long n) {int steps 0;long first curr;long last curr;while (first < n) {steps min(last, n) - first 1;first first * 10;last last * 10 9;}return steps;}int findKthNum…
阅读更多...
Ubuntu20.04 安装汉语拼音后重启登入黑屏

Ubuntu20.04 安装汉语拼音后重启登入黑屏

在虚拟机上装了一个Ubuntu用来学C&#xff0c;默认没有安装中文输入。于是按照网上教程装了几个汉语包。切换输入法的时候突然死机&#xff0c;重启登入直接黑屏。百度后发现有不少老哥和我这个问题一模一样&#xff0c;按照他们的方法也终于整好了&#xff0c;虚惊一场。 解决…
阅读更多...
最新文章

Copyright @ 2022~2023