@[TOC]目录

二叉树——概念与操作

基本概念

二叉树的基本概念与性质

基本概念

二叉树有5种基本形态，特殊的二叉树有满二叉树、完全二叉树、二叉排序树和平衡二叉树。

性质
存储结构

二叉树的存储结构有顺序存储结构和链式存储结构两种。满二叉树和完全二叉树采取顺序存储结构比较合适，树中的节点号可以唯一的反映出节点之间的逻辑关系，可以节省空间也可以利用数组元素的下标确定节点在二叉树中的位置以及节点之间的关系。一般二叉树采用链式结构存储，二叉链表中包含3个域，分别是数据域data、左指针lchild和右指针rchild。二叉树的链式存储结构描述如下：

// 二叉树链式存储结构
typedef struct BiNode {
    ElemType data;                    // 数据域
    struct BiNode *lchild, *rchild;   // 左右孩子指针
}BiNode, *BiTree;

线索二叉树的基本概念与性质

基本概念

线索二叉树的实质就是对一个非线性结构进行线性化操作，使在这个访问序列中的每一个节点都有一个直接前驱和一个直接后继，引入线索二叉树是为了加快查找节点前驱和后继的速度。

在有N个节点的二叉树中，一共有N+1空指针。在二叉树线索化的时候，通常规定：若无左子树，另lchild指向其前驱节点；若无右子树，则rchild指向其后继节点。还需要两个标志域ltag和rtag表明当前指针域所指的对象是左子节点还是直接前驱。保标志域的含义如下所示：

ltag: 0 lchild域指示节点的左孩子；1 lchild域指示节点的前驱；

rtag: 0 rchild域指示节点的右孩子；1 rchild域指示节点的后继。

线索二叉树的存储结构描述如下所示：

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

二叉树的操作

二叉树的遍历

先序遍历
由于这种算法每一个节点都访问且仅访问一次，所以算法的时间复杂度为O(n),在最坏的情况下，算法的空间复杂度为O(n).

  // 递归实现先序遍历二叉树
  void PreOrder(BiTree T) {
      if (T != NULL) {
          visit(T);
          PreOrder(T -> lchild);
          PreOrder(T -> rchild);
      }
  }

/*非递归实现先序遍历二叉树
    算法思路：
    需要借助栈来实现，从根节点开始遍历二叉树，如果节点不为空
    先输出节点的数据，节点入栈，然后指针指向节点的左孩子，如
    果节点为空那么从占中弹出这个节点，并且将指针指向节点的右
    孩子，重复这个过程直到栈为空，并且指针指向也为空为止。
*/
void PreOrder2(BiTree T) {
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)) {
        if (p) {
            visit(p);
            push(S, p);
            p = p -> lchild;
        } else {
            pop(S, p);
            p = p -> rchild;
        }
    }
}
//  算法的时间复杂度和空间复杂度都是O(n)

中序遍历
由于这种算法每一个节点都访问且仅访问一次，所以算法的时间复杂度为O(n),在最坏的情况下，算法的空间复杂度为O(n).

 //  递归算法实现中序遍历二叉树
void InOrder(BiTree T) {
      if (T != NULL) {
          InOrder(T -> lchild);
          visit(T);
          InOrder(T -> rchild);
      }
  }

/*非递归实现中序遍历二叉树
    算法思路：
    需要借助栈来实现，从根节点开始遍历二叉树，如果节点不为空
    将节点入栈，然后指针指向节点的左孩子，如果节点为空，那么
    从栈中弹出这个节点，输出节点的数据，并且将指针指向节点的
    右孩子，重复这个过程直到栈为空，并且指针指向也为空为止。
*/
void InOrder2(BiTree T) {
    InitStack(S);
    BiTree p = T;
    while(p || !isEmpty(S)) {
        if (p) {
            push(S, p);
            p = p -> lchild;
        } else {
            pop(S, p);
            visit(p);
            p = p -> rchild;
        }
    }
}

后序遍历
由于这种算法每一个节点都访问且仅访问一次，所以算法的时间复杂度为O(n),在最坏的情况下，算法的空间复杂度为O(n).

//  递归实现后序遍历二叉树
  void PostOrder(BiTree T) {
      if (T != NULL) {
          PostOrder(T -> lchild);
          PostOrder(T -> rchild);
          visit(T);
      }
  }

/*
非递归实现后序遍历二叉树
    算法思想：后序遍历先访问左节点，再访问右节点，最后访问中间节点
        在访问到中间节点的时候要先弄清楚是从左节点返回的中间节点还
        是从右节点返回的中间节点，所以需要一个辅助指针r指向最近访
        问过的节点。

*/
void PostOrder2(BiTree T) {
    InitStack(S);
    BiTree p, r;
    p = T;
    r = NULL;
    while(p || !isEmpty(S)) {
       if (p) {
           //  走到最左边
           push(S, p);
           p = p -> lchild;
       } else {
           GetTop(S, p);
           if (p -> rchild && p -> rchild != r) {
               // 如果节点的右子树存在，那么转向右边
               p = p -> rchild;
               push(S, p);
               p = p -> lchild;   // 向左走
           } else {
               pop(S, p);
               visit(p);
               r = p;
               p = NULL;          //重置指针
           }
       } //  else
    } //  while
}

层次遍历

void LevelOrder(BiTree T) {
    //  二叉树从上到下，从左到右的层次遍历需要借助队列来实现
    InitQueue(Q);
    BiTree p = NULL;
    EnQueue(Q, T);    //  根节点入栈；
    while(!isEmpty(Q)) {
        DeQueue(Q, p);
        visit(p);
        if (p -> lchild != NULL)
            EnQueue(p -> lchild);
        if (p - > rchild != NULL)
            EnQueue(p -> rchild);
    }
}

void LevelOrderInverse(BiTree T) {
    //  二叉树从下到上，从右到左的层次遍历
    //  实现思路：将二叉树从上到下，左到右的顺序放入栈中，
    //       等遍历完了再弹出即可
    if (T != NULL) {
         InitStack(S);
        InitQueue(Q);
        BiTree p = t;
        EnQueue(Q, p);   //  将根节点放入队列中
        while(!isEmpty(Q)) {
            DeQueue(Q, p);
            push(S, p);
            if (p -> lchild)
                EnQueue(p -> lchild);
            if (p -> rchild)
                EnQueue(p -> rchild);
        }
        while(!isEmpty(S)) {
            pop(S, p);
            visit(p)
        }
    }
}

由遍历序列构造二叉树

（1）根据二叉树的先序和中序可以唯一的确定一棵二叉树： 假设先序和中序分别存在两个一维数组A[1….n],B[1….n]中，编写算法建立该二叉树的二叉链表。

/*
这个算法需要遍历两个一维数组，递归实现：根据先序序列确定二叉树的根节点，根据根节点，在中序序列中划分出左子树和右子树，递归这个过程。
*/
BiTree PreInCreat(ElemType A[], ElemType B[], int l1, int h1, int 12, int h2) {
    //  l1,h1分别树先序序列的第一个节点和最后一个节点；
    //  l2,h2分别树中序序列的第一个节点和最后一个节点；
    BiTree root = (BiNode*)malloc(sizeof(BiNode));
    root -> data = A[l1];
    int i = 0;
    for (i = 0; B[i] != A[l1]; i++);  //  在中序序列中找到根节点位置
    int lenl = i - l2;
    int lenr = h2 - i;
    if (lenl) {
        //  递归建立左子树
        root - lchild = PreInCreat(A, B, l1 + 1, l1 + lenl, l2, l2 + lenl - 1);
    } else {
        root -> lchild  = NULL;
    }
    if (lenr) {
        //  递归建立右子树
        root - rchild = PreInCreat(A, B, h1-lenr+1, h1, h2-lenr+1, h2);
    } else {
        root -> rchild = NULL;
    }
    return root;
}

(2) 由二叉树的后序序列和中序序列可以唯一的确定一棵二叉树
假设后序和中序分别存在两个一维数组A[1….n],B[1….n]中，编写算法建立该二叉树的二叉链表。后序序列的最后一个节点和先序序列的第一个节点类似，可以将中序分割成两个子序列。

BiTree PostInCreat(ElemType A[], ElemType B[], int l1, int h1, int l2, int h2) {
    //  l1,h1分别树后序序列的第一个节点和最后一个节点；
    //  l2,h2分别树中序序列的第一个节点和最后一个节点;
    BiTree root = (BiNode*)malloc(sizeof(BiNode));
    root -> data = A[h1];
    int i = 0;
    for(i = 0;B[i] != A[h1]; i++);  //  在中序序列里面找到根节点
    int lenl = i - l2;
    int lenr = h2 - i;
    if(lenl) {
        root -> lchild = PostInCreat(A, B, l1, l1+lenl-1, l2, l2+lenl-1);
    } else {
        root -> lchild = NULL;
    }

    if(lenr) {
        root -> rchild = PostInCreat(A, B, h1-lenr, h1-1, h2-lenr+1, h2);
    } else {
        root -> rchild = NULL;
    }

    return root;
}
`

(3) 由二叉树的层序序列和中序序列也可以唯一的确定一棵二叉树

//  假设层序序列和中序分别存在两个一维数组A[1....n], B[1....n]中，
//  编写算法建立该二叉树的二叉链表。
/*
  算法思路：从左到右遍历层序数组，层序遍历的第一个元素如果在中序
      中没有访问过，那么这个数可以作为根节点，根据这个根节点可以
      将中序序列划分为左子树和右子树。期间需要借助一个数组来记录
      元素是否在中序序列中被访问过。
*/
BiTree LevelInCreat(ElemType A[], ElemType B[], boolean C[], int index, int l, int r) {
/*
    初始时C是一个全为真的布尔数组，大小与A,B相同，如果C中元素在
    B中被访问过，那么标记为假，此时A中对应的被访问到的元素就不能
    作为根节点，需要继续往右寻找没有被访问过的节点作为根节点。
*/
    BiTree root = (BiNode*)malloc(sizeof(BiNode));
    for(index; C[index] == false; index++);   //  排除已经访问过的节点的干扰
    root -> data = A[index];
    int i = 0;
    for(i = 0; B[i] != A[index]; i++);
    C[index] = false;    //  已经访问过的节点就标记为已访问
    int lenl = i - l;
    int lenr = r - i;
    if (lenl) {
        root -> lchild = LevelInCreat(A, B, C, index+1, l, l+lenl-1);
    } else {
        root -> lchild = NULL;
    }
    if(lenr) {
        root -> lchild = LevelInCreat(A, B, C, index+1, r-lenr+1, r);
    } else {
        root -> rchild = NULL;
    }

    return root;
}

一些二叉树的题目

（1）判断二叉树是否为完全二叉树

    思路：使用层次遍历算法，将所有节点加入队列，包括空节点，遍历结束
    后查看队列，如果遇到了空节点，看看其后是否有非空节点，如果有，那
    么二叉树不是完全二叉树，否则是完全二叉树。

（2）链式存储，计算二叉树的所有双分支节点的个数

    思路：采用如下所示的递归式：
    f(b) = 0;                                  若b = NULL
    f(b) = f(b->lchild) + f(b->rchild) + 1;    若b为双分支节点
    f(b) = f(b->lchild) + f(b->rchild);        其余情况

（3）交换二叉树中所有节点的左右子树

    swap(b->lchild)  递归交换左子树
    swap(b->rchild)  递归交换右子树
    交换左右孩子节点

（4）指针p,q分别指向二叉树的任意两个节点，寻找p,q的最近的公共祖先节点。

    采用后序遍历，访问到其中一个节点之后将其之后的所有祖先节点放
    入一个队列中，另一个节点也是一样，访问到之后将其所有祖先节点
    放入另一个队列中，遍历结束之后，比较两个队列，两个队列第一个
    相同的元素就是两个节点的最近公共祖先节点。

（5）链式存储，求非空二叉树的宽度

    采用层次遍历即可得出

（6）满二叉树已知先序序列pre，求后序序列post.

    先序序列的第一个节点为后序序列的最后一个节点，然后除第一个元
    素之外，将先序序列划分为大小相等的两份，再对这两份转化。
    void PreToPost(pre, post, int l1, int h1, int l2, int h2) {
        if(h1 >= l1) {
            post[h2] = pre[l1];
            half = (h1-l1) / 2;
            PreToPost(pre, post, l1+1, l1+half, l2, l2+half-1);
            PreToPost(pre, post, l1+half+1, h1, l2+half, h2-1);
        }
    }