题目:
输入一颗二元查找树,将该数转换为它的镜像,即在转换后的二元查找树中,左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入:
输出:
定义二元查找树的结点为:
struct BSTreeNode
{
int m_nValue; //value of node
BSTreeNode *m_pLeft; //left child of node
BSTreeNode * m_pRight; //right child of node
};
//就是递归翻转树,有子树则递归翻转子树。
方法一:使用递归
void Revertsetree(list *root)
{if (!root)return;list *p;p = root->leftch;root->leftch = root->rightch;root->rightch = p;if (root->leftch)Revertsetree(root->leftch);if (root->rightch)Revertsetree(root->rightch);}
方法二:使用循环
由于递归的本质是编译器生成了一个函数调用的栈,因此用循环来完成同样任务时最简单的办法就是用一个辅助栈来模拟递归。
首先我们把树的头结点放入栈中,在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树。
如果它有左子树,,把它的左子树压入栈中。
如果他有右子树,把它的右子树压入栈中。
这样在下次循环中就能交换它儿子结点的左右子树了。
//再用辅助栈模拟递归,改成循环的。
void Revertsetree(list* phead){if (!phead)return;stack<list*> stacklist;stacklist.push(phead);while (stacklist.size())//在循环中,只要栈不为空,弹出栈的栈顶结点,交换它的左右子树{list* pnode = stacklist.top();stacklist.pop();list *ptemp;ptemp = pnode->leftch;pnode->leftch = pnode->rightch;pnode->rightch = ptemp;if (pnode->leftch)stacklist.push(pnode->leftch);//若有左子树,把它的左子树压入栈中if(pnode->rightch)stacklist.push(pnode->rightch);//若有右子树,把它的右子树压入栈中}}
而做人的能力则会给你一百种机会。