data structure

代码实现参考

1. 二叉树的遍历

按某条搜索路径访问树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次 。

常见地有先序(NLR)、中序(LNR)和后序(LRN)三种遍历算法 。

1.1 先序遍历

  1. 访问根结点
  2. 先序遍历左子树
  3. 先序遍历右子树

1.2 中序遍历

  1. 中序遍历左子树
  2. 访问根结点
  3. 中序遍历右子树

1.3 后序遍历

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根结点

三种算法的时间复杂度为 O(n) ,空间复杂度为 O(n)

1.4 递归算法和非递归算法的转换

借助栈,可以将二叉树的递归遍历算法转换为非递归算法。以中序遍历为例 。

  1. 根结点进栈,根结点的所有左结点进栈
  2. 出一个左结点 P,访问它。
  3. 扫描 P 的右孩子,将其作为根结点,回到 1 步骤
  4. 重复前 3 步直到栈空

其他两个遍历自己实现 。

1.5 层次遍历

借助队列实现。

  1. 先将二叉树的根结点入队,然后出队,访问该结点
  2. 若它有左子树,则将左子树根结点入队
  3. 若它有右子树,则将右子树根结点入队。
  4. 出队,对出队结点访问,重复 2,3 步骤
  5. 直到队列空

注意 :遍历是二叉树各种操作的基础,可以在遍历的过程中对结点进行各种操作,例如 :对于一棵已知树求结点的双亲、求结点的孩子结点,求二叉树的深度、求二叉树的叶子结点个数、判断两个二叉树是否相同等 。务必熟记于心 。

1.6 由遍历序列构造二叉树

由二叉树的先序遍历和中序遍历可以唯一地确定一棵二叉树。在先序遍历中,第一个结点一定是二叉树的根结点;而中序遍历中,根结点必然将中序序列分割成两个子序列,前一个子序列是根结点的左子树的中序序列,后一个子序列是根结点的右子树的中序序列。根据这两个子序列,在先序遍历中找到对应的左子序列和右子序列(刚好是两段)。在先序序列中,做子序列的第一个结点是左子树的根结点,右子序列的第一个结点是右子树的根结点。递归下去即可 。(P120 例子)

同理,由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树,因为后序序列的最后一个结点就如同先序序列的第一个结点,可以将中序序列分割成两个子序列,然后采用类似方法递归划分即可。

由二叉树的层次遍历和中序遍历也可以唯一地确定一棵二叉树。

2. 线索二叉树

2.1 线索二叉树的基本概念

遍历二叉树其实就是以一定的规则将二叉树中的结点排列成一个线性序列从而得到二叉树结点的各种遍历序列,其实质是对一个非线性结构进行线性操作,使这个访问序列中每一个结点(第一个和最后一个结点除外)都有一个直接前驱和直接后驱。

传统的链式存储仅能体现一种父子关系,不能直接得到结点在遍历中的前驱或后驱。通过观察,我们发现在二叉链表表示的二叉树中存在大量的空指针(n+1 个),若利用这些空链域存放指向其直接前驱或后继的指针,则可以更方便地运用某些二叉树操作算法。引入线索二叉树是为了加快查找结点前驱和后继的速度。

在二叉树线索化时,通常规定 :若无左子树,令 lchild 指向其前驱结点;若无右子树,令 rchild 指向其后继结点,还需要增加两个标志域表明当前指针域所指对象是指向左(右)子结点还是指向直接前驱(后继)。

ltag=0 表示 lchild 域指示结点的左孩子;ltag=1 表示 lchild 域指示结点的前驱

rtag=0 表示 rchild 域指示结点的右孩子;rtag=1 表示 rchild 域指示结点的后继

以这种结点结构构成的二叉链表作为二叉树的存储结构,称为线索链表,其中指向结点前驱和后继的指针称为线索。加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

2.2 线索二叉树的构造

对二叉树的线索化,实质上就是遍历一次二叉树,只是在遍历的过程中,检查当前结点左、右指针域是否为空,若为空,将它们改为指向前驱结点或后继结点的线索。

以中序线索二叉树的建立为例。指针 pre 指向中序遍历时上一个刚刚访问过的结点,用它来表示各结点访问的前后关系。

算法实现查看

有时为了方便,仿照线性表的存储结构,在二叉树的线索链表上也添加一个头结点,并令其 lchild 域的指针指向二叉树的根结点,令其 rchild 域的指针指向中序遍历时访问的最后一个结点;反之,令二叉树中序序列的第一个结点的 lchild 域的指针和最后一个结点的 rchild 域的指针均指向头结点 。这好比为二叉树建立了一个双向线索链表,即可以从第一个结点起顺后继进行遍历,又可从最后一个结点起顺前驱进行遍历 。

2.3 线索二叉树的遍历

中序线索二叉树主要是为访问运算服务的,这种遍历不再需要借助栈,因为它的结点中隐含了线索二叉树的前驱和后继信息。利用线索二叉树,可以实现二叉树遍历的非递归算法。不含头结点的线索二叉树的遍历算法如下

  1. 求中序线索二叉树中中序序列下的第一个结点

  2. 求中序线索二叉树中结点 p 在中序序列下的后继结点

    自行分析并完成求中序线索二叉树的最后一个结点和结点 p 前驱结点的运算 。

  3. 利用上面两个算法,可以写出不含头结点的中序线索二叉树的中序遍历的算法。