数据结构中树与二叉树的区别在于?
二叉树是指一个树的父节点最多只有两个子节点构成的树,树是不限制子节点的个数的。
二叉树是树的一种特例,是树的子集。
三个节点是无法表示出二叉树和树的区别的,需要三个以上的节点。
二叉树的表示如下图。
树的表示如下图。
扩展资料:
树图是一种数据结构,由n (n>=1)个有限节点组成具有层次关系的集合。它被称为树是因为它看起来像一棵倒立的树,意思是它的根是向上的,叶子是向下的。它具有以下特点:
每个节点有零个或多个子节点;没有父节点的节点称为根节点;每个非根节点都有且只有一个父节点;除了根之外,每个子树还可以分为多个不相交的子树。
相关术语
节点的度:节点中包含的子树数称为节点的度;
叶节点或终端节点:度为0的节点称为叶节点;
非终端节点或分支节点:度不为0的节点;
父节点或父节点:如果一个节点包含子节点,该节点称为子节点的父节点;
子节点或子节点:一个节点包含的子树的根节点称为该节点的子节点;
同级节点:具有相同父节点的节点称为同级节点。
树度:在树中,最大节点的度称为树的度;
节点层次结构:从根开始,根是第一层,根的子节点是第二层,依此类推。
树的高度或深度:树中节点的最大级别;
表亲节点:父节点在同一层的节点是彼此的表亲;
节点的祖先:从根节点到该节点所经过的分支的所有节点;
子代:根于某一节点的子树中的任何节点称为该节点的子代。
森林:以m (m>=0)相交的树的集合称为森林;
参考资料:百度百科-树(数据结构)
2024-11-30 广告
推荐于2018-02-22
一个二叉树就是每个节点只能最多拥有2个子节点的树结构,这些子节点一般被视为左子节点和右子节点。
2013-08-26
推荐于2016-02-19
在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点,简称树的根。每一个结点可以有多个后件,称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件的个数称为该结点的度,所有结点中最大的度称为树的度。树的最大层次称为树的深度。
二叉树的特点:(1)非空二叉树只有一个根结点;(2)每一个结点最多有两棵子树,且分别称为该结点的左子树与右子树。
二叉树的基本性质:
(1)在二叉树的第k层上,最多有2k-1(k≥1)个结点;(2)深度为m的二叉树最多有2m-1个结点;
(3)度为0的结点(即叶子结点)总是比度为2的结点多一个;
(4)具有n个结点的二叉树,其深度至少为[log2n]+1,其中[log2n]+1表示取log2n的整数部分;
(5)具有n个结点的完全二叉树的深度为[log2n]+1;
(6)设完全二叉树共有n个结点。如果从根结点开始,按层序(每一层从左到右)用自然数1,2,….n给结点进行编号(k=1,2….n),有以下结论:
①若k=1,则该结点为根结点,它没有父结点;若k>1,则该结点的父结点编号为INT(k/2);
②若2k≤n,则编号为k的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点);
③若2k+1≤n,则编号为k的结点的右子结点编号为2k+1;否则该结点无右子结点。
满二叉树是指除最后一层外,每一层上的所有结点有两个子结点,则k层上有2k-1个结点深度为m的满二叉树有2m-1个结点。
完全二叉树是指除最后一层外,每一层上的结点数均达到最大值,在最后一层上只缺少右边的若干结点。
二叉树存储结构采用链式存储结构,对于满二叉树与完全二叉树可以按层序进行顺序存储。
二叉树的遍历:
(1)前序遍历(DLR),首先访问根结点,然后遍历左子树,最后遍历右子树;
(2)中序遍历(LDR),首先遍历左子树,然后访问根结点,最后遍历右子树;
(3)后序遍历(LRD)首先遍历左子树,然后访问遍历右子树,最后访问根结点。