小学生课程同步做网站软件,企业为什么选择上市,国外服务器地址ip,wordpress点赞出现空白页一、树的概念
树是一种分组的层次结构。
树的定义#xff1a;
树是n(n0)个数据元素的集合,在任意一棵非空树中#xff0c;有如下特征
有且只有一个根结点#xff08;无前驱结点#xff09;当n1时#xff0c;其他结点被分为若干个互不相交集合#xff0c;并且…一、树的概念
树是一种分组的层次结构。
树的定义
树是n(n0)个数据元素的集合,在任意一棵非空树中有如下特征
有且只有一个根结点无前驱结点当n1时其他结点被分为若干个互不相交集合并且每个集合又是一棵树
我们可以看到树的定义引用了集合的概念和迭代的概念。
二、树的表示方法
文氏图圆括号凹入法树形图
三、基本术语
结点树的结点包含一个数据元素和若干指向其他子树的分支结点的度结点的子节点的个数树的度树的所有结点的度的最大值叶子结点结点的度为0的结点分支结点结点的度不为0的结点兄弟结点同一个父结点下的子节点称为兄弟结点层数根节点的层数为1其他结点的层数为父节点的层数加1树的深度所有结点层数的最大值森林零棵或者有限棵互不相交的树称为森林有序树和无序数结点的各子节点从左到右无序可以互换的树称之为无序树否则称为有序树
四、二叉树
1、二叉树的定义
一种特殊的树除了有树的特征外还有如下特征
当结点数大于0时该树由根节点和两个子树组成分别称之为左子树和右子树左子树和右子树又是二叉树
2、二叉树的基本操作
CreateTree创建一棵二叉树ShowTree用凹入法或者圆括号法显示一棵二叉树PreOrder按照先序根左右遍历一棵二叉树上的所有结点InOrder按照中序左根右遍历一棵二叉树上的所有结点PostOrder按照后序左右根遍历一棵二叉树上的所有结点LevelOrder按层次遍历一棵二叉树上的所有结点Leafnum求一棵二叉树上的所有叶子结点TreeDepth求一棵二叉树的深度
3、二叉树的性质
一棵二叉树的第i层至多有2分之i-1个结点深度为h的一棵二叉树至多有2分之h-1个结点对于一棵有n个结点的完全二叉树若按照满二叉树的方式对结点进行编号对于任意编号为i的结点有如下性质
i等于1的结点为根结点当i1时该结点的父节点编号为i/2当2in时该结点的左子结点编号为2i当2in时,该结点没有左子节点当2i1n时该结点的右子节点编号为2i1当2i1n时该结点没有右子节点
具有nn0个结点的完全二叉树其深度为floorlog2n1,floor表示向下取整对于一棵非空的二叉树设结点的度为0,1,2的结点的个数分别为n0,n1,n2那么有n0n21
