C++算法题：关于树的算法

问题1：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。

什么是二元查找树？

比如：

转换成双向链表的顺序是：

1  3  4  6  7  8  10  13  14 

步骤一：建立二叉搜索树

struct BSTreeNode  
{  
    int value;  
    BSTreeNode *left;  
    BSTreeNode *right;  
};

BSTreeNode * Insert(BSTreeNode *p, int x)  
{  
    if(p == NULL)  
    {  
//最终新加的元素将会被赶到最下面，新建这个节点；这么做是遵循二元查找树定义的
//前面也可插入只是太麻烦
        p = new BSTreeNode;  
        p->value = x;  
        p->left = NULL;  
        p->right = NULL;  
    }  
    else  
    {  
//如果x小于头结点，加到左边
        if(p->value > x)  
            p->left = Insert(p->left, x);  
//如果x大于头结点，加到右边
        if(p->value < x)  
            p->right = Insert(p->right, x);  
    }  
    return p;  
} 

步骤二：遍历二元查找树

void Traverse(BSTreeNode *p) //中序遍历  
{  
    if(p == NULL)  
        return;  
    Traverse(p->left);      //左
    cout<<p->value<<' ';  //根
    Traverse(p->right);    //右
}  

步骤三：转换为双向链表（比我小之中取最大，比我大之中取最小，分列我两侧）

BSTreeNode * Convert(BSTreeNode *node)  
{  
    if(node == NULL)  
        return NULL;  
    BSTreeNode *leftMax,*rightMin;  
    leftMax = node->left;      
    rightMin = node->right;  
    //找到左子树的最大结点  
    while(leftMax != NULL && leftMax->right != NULL)  
        leftMax = leftMax->right;  
    //找到右子树的最小结点  
    while(rightMin != NULL && rightMin->left != NULL)  
        rightMin = rightMin->left;  
    //递归求解  在调整指针之前，先递归
    Convert(node->right);   
    Convert(node->left);  
    //将左右子树同根结点连起来，只不过是以兄弟的关系  
    if(leftMax != NULL)  
        leftMax->right = node;  
    if(rightMin != NULL)  
        rightMin->left = node;  
    node->left = leftMax;  
    node->right = rightMin;  
    return node;  
}  

问题2：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换

struct BSTreeNode    
{    
    int value;    
    BSTreeNode *left;    
    BSTreeNode *right;    
}; 

解法一：用递归

//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像  
//函数参数 ： pRoot为根结点  
//返回值 ：   根结点  
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)  
{  
    if(pRoot != NULL)  
    {  
 //必须记住这个节点，不然下面的赋值将把原来的关系解除，就找不到原来的pRoot->left;了
        BSTreeNode * pRight = pRoot->right;  
        BSTreeNode * pLeft = pRoot->left; 
        pRoot->left = Mirror_Solution1(pRight);  //转化右子树  
        pRoot->right = Mirror_Solution1(pLeft);  //转化左子树  
    }  
    return pRoot;  
} 

解法二：用循环

BSTreeNode * Mirror_Solution2(BSTreeNode * pRoot)  
{  
    if(pRoot != NULL)  
    {  
        stack<BSTreeNode *> stk;   //辅助栈  
        stk.push(pRoot);           //压入根结点  
        while(stk.size())  
        {  
            BSTreeNode *pNode = stk.top();  
            BSTreeNode *pLeft = pNode->left;  
            BSTreeNode* pRight = pNode->right;  
            stk.pop();  
  
            if(pLeft != NULL)  
                stk.push(pLeft);  
            if(pRight != NULL)  
                stk.push(pRight);  
            pNode->left = pRight;  //交换左右子女  
            pNode->right = pLeft;  
        }  
    }  
    return pRoot;  
} 

问题3：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。

//跟上一篇的镜像二叉树类似
//函数功能 ： 按层次遍历二元树  
//函数参数 ： pRoot指向根结点  
//返回值 ：   无  
void LevelReverse(BSTreeNode *pRoot)  
{  
    if(pRoot == NULL)  
        return;  
  
    queue<BSTreeNode *> nodeQueue;  
    nodeQueue.push(pRoot);  
    while(nodeQueue.size())  
    {  
        BSTreeNode * pNode = nodeQueue.front(); //取队首元素  
        nodeQueue.pop(); //必须出队列  
        if(pNode->left)  //左子女  
            nodeQueue.push(pNode->left);  
        if(pNode->right) //右子女  
            nodeQueue.push(pNode->right);  
  
        cout<<pNode->value<<' ';  
    }  
} 

问题4：输入一棵二叉树的根结点，判断该树是不是平衡二叉树。如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。例如下图中的二叉树就是一棵平衡二叉树

struct BinaryTreeNode  
{  
    int data;  
    BinaryTreeNode *pLeft;  
    BinaryTreeNode *pRight;  
};  
//函数功能 ： 判断二叉树是不是平衡的  
//函数参数 ： pRoot为根结点，pDepth为根结点的深度。  
//返回值 ：   是否平衡的  
bool IsBalanced(BinaryTreeNode *pRoot, int *pDepth)  
{  
    if(pRoot == NULL)  
    {  
        *pDepth = 0;  
        return true;  
    }  
    int leftDepth, rightDepth; //左右子树的深度  
    //只有左右子树已经是平衡，才能比较当前节点是不是平衡
    if(IsBalanced(pRoot->pLeft, &leftDepth)&&  
        IsBalanced(pRoot->pRight, &rightDepth))  
    {  
        int diff = leftDepth - rightDepth;  
        if(diff == 0 || diff == 1 || diff == -1)  //相差为0或1或-1  
        {  
            *pDepth = 1 + (leftDepth > rightDepth ? leftDepth: rightDepth);   
            return true;  
        }  
        else  
     //如果返回一个false则全盘都是false
            return false;  
    }  
    return false;  
}