二叉查找树通俗说就是左孩子比父亲小，右孩子比父亲大。构造这么一个树，树嘛，递归即可。
例如一棵树后序遍历是这样（下图的树）：2 9 8 16 15 10 25 38 45 42 30 20。最后的20肯定是树根，这里要抓住一个规律：20是树根，那么2 9 8 16 15 10都是左子树，25 38 42 45 30在右子树，因为左边都小于根、右边都大于根嘛。然后递归即可。
下面是树的样子和代码和src.txt（后序遍历的结果）以及运行结果：
#include <iostream>
#include <vector>
#include <fstream> using std::cin;
using std::cout;
using std::endl;
using std::vector; #define MY_DEBUG struct Node
{
int data;
Node* pLC;
Node* pRC;
}; Node* creatBSTree(vector<int>& arr)
{
//数组里面没有元素
if (!arr.size())
return nullptr; Node* pNode = new Node;
int thisData = arr.back();
pNode->data = thisData; //只有一个元素就不要折腾了，它就是叶子节点，它没有左右孩子
if ( == arr.size())
{
pNode->pLC = pNode->pRC = nullptr;
return pNode;
} //下面找出左半边
vector<int> arrLeft;
for (int i = ; i < arr.size() - ; i++)
{
if (arr[i] < thisData)
arrLeft.push_back(arr[i]);
else
break;
} //下面找出右半边
vector<int> arrRight;
for (int i = arrLeft.size(); i < arr.size() - ; i++)
arrRight.push_back(arr[i]); #ifdef MY_DEBUG
for (int i = ; i < arrLeft.size(); i++)
cout << arrLeft[i] << " ";
cout << endl; for (int i = ; i < arrRight.size(); i++)
cout << arrRight[i] << " ";
cout << endl << endl;
#endif //递归处理左右孩子。arrLeft和arrRight可能为空，不要紧，在函数的开头处理了
pNode->pLC = creatBSTree(arrLeft);
pNode->pRC = creatBSTree(arrRight); return pNode;
} //中序遍历
void show(Node* pNode)
{
if (!pNode)
return; show(pNode->pLC);
cout << pNode->data << " ";
show(pNode->pRC);
} int main(void)
{
vector<int> arr;
std::ifstream fin("src.txt"); int temp;
while (fin >> temp)
arr.push_back(temp); Node* pHead = creatBSTree(arr);
show(pHead);
cout << endl;
cin.get();
}
由其他的遍历方式得到树的道理类似。
题目：
输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
分析：
这不是很简单了嘛，由最后的根把输入分成三份，第一份是左孩子，第二份是右孩子，最后是树根。7、4、6、5就不能构成了，因为5是根，那么7,4,6都是右子树里面的，但是里面有小于5的4，所以不行。递归即可。
题目：
输入一棵二元查找树，将该二元查找树转换成一个排序的双向链表。要求不能创建任何新的结点，只调整指针的指向。
例如如果树如上图，那么得到的链表是 2=8=9=……=42=45。
分析：
树嘛，递归就是啦。
如上树，先递归处理左子树（根为10的树），处理完左子树就成了一个链表了，并要能够返回左子树的最大节点16；然后递归处理右子树（根为30的树），处理完右子树也成了一个有序链表，并返回右子树的最小节点25，然后把16、20、25串起来，不就是链表了嘛？
这里要注意一点：在处理根为20的树时，这是不是要递归处理根为10的左子树嘛，那么这个左子树怎么知道它要返回16节点呢？同样对于20的右子树，它怎么知道返回25以和20串起来呢？所以在处理子树的时候，要传给它一个标志，表明它是父亲的左子树还是右子树。我在这里纠结好久……
代码：
#include <iostream>
#include <set>
#include <fstream>
#include <queue> using std::cin;
using std::cout;
using std::endl;
using std::set;
using std::vector; struct Node
{
int data;
Node* pLC;
Node* pRC;
}; Node* creatBSTree(vector<int>& arr)
{
//数组里面没有元素
if (!arr.size())
return nullptr; Node* pNode = new Node;
int thisData = arr.back();
pNode->data = thisData; //只有一个元素就不要折腾了，它就是叶子节点，它没有左右孩子
if ( == arr.size())
{
pNode->pLC = pNode->pRC = nullptr;
return pNode;
} //下面找出左半边
vector<int> arrLeft;
for (int i = ; i < arr.size() - ; i++)
{
if (arr[i] < thisData)
arrLeft.push_back(arr[i]);
else
break;
} //下面找出右半边
vector<int> arrRight;
for (int i = arrLeft.size(); i < arr.size() - ; i++)
arrRight.push_back(arr[i]); #ifdef MY_DEBUG
for (int i = ; i < arrLeft.size(); i++)
cout << arrLeft[i] << " ";
cout << endl; for (int i = ; i < arrRight.size(); i++)
cout << arrRight[i] << " ";
cout << endl << endl;
#endif //递归处理左右孩子。arrLeft和arrRight可能为空，不要紧，在函数的开头处理了
pNode->pLC = creatBSTree(arrLeft);
pNode->pRC = creatBSTree(arrRight); return pNode;
} //中序遍历
void show(Node* pNode)
{
if (!pNode)
return; show(pNode->pLC);
cout << pNode->data << " ";
show(pNode->pRC);
} //这个函数多传了一个参数 asLeft，表明树根是树根的左子树还是右子树
//因为如果是左子树的话，那么要返回左子树最大节点，右子树要返回最小节点
//不要这个标志的话 pNode 不知道指向的树到底是父亲的左子树还是右子树
Node* letStraight(Node* pNode, bool asLeft)
{
//如果是空树或者只是一个叶子节点，返回自身
if (!pNode || (!pNode->pLC && !pNode->pRC))
return pNode; //递归处理左右子树
Node* pLMax = nullptr;
if (pNode->pLC)
pLMax = letStraight(pNode->pLC, true); Node* pRMin = nullptr;
if (pNode->pRC)
pRMin = letStraight(pNode->pRC, false); //连接左子树、右子树、树根
if (pLMax)
{
pNode->pLC = pLMax;
pLMax->pRC = pNode;
}
if (pRMin)
{
pNode->pRC = pRMin;
pRMin->pLC = pNode;
} //返回值处理，注意 asLeft 表明这棵树是它父亲的左子树还是右子树，所以它要重新找到合适的返回节点
// pNode 的左孩子最大或右孩子最小并不是它要返回的值，它要返回的还是要看这整棵树，而不是单单看左右孩子
Node* pRetutnNode = pNode;
if (asLeft)
{
while (pRetutnNode->pRC)
pRetutnNode = pRetutnNode->pRC;
}
else
{
while (pRetutnNode->pLC)
pRetutnNode = pRetutnNode->pLC;
}
return pRetutnNode;
} int main(void)
{
vector<int> arr;
std::ifstream fin("src.txt"); int temp;
while (fin >> temp)
arr.push_back(temp); Node* pHead = creatBSTree(arr);
show(pHead);
cout << endl; //顺序链表化并返回第一个节点
pHead = letStraight(pHead, false);
while (pHead)
{
cout << pHead->data << " ";
pHead = pHead->pRC;
}
cout << endl; cin.get();
}
结果：
