这篇文章主要介绍“c++树的定义实例分析”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“C++树的定义实例分析”文章能帮助大家解决问题。概念本文以一个简单的树为例,如下图,来记录树的一些概念。树一种由
这篇文章主要介绍“c++树的定义实例分析”的相关知识,小编通过实际案例向大家展示操作过程,操作方法简单快捷,实用性强,希望这篇“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]。
特点:
若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值。
任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
任意结点的左、右子树也分别为二叉查找树。
没有键值相等的结点。
下面直接上代码,一个简单的树的创建、遍历输出,叶子节点数,高度。
Tree.h
#pragma oncetypedef 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,minusing 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++树的定义实例分析”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识,可以关注编程网其他教程频道,小编每天都会为大家更新不同的知识点。
--结束END--
本文标题: C++树的定义实例分析
本文链接: https://www.lsjlt.com/news/341964.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0