最后万博体育max手机版再访问根结点即左—右—根

当前位置:万博man手机客户端 > 万博体育max手机版 > 最后万博体育max手机版再访问根结点即左—右—根
作者: 万博man手机客户端|来源: http://www.shiketool.com|栏目:万博体育max手机版

文章关键词:万博man手机客户端,二叉树

  二叉树是树的特殊一种,具有如下特点:1、每个结点最多有两颗子树,结点的度最大为2。2、左子树和右子树是有顺序的,次序不能颠倒。3、即使某结点只有一个子树,也要区分左右子树。万博体育max手机版

  所有的结点都只有左子树(左斜树),或者只有右子树(右斜树)。这就是斜树,应用较少

  所有的分支结点都存在左子树和右子树,并且所有的叶子结点都在同一层上,这样就是满二叉树。就是完美圆满的意思,关键在于树的平衡。

  对一棵具有n个结点的二叉树按层序排号,如果编号为i的结点与同样深度的满二叉树编号为i结点在二叉树中位置完全相同,就是完全二叉树。满二叉树必须是完全二叉树,反过来不一定成立。

  在上图中,树1,按层次编号5结点没有左子树,有右子树,10结点缺失。树2由于3结点没有字数,是的6,7位置空挡了。树3中结点5没有子树。

  1、在非空二叉树的i层上,至多有2i-1个节点(i=1)。通过归纳法论证。

  2、在深度为K的二叉树上最多有2k-1个结点(k=1)。通过归纳法论证。

  3、对于任何一棵非空的二叉树,如果叶节点个数为n0,度数为2的节点个数为n2,则有: n0 = n2+ 1

  在一棵二叉树中,除了叶子结点(度为0)之外,就剩下度为2(n2)和1(n1)的结点了。则树的结点总数为T = n0+n1+n2;在二叉树中结点总数为T,而连线;最后得到n0 = n2+1;

  满二叉树是完全二叉树,万博体育max手机版对于深度为k的满二叉树中结点数量是2k-1 = n,完全二叉树结点数量肯定最多2k-1,同时完全二叉树倒数第二层肯定是满的(倒数第一层有结点,那么倒是第二层序号和满二叉树相同),所以完全二叉树的结点数最少大于少一层的满二叉树,为2k-1-1。

  b、如果有一颗有n个节点的完全二叉树的节点按层次序编号,对任一层的节点i(1=i=n)有

  1.如果i=1,则节点是二叉树的根,无双亲,如果i1,则其双亲节点为[i/2],向下取整

  当i=1时,为根节点。当i1时,比如结点为7,他的双亲就是7/2= 3;结点9双亲为4.

  二叉树遍历:从树的根节点出发,按照某种次序依次访问二叉树中所有的结点,使得每个结点被访问仅且一次。

  基本思想:先访问根结点,再先序遍历左子树,最后再先序遍历右子树即根—左—右。

  b. 判断结点p的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点p,循环置a;若不为空,则将p的左孩子置为当前结点p;

  基本思想:先中序遍历左子树,然后再访问根结点,万博体育max手机版最后再中序遍历右子树即左—根—右。

  根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一个根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才停止访问,然后按相同的规则访问其右子树。其处理过程如下:

  a. 若其左孩子不为空,则将p入栈,并将p的左孩子设置为当前的p,然后对当前结点再进行相同的操作;

  b. 若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的p置为栈顶结点的右孩子;

  基本思想:先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左—右—根。

  后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左孩子和右孩子都已被访问,并且左孩子在右孩子之前访问才能访问根结点,这就为流程控制带来了难题。下面介绍一种思路。

  要保证根结点在左孩子和右孩子访问之后才能访问,因此对于任一结点p,先将其入栈。若p不存在左孩子和右孩子,则可以直接访问它,或者p存在左孩子或右孩子,但是其左孩子和右孩子都已经被访问过了,则同样可以直接访问该结点。若非上述两种情况,则将p的右孩子和左孩子依次入栈,这样就保证了每次取栈顶元素的时候,左孩子在右孩子之前别访问,左孩子和右孩子都在根结点前面被访问。

  其实而二叉树的建立就是二叉树的遍历,只不过将输入内容改为建立结点而已,比如,利用前序遍历建立二叉树

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!