第六章 树和二叉树

1、证明：一棵二叉树的所有终端结点（叶结点）在前序序列、中序序列以及后序序列中都按相同的相对位置出现.

前序遍历是“根一左一右”中序遍历是“左一根一右”后序遍历是“左一右一根”。三种遍历中只是访问“根”结点的时机不同对左右子树均是按先左后右顺序来遍历的因此所有叶子都按相同的相对位置出现。

2、试写一个判定所给定二叉树是否为二叉排序树的算法，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不同。

int IsSearchTree(const BTNode *t){
    if(!t) //空二叉树情况
        return 1;
    else if(!(t->lchild) && !(t->rchild))//左右子树都无情况
        return 1;
    else if((t->lchild) && !(t->rchild)){//只有左子树情况
        if(t->lchild->data>t->data)
            return 0;
        else
        return IsSearchTree(t->lchild);
    }
    else if((t->rchild) && !(t->lchild)){//只有右子树情况
        if(t->rchild->datadata)
            return 0;
        else
            return IsSearchTree(t->rchild);
    }
    else{ //左右子树全有情况
        if((t->lchild->data>t->data) ||(t->rchild->datadata))
            return 0;
        else
            return IsSearchTree(t->lchild) && IsSearchTree(t->rchild);
    }
}

3、证明若二叉排序树中的一个节点存在两个孩子，则它的中序后继节点没有左孩子，且它的中序前趋节点没有右孩子。

• 前序遍历：45 12 3 37 24 53 100 61 90 78
• 中序遍历：3 12 24 37 45 53 61 78 90 100

【证明】根据中序遍历的定义，该结点的中序后继是其右子树上按中序遍历的第一个结点，即右子树上值最小的结点：叶子结点或仅有右子树的结点，没有左孩子；而其中序前驱是其左子树上按中序遍历的最后个结点，即左子树上值最大的结点：叶子结点或仅有左子树的结点，没有右孩子。命题得证。

4、给定二叉树 T，其中任意两个结点 p、q，设计算法，求 p 和 q 最近的共同祖先。

求解思路:先判断给定的两个结点是否有一个为根结点，如果有一个结点为根结点，则直接返回根结点。否则判断两个结点是否在同一颗子树，如果不在，则它们最近的公共祖先结点也为根结点；如果同在左子树，重复上述过程；否则在右子树中重复上述过程。

struct TreeNode* Find(struct TreeNode* root,int val)
{
    if(root == NULL)
    {
        return NULL;
    }
    if(root->val == val)
    {
        return root;
    }
    struct TreeNode* found = Find(root->left,val);
    if(found != NULL)
    {
        return found;
    }
    return Find(root->right,val);
}

struct TreeNode* lowestCommonAncestor(struct TreeNode* root, struct TreeNode* p, 

struct TreeNode* q) {
    struct TreeNode* pInLeft = Find(root->left,p->val);
    struct TreeNode* qInLeft = Find(root->left,q->val);
    if(p == root || q == root)   //判断给定结点是否是根结点
    {
        return root;
    }
    //如果给定结点不 同在左子树，返回根结点
    if(pInLeft == NULL && qInLeft != NULL)  
    {
        return root;
    }
    //如果给定结点不 同在右子树，返回根结点
    if(pInLeft != NULL && qInLeft == NULL)   
    {
        return root;
    }
    if(pInLeft != NULL)   //给定结点同在左子树
    {

        return lowestCommonAncestor(root->left,p,q);
    }
    else    //给定结点同在右子树
    {
        return lowestCommonAncestor(root->right,p,q);
    }
}

5、若一棵二叉树，左右子树均有三个结点，其左子树的前序序列与中序序列相同，右子树的中序序列与后序序列相同，试构造该树。

由左子树的前序序列与中序序列相同得:

• 前序： 根 左 右
• 中序： 左 根 右
  所以以左子树为根的树没有左孩子。
  由左子树的前序序列与中序序列相同得:
• 中序： 左 根 右
• 后序： 左 右 根
  所以以左子树为根的树没有右孩子。