二叉树的遍历和线索二叉树

本文主要讨论二叉树的四种遍历方式，以及对应线索二叉树的构造以及遍历过程。

先序遍历（PreOrder）

算法逻辑：（NLR）

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

由此可以简单写出对应递归算法：

void PreOrder(BinTree T) {
	if(T != null) {
    visit(T);
    PreOrder(T -> lchild);
    PreOrder(T -> rchild);
  }
}

因为每个节点都被访问一次，所以时间复杂度为\(O(n)\)，递归工作栈的深度恰好为树的深度，所以最坏情况是树为单链树时空间复杂度为\(O(n)\)。

接下来使用非递归方式实现二叉树的先序遍历：

void PreOrder_nonRecursive(BinTree T) {
  BinTree *p = T;
  InitStack(s); //初始化辅助栈
  while(p != null || isEmpty(s)) {
    if(p != null) {
      visit(p);
      Push(s, p); //当前指向结点入栈
     	p = p -> lchild; //一路向左
    }
    else { //当无左孩子访问时
      pop(s, p); //出栈上一层访问的元素，直到其有右孩子
      p = p -> rchild; 
    }
    //当栈和指针p都为空时，说明树已遍历完成，结束循环
  }
}

中序遍历（InOrder）

算法逻辑：（LNR）

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

由此可以简单写出对应递归算法：

void InOrder(BinTree T) {
	if(T != null) {
    InOrder(T -> lchild);
    visit(T);
    InOrder(T -> rchild);
  }
}

因为每个节点都被访问一次，所以时间复杂度为\(O(n)\)，递归工作栈的深度恰好为树的深度，所以最坏情况是树为单链树时空间复杂度为\(O(n)\)。

接下来使用非递归方式实现二叉树的先序遍历：

void InOrder_nonRecursive(BinTree T) {
	BinTree *p = T;
  InitStack(s); //初始化辅助栈
  while(p != null || isEmpty(s)) {
    if(p != null) {
      Push(s, p); //当前指向结点入栈
     	p = p -> lchild; //一路向左
    }
    else {
      Pop(s, p); //无左孩子可访问时，出栈
      visit(p); //访问上一轮入栈的结点
      p = p -> rchild; //转向其右孩子
    }
  }
}

可以发现先序遍历和中序遍历的非递归实现逻辑很相似，可以联想记忆。

后序遍历（PostOrder）

算法逻辑：（LRN）

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

由此可以简单写出对应递归算法：

void PostOrder(BinTree T) {
	if(T != null) {
    PostOrder(T -> lchild);
    PostOrder(T -> rchild);
    visit(T);
  }
}

因为每个节点都被访问一次，所以时间复杂度为\(O(n)\)，递归工作栈的深度恰好为树的深度，所以最坏情况是树为单链树时空间复杂度为\(O(n)\)。

对于后序遍历的非递归实现，发现和前两者不同，要保证左孩子和右孩子都已经被访问并且左孩子在右孩子之前访问才能访问根结点。

后序非递归遍历算法的思路分析：从根结点开始，将其入栈，然后沿其左子树一直往下搜索，直到搜索到没有左孩子的结点,但是此时不能出栈并访问，因为如果其有右子树,还需按相同的，规则对其右子树进行处理。直至上述操作进行不下去，若栈顶元素想要出栈被访问，要么右子树为空,要么右子树刚被访问完(此时左子树早已访问完)，这样就保证了正确的访问顺序。

void PostOrder_nonRecursive(BinTree T) {
	BinTree *p = T ,r = null; //指针r用来记录最近访问结点。
  InitStack(s); //初始化辅助栈
  
  while(p != null || isEmpty(s)) {
    if(p != null) {
      Push(s, p); //当前指向结点入栈
     	p = p -> lchild; //一路向左
    }
    else {
			GetTop(s, p); //读取栈顶元素（非出栈）
      //当p的右孩子存在，且没被访问过时
      if (p -> rchild != null && p -> rchild != r) {
        p = p -> rchild;
        Push(s, p); //入栈p的右孩子
        p = p -> lchild; //接着转向p的左孩子
      }
      else {
        pop(s, p);
        visit(p);
        r = p; //记录最近访问的结点
        p = null;//重置p为空
      }
    }
  }
}

层序遍历

从上到下，从左到右对每层元素进行访问。

通过借助辅助队列，我们可得遍历算法如下：

void LevelOrder(BiTree T) {
  InitQueue(Q); //初始化辅助队列
  BiTree p;
  EnQueue(Q, T); //根结点入队
  while (!isEmpty(Q)) {
    DeQueue(Q, p);
    visit(p);
    if (p -> lchild != null) {
      EnQueue(Q, p -> lchild);
    }
    if (p -> rchild != null) {
      EnQueue(Q, p -> rchild);
    }
  }
}

由遍历序列构造二叉树

需要特别说明的是，上述四种遍历方法，任选其一与中序遍历，都能唯一确定一颗二叉树。

中序遍历序列主要用来划分左右子树。但是没有中序序列的话，无法唯一确定一颗二叉树。

线索二叉树

遍历二叉树是以一定的规则将二叉树中的结点排列成一个线性序列，从而得到几种遍历序列，使得该序列中的每个结点（第一个和最后一个结点除外）都有一个直接前驱和直接后继。传统的二叉链表存储仅能体现一种父子关系，不能直接得到结点在遍历中的前驱或后继。 前面提到，在含\(n\)个结点的二叉树中,有\(n+1\)个空指针。这是因为每个叶结点有2个空指针，每个度为1的结点有1个空指针，空指针总数为\(2n_0+n_1\),又\(n=n_2+1\)，所以空指针总数为\(n_0+n_1+n_2+1=n+1\)。利用这些空指针来存放指向其前驱或后继的指针这样就可以像遍历单链表那样方便地遍历二叉树。

引入线索二叉树正是为了加快查找结点前驱和后继的速度。

线索二叉树是一种物理结构，它是二叉树在计算机内的一种存储结构。

typedef struct ThreadNode{
	ElemType data; //数据元素
	struct ThreadNode *lchild, *rchild; //左,右孩子指针
	int ltag,rtag; //左,右线索标志
}ThreadNode,*ThreadTree;

标志域含义如下： \[ ltag=\left\{ \begin{array}{aligned} 0 && lchild域指示结点左孩子 \\ 1 && lchild域指示结点的前驱 \end{array} \right.\\ rtag=\left\{ \begin{array}{aligned} 0 && rchild域指示结点右孩子 \\ 1 && rchild域指示结点的后继 \end{array} \right. \]

中序线索二叉树的构造

思路：我们还是通过先进行一次中序遍历，用指针p指向当前结点，指针pre指向前一个节点，这样当我们想找到任意节点q的前驱或者后继时，满足条件\(p == q\)时，pre为前驱；当满足条件\(pre = q\)时，p指向后继。

//辅助全局变量
BiTNode *p;           //指向当前结点
BiTNode *pre = null;  //指向当前结点的前驱
BiTNode *final = null;//用于记录最终结果

//中序遍历
void InOrder(BinTree T) {
	if(T != null) {
    InOrder(T -> lchild);
    visit(T);
    InOrder(T -> rchild);
  }
}

void visit(BiTNode *q) {
  //当前结点左孩子为空
  if (q -> lchild == null) { 
    q -> lchild = pre;
    q -> ltag = 1;
  }
  //前驱结点存在并且前驱右孩子为空，线索化
  if (pre != null && pre -> rchild == null)
  {
    pre -> rchild = q; // 前驱的后继为q
    pre -> rtag = 1;
  }
  pre = q;
}

// 注意：需要处理最后一个结点，需要让其右孩子指向null，并且修改rtag。

同理可得先序线索二叉树。注意⚠️

void PreOrder(BinTree T) {
	if(T == null) {
    visit(T);
    if (T -> ltag == 0) { // 只有在当前结点的左孩子未被先线索化是进行线索化
      PreOrder(T -> lchild); //不做判断的话，会陷入死循环
    }
    PreOrder(T -> rchild);
  }
}

同理可得后序线索二叉树。注意⚠️，需要处理最后一个访问结点的rchild & rtag。

练习部分

求一棵树的深度（递归方法）

int treeDepth(BinTree T) {
	if (T == null) {
		return 0;
	}
	else {
		int l = treeDepth(T -> lchild);
		int r = treeDepth(T -> rchild);
		return l > r ? l + 1 : r + 1;
	}
}

求一棵树的深度（非递归方法）

采取层次遍历的方法，设置变量level记录当前结点所在的层数，设置指针last指向当前层的最右结点，每次层次遍历出队与last比较，若两者相等，则层数加1，并让last指向下一层最右结点，至遍历完成，返回level值。

int treeDepth(BiTree T) {
  if (T == null) {
    return 0;
  }
  int front = -1, rear = -1;
  InitQueue(Q);
  BiTree p;
  Q[++rear] = T; //根结点入队
  while(front < rear) {
    p = Q[++front]; //队列元素出队，访问
    if (p -> lchild) {
      Q[++rear] = p -> lchild; //左孩子入队
    }
    if (p -> rchild) {
      Q[++rear] = p -> rchild; //右孩子入队
    }
    if (front == last) { //处理该层最右边的结点
      level++; //层数加一
      last = rear; //last指针指向下层最右侧结点
    }
  }
  return level;
}

已知一棵二叉树按顺序存储结构进行存储，设计一个算法，求编号分别为i和j的两个结点的最近的公共祖先结点的值。

最好情况是一结点为另一结点的父结点，最坏情况是两个结点的公共祖先是二叉树的根结点。

因为采取顺序存储的方式，初始时，整数 i， j分别对应的两个结点在顺序表中的存储位置（根结点对应1）。

让i，j中的较大者先进行循环。此时父结点的下标对应为 \(\frac{子结点下标}{2}\)。循环至，i = j时结束。

Elemtype findAncestor(SqTree T[], int i, int j) {
    if (T[i] != '#' && T[j] != '#') // 两节点存在
    {
        while (i != j)
        {
            if (i > j)
            {
                i = i / 2;
            }
            else
            {
                j = j / 2;
            }
        }
        return T[i];
    }
}