脚本宝典收集整理的这篇文章主要介绍了数据结构——树,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
注意: 1.n>0时根结点是唯一的,不可能存在多个根结点。 2.m>0时,子树的个数没有限制,但它们一定是互不相交的。
任何一棵非空树是一个二元组: Tree = (root,F) 其中:root 被称为根结点,F被称为子树森林
对于这种在某个阶段都是两种结果的情形,比如开和关、0和1、真和假、上和下、对与错、正面和反面等,都适合用树状结构来建模,而这种树是很特殊的树状结构,叫做二叉树。
二叉树(Binary Tree)是n(n≥0)个结点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。如下图:
每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。
左子树和右子树是有顺序的,次序不能任意颠倒。
即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。如下图,树1和树2是同一棵树,但它们却是不同的二叉树。
二叉树具有五种基本形态:
所有结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。
在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树 如下图:
如果对一颗有n个结点的二叉树按层序排序,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则称这颗二叉树为完全二叉树
在二叉树的第i层上至多有2i-1个结点(i>=1)
深度为k的二叉树至多有2k-1个结点(k>=1)
对任意一个二叉树,如果其终端结点数为n0,度为2的结点数为n2,则n0 = n2+1。
具有n个结点的完全二叉树的深度为[log2n]+1([]表示向下取整)
如果对一颗有n个结点的完全二叉树的结点按层序编号,对任意一个结点i(1<=i<=n)有: 1. 如果i=1,则结点i为二叉树的根,无双亲;如果i>1,则其双亲为结点[i/2]。 2. 如果2i>n,则则结点i无左孩子(且结点i为叶子结点);否则其左孩子为结点2i。 3. 如果2i+1>n,则则结点i无右孩子;否则其右孩子为结点2i+1。
以上是脚本宝典为你收集整理的数据结构——树全部内容,希望文章能够帮你解决数据结构——树所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。