二叉树的度含义是:二叉树的某个结点的子节点或者直接后继节点的个数,1度代表只有一个子节点或者是单子树,2度代表有两个子节点或者是左右子树都有,二叉树是一个连通的无环图,并且每一个顶点的度不大于3。
在二叉树中,一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大节点数。而在一棵二叉树中,除最后一层外,若其余层都是满的,并且最后一层或者是满的,或者是在右边缺少连续若干节点,则此二叉树为完全二叉树。
扩展资料二叉树的性质和应用方法:
1、在非空二叉树中,第i层的结点总数不超过, i>=1;
2、深度为h的二叉树最多有个结点(h>=1),最少有h个结点;
3、对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1;
5、有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:
若I为结点编号则 如果I>1,则其父结点的编号为I/2;
如果2I<=N,则其左孩子(即左子树的根结点)的编号为2I;若2I>N,则无左孩子;
如果2I+1<=N,则其右孩子的结点编号为2I+1;若2I+1>N,则无右孩子。
参考资料:
结点所拥有的子树的个数称为该结点的度(Degree); 树中各结点度的最大值称为该树的度; 称度为m的树为m叉树。
:在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。
二叉树不是树的一种特殊情形,尽管其与树有许多相似之处,但树和二叉树有两个主要差别:
1 树中结点的最大度数没有限制,而二叉树结点的最大度数为2;
2 树的结点无左、右之分,而二叉树的结点有左、右之分。
二叉树的度是指树中所以结点的度数的最大值。二叉树的度小于等于2,因为二叉树的定义要求二叉树中任意结点的度数(结点的分支数)小于等于2。
通俗的讲二叉树中连接节点和节点的线就是度,有n个节点,就有n-1个度,节点数总是比度要多一个,那么度为0的节点一定是叶子节点,因为该节点的下面不再有线;度为1的节点即:该节点只有一个分支;同理度为2的节点就是有两个分支。在二叉树中不可能存在度为3或大于3的节点。
二叉树的性质
性质1:在二叉树的第i层上最多有2^(i-1)个结点(i≥1)。
性质2:深度为k的二叉树至多有2^k-1个结点(k≥1)。
性质3:对任何一棵二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。
性质4:具有n个结点的完全二叉树的深度为|log(2^n)+1|。
性质5:如果对一棵有n个结点的完全二叉树(其深度为|log(2^n)+1|)的结点按层序编号(从第一层到第层,每层从左到右)。
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)