二叉树和线索二叉树相关问题v1

遍历算法

• pre (NLR)=A{B(DHI)(EJK)}{C(FLM)(GNO)}:$\angle$
  • 
• in (LNR)={(HDI)B(JEK)}A{(LFM)C(NGO)}:$\wedge$
  • 
• post(LRN)={(HID)(JKE)B}{(LMF)(NOG)C}A:⦣
  • 

遍历顺序分类

• 设根节点为N,左子树为L;右子树为R

  • 下面的三种有序遍历都是将高树降阶(矮化)展开
    • 高树=两棵矮树+一个根结点
    • 不断的对矮树进行矮化,直到矮树只有2层甚至1层

• 先根遍历(先序遍历):preOrder

  • NLR

• 中根遍历(中序遍历):InOrder

  • LNR

• 后根遍历(后序遍历):postOrder

  • LRN

遍历要点

• 根据树的定义(二叉树也是树)是递归这一特点,遍历树的所有结点的过程用递归将会很合适,很容易描述
• 我们可以把二叉树的所有结点当做不同级别子树(根节点)
  • 对于叶子结点,其左右孩子都为NULL
  • 左子树永远比(同级别)的右子树先被遍历到
  • 根结点左子树的递归中,较矮的子树先完成遍历,然后是同样矮的右子树完成遍历
    • 最后才是高一层的子树完成遍历
    • 对于中序遍历和后续遍历是自下而上,自左往右的遍历结点
    • 第一个输出(visit)的结点是全树的最左下角结点
    • 当最浅层调用(最近一次调用)完成(弹出调用栈);
    • 次浅层以及更深层调用也逐渐先后地完成,弹出调用栈
  • 调用栈是进进出出的
    • 第一次出栈调用前全部都是进栈
  • 对应于手工计算中序遍历
    • 如果某子树的左子树缺失,那么我们显式的将缺失的左子树用NULL来表示
    • 访问

void xOrderTraverse(BinaryTree T){//参数是二叉树的根节点(作为代表,表示被遍历的二叉树)if(T){/*下面place1/2/3除是三种防止visit(T)的位置,分别对应先序遍历,中序遍历,后序遍历*///place1xOrderTraverse(T->lchild);//递归遍历左子树(递归调用的参数为左子树的根结点)//place2xOrderTraverse(T->rchild);//递归遍历右子树(递归调用的参数为右子树的根结点)//place3}/*递归出口如果本次传入的参数T是个NULL,那么直接结束本次递归调用内部的两个递归调用是通过(子)的树根节点联系起来*/
}

• 对于叶子结点:

xOrderTraverse(Leaf);//
//内部
if(leaf){//visit位于palce1/2/3xOrderTraverse(NULL);xOrderTraverse(NULL);
}

• 另外,对于度为1的结点,它的调用执行过程形如:

  • 下面两种情况都会触发一次空调用

    • T->child表示非空的子树(的根结点)

  • {    xOrderTraverse(NULL);xOrderTraverse(T->child);}
    \\或者
    {    xOrderTraverse(T->child);xOrderTraverse(NULL);}
    

• 最浅层调用：

  • 叶子结点的调用中，包含了来两个xOrderTraverse(NULL)调用
  • 它们是几乎是瞬间就完成的:
  • 计算量非常少,即if(NULL)就结束了

核心

• 本质上是对两层矮树的遍历
• 任何一棵高层树,都会化为对2层矮树的遍历
  • 如果将已经遍历的矮树视为一个大结点
• 每遍历完一棵二层矮子树，就将其视为一个大结点，并且继续遍历这个矮树大结点的双亲（LNR)或者其右兄弟树(LRN）（如果有）

递归方式

• 三种方式的递归遍历算法都比较相似
  • 差别仅在于一行访问逻辑(visit()的位置)
    • 如果抹去这一行,那么三种顺序的遍历函数就是一样的
  • 当然还有函数名字

非递归方式

线索二叉树

二叉树vs线索二叉树(逻辑结构OR存储结构)

• 二叉树是一种逻辑结构(非线性结构)

  • 可以用顺序存储
  • 可以用链式存储
    • 二叉树常用的是二叉链表
    • 结点中包含数据域和若干指针域(至少2个)
    • 如果需要结点能够指向双亲结点,那么可以用3叉链表

• 线索二叉树是一种物理结构

  • 加上线索的二叉树称为**线索二叉树**
    • 线索二叉树中,二叉链表结点结构(ThreadNode)中包含
      • 左右指针(lchild/rchild),指针类型为
      • 左右线索标志(ltag/rtag)

• 线索二叉树利用空指针域配合标记位,可以加速查找节点的前驱/后继

• 对于线索二叉树,树中的2度结点是没有线索的(因为度为2的结点的指针域全被他的左右孩子占用了)

• 线索二叉树分为三种(他们分别对应于险种二叉树的顺序遍历)

  • 先序线索二叉树
  • 中序线索二叉树
  • 后序线索二叉树

线索二叉树的空指针剩余问题

• 假设二叉树线索化后(指针域和标志位相应的被被修改)
  • 比如x序线索二叉树遍历(x可以取先,中,后)
  • 先将其xOrderTraverse序列写出(比如:ABCDE)
    • 首先要考察的是首位结点A&E
      • 他们各自可能提供0个或1个空指针域
      • 先看首尾结点是否为0/1度结点
      • 如果是2度结点,也不提供空指针域
    • 其余结点位于序列内部(不提供空指针域)
      • 他们要么为二度结点(没有空指针域/线索)
      • 并且,他们都既有前驱又有后继,因此注定不会贡献空指针域
  • 对于具体的:先/中/后 序,可以有更进一步的结论

线索二叉树的遍历

• 线索二叉树的遍历应当充分利用线索指针(所以这里避开递归方案)
• 对于先序线索二叉树和中序线索二叉树,它们的遍历可以沿着根结点的后继顺次访问就可以直接完成那边离
• 对于后续线索二叉树,它的遍历稍微多一些细节,需要用到栈
  • 比如结点x作为某个结点T右孩子,x本身又有右孩子,那么x的有指针显然被他的右孩子占用掉,没有更多的右指针可以用来指向后继结点
    • 至于x的左指针,那是用来指向前驱的,因此对于x的后继也帮不上忙
    • 但是可以考虑使用具有指向双亲结点的三叉链来表示