返回顶部
首页 > 资讯 > 后端开发 > 其他教程 >C++关于树的定义全面梳理
  • 390
分享到

C++关于树的定义全面梳理

2024-04-02 19:04:59 390人浏览 薄情痞子
摘要

目录概念树树的叶子节点节点的度分支结点树的度树的高度树的深度二叉树二叉树的特点满二叉树完全二叉树二叉查找树示例代码实现开发环境运行结果概念 本文以一个简单的树为例,如下图,来记录树的

概念

本文以一个简单的树为例,如下图,来记录树的一些概念。

一种由n个节点组成的具有一定层次关系的有限数据集合。每个节点有0个或者n个子节点,有一个根节点(没有前驱只有后继),除根节点外每一个节点都有一个前驱,0个或多个后继。

树的叶子节点

只有一个前驱,没有后继的节点,为最外层的节点。叶子节点的度为0。

节点的度

节点拥有的子树的数目。

分支结点

度不为0的结点。

树的度

树中结点的最大的度。

树的高度

任意叶子节点距离根节点的最大深度。此文中树的叶子节点为D、E、H,距离根节点的深度都为4,故高度为4。

树的深度

即从根节点到叶子节点的行数。此文中树的深度为4。

二叉树

二叉树是每个节点最多有两个子树的树结构。

它有五种基本形态:

二叉树可以是空集;

根可以有空的左子树或右子树;

或者左、右子树皆为空。

二叉树的特点

二叉树第i层上的结点数目最多为2i-1(i>=1)

深度为k的二叉树至多有2k-1个结点(k>=1)

包含n个结点的二叉树的高度至少为(log2n)+1

满二叉树

高度为h,并且由2h-1个节点组成的二叉树。

完全二叉树

一棵二叉树中,只有最下面两层节点的度可以小于2,并且最下层的叶节点集中在靠左的若干位置上,这样的二叉树称为完全二叉树。

二叉查找树

二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点,x结点包含关键字key,结点x的key值计为key[x]。如果y是x的左子树中的一个结点,则key[y]<=key[x];如果y是x的右子树的一个结点,则key[y]>=key[x]。

特点:

1.若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值。

2.任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值。

3.任意结点的左、右子树也分别为二叉查找树。

4.没有键值相等的结点。

示例

下面直接上代码,一个简单的树的创建、遍历输出,叶子节点数,高度。

代码实现

Tree.h

#pragma once
typedef struct MYTREE {
	char data;
	struct MYTREE* lChild;
	struct MYTREE* rChild;
}MyTree;
class Tree
{
public:
	Tree();
	~Tree();
	void CreateTree();
	void TraverseTree(MyTree *root);
	void GetLeafnode(MyTree *root,int &num);
	int GetTreeDepth(MyTree *root);
	void GetTreeNode(MyTree *root, int &num);
};

Tree.cpp

#include "Tree.h"
#include <iOStream>
#include<alGorithm>//max,min
using namespace std;
Tree::Tree()
{
}
Tree::~Tree()
{
}
void Tree::CreateTree()
{
	MyTree t1 = {'A',nullptr,nullptr};
	MyTree t2 = { 'B',nullptr,nullptr };
	MyTree t3 = { 'C',nullptr,nullptr };
	MyTree t4 = { 'D',nullptr,nullptr };
	MyTree t5 = { 'E',nullptr,nullptr };
	MyTree t6 = { 'F',nullptr,nullptr };
	MyTree t7 = { 'G',nullptr,nullptr };
	MyTree t8 = { 'H',nullptr,nullptr };
	t1.lChild = &t2;
	t1.rChild = &t6;
	t2.rChild = &t3;
	t3.lChild = &t4;
	t3.rChild = &t5;
	t6.rChild = &t7;
	t7.lChild = &t8;
	TraverseTree(&t1);
	cout << endl;
	int leafNum = 0;
	GetLeafNode(&t1,leafNum);
	cout << "leaf num: " << leafNum << endl;
	int treeDepth = GetTreeDepth(&t1);
	cout << "depth:" << treeDepth << endl;
	int nodeNum = 0;
	GetTreeNode(&t1,nodeNum);
	cout << "node num; " << nodeNum << endl;
}
void Tree::TraverseTree(MyTree *root)
{
	if (root == nullptr)
	{
		return;
	}
	TraverseTree(root->lChild);
	cout << root->data;
	TraverseTree(root->rChild);
}
void Tree::GetLeafNode(MyTree *root,int &num)
{
	if (root == nullptr)
	{
		return ;
	}
	if (root->lChild == nullptr && root->rChild == nullptr)
	{
		num++;
	}
	GetLeafNode(root->lChild,num);
	GetLeafNode(root->rChild,num);
}
int Tree::GetTreeDepth(MyTree * root)
{
	int num = 0;
	if (root == nullptr)
	{
		return num;
	}
	int lNum = GetTreeDepth(root->lChild);
	int rNum = GetTreeDepth(root->rChild);
	return max(lNum,rNum)+1;
}
void Tree::GetTreeNode(MyTree * root, int & num)
{
	if (root == nullptr)
	{
		return;
	}
	++num;
	GetTreeNode(root->lChild,num);
	GetTreeNode(root->rChild,num);
}

main.cpp

#include <iostream>
#include "Tree.h"
using namespace std;
void test() {
	Tree t;
	t.CreateTree();
}
int main()
{
	test();
	return 0;
}

开发环境

vs2017控制台输出程序。

运行结果

到此这篇关于c++关于树的定义全面梳理的文章就介绍到这了,更多相关C++树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

--结束END--

本文标题: C++关于树的定义全面梳理

本文链接: https://www.lsjlt.com/news/152590.html(转载时请注明来源链接)

有问题或投稿请发送至: 邮箱/279061341@qq.com    QQ/279061341

猜你喜欢
  • C++关于树的定义全面梳理
    目录概念树树的叶子节点节点的度分支结点树的度树的高度树的深度二叉树二叉树的特点满二叉树完全二叉树二叉查找树示例代码实现开发环境运行结果概念 本文以一个简单的树为例,如下图,来记录树的...
    99+
    2024-04-02
  • C语言数组全面总结梳理
    目录一,一维数组1.创建和初始化2.使用下标访问3.在内存中的存储二,二维数组 1.创建和初始化2.使用下标访问3.在内存中的存储三,越界问题数组(array)是由一系列类...
    99+
    2024-04-02
  • 关于C#线程的全面解析
    目录线程的作用和意义线程生命周期C#创建线程C#让线程休眠一会C#销毁线程C#线程优先级lock:给线程加锁,保证线程同步Monitor:锁定资源Mutex:互斥锁线程的作用和意义 ...
    99+
    2024-04-02
  • Golang中关于defer的盲区梳理
    目录defer的执行顺序是什么样的defer与return谁先谁后函数的返回值初始化与defer间接影响defer遇见panic。defer中包含panicdefer下的函数参数包含...
    99+
    2023-03-06
    Golang defer盲区 Golang defer Go defer
  • 基于自定义Toast全面解析
    Toast一般用来显示一行文字,用法比较固定:Toast.makeText(Context context,String message,int duration);...
    99+
    2023-05-30
    自定义 toast st
  • 全面梳理下CSS盒模型的相关知识点
    CSS 盒模型是 CSS 基础的重点难点,因此常被面试官们拿来考察候选人对前端基础的掌握程度,这篇文章将对 CSS 盒模型知识点进行全面的梳理。我们先看个例子:下面的 div 元素的总宽度是多少呢?<!DOCTYPE html>...
    99+
    2023-05-14
    css 前端 JavaScript 面试
  • C语言全面梳理文件操作方法
    目录1.什么是文件1.1程序文件1.2数据文件1.3文件名2.为什么使用文件3.文件的打开和关闭3.1文件指针3.2文件的打开和关闭4.文件的顺序读写什么是流5.文件的随机读写5.1...
    99+
    2024-04-02
  • C语言全面梳理结构体知识点
    目录一、什么是结构体二、结构体的定义三、结构体变量的定义四、结构体变量的初始化五、结构体变量的赋值六、引用结构体变量中的成员七、结构体变量的传参问题八、传输地址带来的问题九、动态结构...
    99+
    2024-04-02
  • C++树的定义实例分析
    这篇文章主要介绍“C++树的定义实例分析”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C++树的定义实例分析”文章能帮助大家解决问题。概念本文以一个简单的树为例,如下图,来记录树的一些概念。树一种由...
    99+
    2023-07-02
  • C语言宏定义容易认不清的盲区梳理
    目录1、概念3、宏不是函数4、宏定义不是说明或语句5、宏不是类型定义6、与之相关的宏定义7、总结1、概念 #define命令是C语言中的一个宏定义命令,它用来将一个标识符定义为一个字...
    99+
    2024-04-02
  • C语言线性表全面梳理操作方法
    线性表:零个或多个数据元素的有限序列 强调几点: 首先它是一个序列。也就是说,元素之间是有顺序的,若元素存在多个,则第一个元素无前驱,最后一个元素无后继,其他都有一个前驱和后继。其次...
    99+
    2024-04-02
  • C语言自定义类型全面系统理解
    目录一、结构体1.结构体的声明局部结构体变量全局结构体变量2.特殊声明3.结构体的自引用4.结构体变量的初始化5.结构体内存对齐 6.修改默认对齐数7.结构体传参传址调用原因:二、位...
    99+
    2024-04-02
  • C语言中关于树和二叉树的相关概念
    目录一、树树的相关概念树的存储结构二、二叉树二叉树的性质树是一种 非线性的 数据结构,由 n(n >= 0) 个 有限节点 组成一种 具有层次关系 的集合 一、树 树的结构可以...
    99+
    2023-02-14
    C语言树和二叉树的概念 C语言树和二叉树
  • C++中关于互斥量的全面认知
    目录互斥量(保护对共享变量的访问)1.概念2.状态3.特点互斥量的分配1.静态分配2.动态分配加锁和解锁互斥量1.创建互斥锁2.初始化互斥锁3.获取互斥锁4.阻塞调用5.非阻塞调用6...
    99+
    2024-04-02
  • java自定义切面增强方式(关于自定义注解aop)
    目录java自定义切面增强切面、自定义注解的使用AOP简介AOP定义注解简介元素和组成元注解总结java自定义切面增强 写代码时会遇到一些有些重复机械的工作, 这个时候就可以运用切面...
    99+
    2023-05-14
    java自定义切面增强 自定义注解aop java切面
  • Java超全面梳理内部类的使用
    目录一、内部类1.内部类的概念2.内部类的定义3.内部类与外部类的访问规则4.内部类的注意事项二、匿名内部类一、内部类 1.内部类的概念 内部类是定义在类中的类。 内部类把逻辑上相关...
    99+
    2024-04-02
  • 关于ES6中的箭头函数超详细梳理
    目录一、箭头函数的介绍1.1 什么是箭头函数1.2 基本语法1.3 箭头函数的参数1.4 箭头函数的函数体二、箭头函数的this指向规则三、箭头函数的arguments规则3.1 箭...
    99+
    2022-11-13
    es6箭头函数详解 es6箭头函数作用 es6 箭头
  • 关于springboot中对sqlSessionFactoryBean的自定义
    目录springboot sqlSessionFactoryBean自定义代码如下以上配置也可以通过properties文件配置springboot启动报找不到sqlSessionF...
    99+
    2024-04-02
  • 基于hashmap 的扩容和树形化全面分析
    一、树形化 //链表转红黑树的阈值 static final int TREEIFY_THRESHOLD = 8; //红黑树转链表的阈值 static final int UN...
    99+
    2024-04-02
  • C语言关于二叉树中堆的创建和使用整理
    目录一、堆的创建1、向上调整算法建堆2、向下调整算法建堆二、堆排序1、建堆2、利用堆删除思想来进行排序一、堆的创建 下面我们先看一段代码: void HeapSort(int* a,...
    99+
    2022-11-13
    C语言 创建堆 C语言 堆的应用
软考高级职称资格查询
编程网,编程工程师的家园,是目前国内优秀的开源技术社区之一,形成了由开源软件库、代码分享、资讯、协作翻译、讨论区和博客等几大频道内容,为IT开发者提供了一个发现、使用、并交流开源技术的平台。
  • 官方手机版

  • 微信公众号

  • 商务合作