长沙 外贸网站建设公司,上海对外贸易公司,Orchard与wordpress,赣州章贡区邮政编码是多少树概念树树的叶子节点节点的度分支结点树的度树的高度树的深度二叉树二叉树的特点满二叉树完全二叉树二叉查找树示例代码实现开发环境运行结果概念
本文以一个简单的树为例#xff0c;如下图#xff0c;来记录树的一些概念。
树
一种由n个节点组成的具有一定层次关系的有…
树概念树树的叶子节点节点的度分支结点树的度树的高度树的深度二叉树二叉树的特点满二叉树完全二叉树二叉查找树示例代码实现开发环境运行结果概念
本文以一个简单的树为例如下图来记录树的一些概念。
树
一种由n个节点组成的具有一定层次关系的有限数据集合。每个节点有0个或者n个子节点有一个根节点没有前驱只有后继除根节点外每一个节点都有一个前驱0个或多个后继。
树的叶子节点
只有一个前驱没有后继的节点为最外层的节点。叶子节点的度为0。
节点的度
节点拥有的子树的数目。
分支结点
度不为0的结点。
树的度
树中结点的最大的度。
树的高度
任意叶子节点距离根节点的最大深度。此文中树的叶子节点为D、E、H距离根节点的深度都为4故高度为4。
树的深度
即从根节点到叶子节点的行数。此文中树的深度为4。
二叉树
二叉树是每个节点最多有两个子树的树结构。 它有五种基本形态 二叉树可以是空集 根可以有空的左子树或右子树 或者左、右子树皆为空。
二叉树的特点
二叉树第i层上的结点数目最多为2i-1(i1) 深度为k的二叉树至多有2k-1个结点k1 包含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 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
#includealgorithm//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控制台输出程序。
运行结果
