按层次遍历二元树
问题描述：输入一颗二元树，从上往下按层打印树的每个结点，同一层中按照从左往右的顺序打印。
例如输入：
8 / / 6 10 / / / / 5 7 9 11</div>
输出
8 6 10 5 7 9 11</div>
定义二元树（其实是二元搜索树，但并不遍历算法）的结点为：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
</div>
思路：利用队列的先进先出，很容易实现。每次取出队列的首元素，然后将其左右子女放入队列中。直至队列为空即可。按这种方式进出队列，正好是按层遍历二元树。
参考代码：
//函数功能 ： 按层次遍历二元树
//函数参数 ： 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<<' ';
}
}
</div>
扩展一：上文给出的代码，所有结点都输出在同一行。如果希望仅仅同层结点输出在同一行，该如何修改代码呢？
思路：如果我们能知道每层的最后一个结点，那么就方便多了，输出每层最后一个结点的同时，输出一个换行符。因此，关键在于如何标记每层的结束。可以考虑在每层的最后一个点之后，插入一个空结点。比如队列中先放入根结点，由于第0层只有一个结点，因此放入一个空结点。然后依次取出队列中的结点，将其子女放入队列中，如果遇到空结点，表明当前层的结点已遍历完了，而队列中放的恰恰是下一层的所有结点。如果当前队列为空，表明下一层无结点，也就说是所有结点已遍历好了。如果不为空，那么插入一个空结点，用于标记下一层的结束。
参考代码：
void LevelReverse(BSTreeNode *pRoot)
{
if(pRoot == NULL)
return;
queue<BSTreeNode *> nodeQueue;
nodeQueue.push(pRoot);
nodeQueue.push(NULL); //放入空结点，作为层的结束符
while(nodeQueue.size())
{
BSTreeNode * pNode = nodeQueue.front(); //取队首元素
nodeQueue.pop(); //必须出队列
if(pNode)
{
if(pNode->left) //左子女
nodeQueue.push(pNode->left);
if(pNode->right) //右子女
nodeQueue.push(pNode->right);
cout<<pNode->value<<' ';
}
else if(nodeQueue.size()) //如果结点为空并且队列也为空，那么所有结点都已访问
{
nodeQueue.push(NULL);
cout<<endl;
}
}
}
</div>
扩展二：之前讨论的都是从上往下、从左往右遍历二叉树，那么如果希望自下往上、从左右往右遍历二叉树，该如何修改代码呢？
思路：比较简单的方法，首先遍历二叉树，将所有结点保存在一个数组中，遍历的同时记录每一层在数组中的起止位置。然后根据起止位置，就可以自下往上的打印二叉树的结点。
//每层的起止位置
struct Pos
{
int begin;
int end;
Pos(int b, int e): begin(b),end(e) {}
};
void LevelReverse(BSTreeNode *pRoot)
{
if(pRoot == NULL)
return;
vector<BSTreeNode*> vec; //用以存放所有结点
vector<Pos> pos; //用以记录每层的起止位置
vec.push_back(pRoot);
int level = 0; //树的层数
int cur = 0;
int last = 1;
while(cur < vec.size())
{
last = vec.size();
pos.push_back(Pos(cur, last)); //记录当前层的起止位置
while(cur < last) //遍历当前层的结点，将子女放入数组中
{
if(vec[cur]->left) //先是左然后是右。如果希望自由向左，交换一下顺序即可
vec.push_back(vec[cur]->left);
if(vec[cur]->right)
vec.push_back(vec[cur]->right);
cur++;
}
level++; //层数加1
}
for(int i = level - 1; i >= 0; i--) //自下往上遍历
{
for(int j = pos[i].begin; j < pos[i].end; j++)
cout<<vec[j]->value<<' ';
cout<<endl;
}
}
</div>
输入一颗二元查找树，将该树转换为它的镜像
问题描述：输入一颗二元查找树，将该树转换为它的镜像，即在转换后的二元查找树中，左子树的结点都大于右子树的结点。用递归和循环两种方法完成树的镜像转换。
例如输入：
8 / / 6 10 // // 5 7 9 11</div>
输出：
8 / / 10 6 // // 11 9 7 5</div>
定义二元查找树的结点为：
struct BSTreeNode
{
int value;
BSTreeNode *left;
BSTreeNode *right;
};
</div>
思路：题目要求用两种方法，递归和循环，其实质是一样的。
解法一：用递归。假设当前结点为pNode，只需交换该结点的左右子女，然后分别递归求解左子树和右子树即可。代码极为简单。
解法二：用循环，需要一个辅助栈完成，每次取栈顶元素交换左右子女，然后将左右子女分别压入辅助栈，当栈中元素为空时，结束循环。其实不论是递归也好，循环也好，都是利用栈的特性完成。
参考代码：
//函数功能 ： 输入一颗二元查找树，将该树转换为它的镜像
//函数参数 ： pRoot为根结点
//返回值 ： 根结点
BSTreeNode * Mirror_Solution1(BSTreeNode * pRoot)
{
if(pRoot != NULL)
{
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;
}
</div>
判断整数序列是不是二元查找树的后序遍历结果
问题描述：输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
例如输入5、7、6、9、11、10、8，由于这一整数序列是如下树的后序遍历结果：
8 / / 6 10 / / / / 5 7 9 11</div>
因此返回true。如果输入7、4、6、5，没有哪棵树的后序遍历的结果是这个序列，因此返回false。
思路：分析后序遍历的特点，序列的最后一个数应该是根结点，剩余的节点分为两个连续的子序列，前一子序列的值小于最后一个数，后一子序列的值大于最后一个数。然后递归求解这两个子序列。
如果是判断是前序遍历也很简单，只不过根节点变为了第一个数，剩余的节点也是分为两个连续的子序列。如果判断是中序遍历，更方便，只需扫描一遍，检查序列是不是排好序的，如果没有排好序，就不是中序遍历的结果。
把二元查找树转变成排序的双向链表
问题描述：输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何