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

目录

概念

树的叶子节点

节点的度

分支结点

树的度

树的高度

树的深度

二叉树

二叉树的特点

满二叉树

完全二叉树

二叉查找树

示例

代码实现

开发环境

运行结果

概念

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

一种由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++树内容请搜索易知道(ezd.cc)以前的文章或继续浏览下面的相关文章希望大家以后多多支持易知道(ezd.cc)!

推荐阅读

    cad怎么设置节点|CAD怎么加节点

    cad怎么设置节点|CAD怎么加节点,,1. CAD怎么加节点天正CAD软件画节点的方法:1、在打开的软件中点击左侧工具栏中的图块图案-通用图库。2、

    js用代码实现简单购物车

    js用代码实现简单购物车,,图: 选择所有按钮: 复制代码代码如下所示: 选择 笔记本电脑:3000元 笔记本电脑:3000元 笔记本电脑:3000元 笔记本电脑:3

    海龙节点快捷键|海龙工具快捷键

    海龙节点快捷键|海龙工具快捷键,,1. 海龙工具快捷键惠普笔记本电脑的优点:1、 品牌:这年头买任何东西都要涉及这样一个问题,很多人购买东西都

    xad节点快捷键|xad复制快捷键

    xad节点快捷键|xad复制快捷键,,1. xad复制快捷键CAD中复制粘贴操作非常简单也容易理解,以下小编给大家准备了使用的图文教程及快捷键说明。

    cad添加节点快捷键|cad创建点快捷键

    cad添加节点快捷键|cad创建点快捷键,,cad创建点快捷键我用cad已经10年了,这个也很简单。在cad目录里面搜索acad.pgp.用记事本打开。在里面

    nuke移动节点快捷键|nuke快捷键大全

    nuke移动节点快捷键|nuke快捷键大全,,1. nuke快捷键大全很负责的告诉你,AE有很多快捷键,而且不好记,要多用才能记住。 打开项目 Ctrl+O   

    如何在Git中删除一个分支

    如何在Git中删除一个分支,分支,删除,命令,远程分支,合并,名称,在Git中,一个分支(branch)代表着一个独立的开发线,可以与主分支(master)进行合并(merge)

    git怎样转换分支

    git怎样转换分支,分支,命令,转换,语法,执行,作用,在git中,可利用checkout命令转换分支,该命令的作用就是切换分支或恢复工作树文件,语法为“git ch

    git怎么删除某个分支

    git怎么删除某个分支,分支,删除,远程分支,缩写,上游,命令,git删除某个分支的方法:1、利用“git branch --delete dev”命令删除本地分支;2、利用

    git如何建本地分支

    git如何建本地分支,分支,合并,命令,提交,修改,文件,Git是一款非常流行的版本控制系统,使用Git进行版本控制可以让我们更好地管理代码。而在Git中

    如何使用git删除远程分支

    如何使用git删除远程分支,远程分支,删除,命令,分支,查看,输入,在使用git进行版本控制时,我们常常需要在本地进行一些代码修改,然后将这些修改推送