茉莉网
当前位置:首页»其它»二叉树

二叉树的性质的解释 让你更好的理解什么是二叉树 性质及遍历

2018年03月09日 来源:二叉树的性质的解释 大字体小字体

  (2)对于完全二叉树,若某结点无左孩子,则必无右孩子,该结点为叶结点。

  二.二叉树的遍历

  【例6.2】树与二叉树有什么区别?

  二叉树与树的区别:二叉树中每个结点的孩子至多不超过两个,而树对结点的孩子数无限制;另外,二叉树中结点的子树有左右之分,而树的子树没有次序。思考一棵度为2的树与一棵二叉树有什么区别?

  2^(k-1)-1

      c)对任何一棵二叉树T,度为2的节点数n2,度为0的节点数n0,则n0=n2+1。(n个节点共n-1条边:n-1=n1+2*n2;又n=n0+n1+n2,联立两式即得出结论。)

  深度为k且有2^k-1个结点的二叉树称为满二叉树。

      b)满二叉树

  性质2:深度为k的二叉树至多有2k-1个结点(k>=1)

  二叉树(BinaryTree)是结点的有限集合,这个集合或者为空,或者是由一个根结点和两颗互不相交的分别称为左子树和右子树的二叉树组成。二叉树中的每个结点至多有两棵子树,且子树有左右之分,次序不能颠倒。

  (1)满二叉树是完全二叉树,反之不成立;

  c.然后Push该节点的左孩子和右孩子到第一个栈s中。

  根据定义:

   完全二叉树是具有n个节点的二叉树,若按层序编号那么其编号与同样深度的满二叉树的节点编号在二叉树的位置相同,那么他就是完全二叉树,也就是说他的叶子几点只可能出现在最下边的两层,他的深度等于满二叉的深度,但他的节点一定少于等于满二叉树的节点个数,但一定多与2k-1-1,2k-1-1第度数为k-1层的满二叉树的节点个数,那么n就满足2k-1-1

  n=n1+2*n2+1(式7.2)

      a)在二叉树的第i层上至多有2^(i-1)个节点(i>=1)。

  若二叉树为空,则空操作返回;否则按照“左孩子-根结点-右孩子”的顺序进行访问。

  若二叉树为空,则空操作返回;否则按照“根结点-左孩子-右孩子”的顺序进行访问。

  性质3:任意二叉树中,若叶结点的个数为n0,度为2的结点数为n2,则n0=n2+1。

      递归定义:二叉树(BinaryTree)是n(n>=0)个节点的有限集合,该集合或者为空集(称为空二叉树),或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成。

  如图6.11(b)所示,具有3个结点的二叉树有以下5种不同态。

      顾名思义,二叉树是斜的:左斜树,所有节点都只有左子树;右斜树,所有节点都只有右子树。

  数学归纳法证明。

  a.Push根节点到第一个栈s中。

  n=n0+n1+n2(式7.1)

  两种特殊形态的二叉树:满二叉树和完全二叉树,如图6.12所示。

  (5)有N个结点的完全二叉树各结点如果用顺序方式存储,则结点之间有如下关系:若I为结点编号则如果I>1,则其父结点的编号为I/2;

  另一方面,1度结点有一个孩子,2度结点有两个孩子,故二叉树中孩子结点的总效是n1+2*n2,但树中只有根结点不是任何结点的孩子,故二叉树中的结点总数又可表示为:

  如图6.11(a)所示,具有3个结点的树有两种不同形态。

      从树中节点的组成特点来看,有几种特殊二叉树:

  证明:

  归纳步骤:根据归纳假设,第i-1层上至多有2^i-2个结点。由于二叉树的每一个结点至多有两个孩子,故第i层上的结点数,至多是第i-1层上的最大结点数的2倍,即j=i时,该层上至多有2x2^i-2=2^i-1个结点,故命题成立。

  6.2.2二叉树的性质

  归纳基础:i=1时,有2^i-1=2^0=1,因为第1层上只有一个根结点,所以命题成立。

      二叉树具有一些需要我们理解并记住的性质,方便我们更好地使用它。本文省略这些性质的证明,感兴趣的话可以查阅相关书籍。

  (1)若i=1,则该结点是二叉树的根,无双亲,否则,编号为[i/2]的结点为其双亲结点;

  【例6.3】分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。

  (2)二叉树的一个结点的子树有左右之分,而树的子树没有次序。

  证明:设n1为二叉树T中度为1的结点数。因为二叉树中所有结点的度均小于或等于2,,所以其结点总数:

  性质1:二叉树第i层上的结点数目最多为2^i-1(i>=1)

  (1)二叉树的一个结点至多有两个子树,树则不然;

  对任一节点P,先将其入栈;如果P不存在左右孩子,则可直接访问它,或者P存在左右孩子,但它们都已被访问过了,则同样直接访问P;若非上述两种情况,则将P的右孩子和左孩子依次入栈。这样就保证了每次取栈顶元素的时候,左孩子在右孩子的前面被访问,左右孩子都在根节点前面被访问。如下:

  若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。

  二叉树

  性质4:具有n个结点的完全二叉树的深度为[log2n]+1([log2n]表示该值的最大整数)

  区别有两点:

  归纳假设:假设对所有的j(1

  6.2.1二叉树的概念

  由式7.1和式7.2得n0=n2+1

  二叉树是一种重要的树型结构,但二叉树不是树的特例。二叉树的5种形态分别为:空二叉树、只有根结点的二叉树、根结点和左子树、根结点和右子树、根结点和左右子树。

  1.2性质

  证明:在具有相同深度的二叉树中,仅当每一层都含有最大结点数时,其树中结点数最多。因此,利用性质1可得,深度为k的二叉树的结点数至多为:2^0+2^1+...+2^k-1=2^k-1故命题成立。

  证明:设深度为k,则根据性质2和完全二叉树的定义有

      c)根节点只有左子树

  2.1先序遍历

相关内容

编辑精选

Copyright © 2015 茉莉网 http://www.szmlwh.cn. All rights reserved.