首页 > 代码库 > 由后序遍历结果构造二叉查找树
由后序遍历结果构造二叉查找树
<style></style>
二叉查找树通俗说就是左孩子比父亲小，右孩子比父亲大。构造这么一个树，树嘛，递归即可。
例如一棵树后序遍历是这样（下图的树）：2 9 8 16 15 10 25 38 42 45 30 20。最后的20肯定是树根，这里要抓住一个规律：20是树根，那么2 9 8 16 15 10都是左子树，25 38 42 45 30在右子树，因为左边都小于根、右边都大于根嘛。然后递归即可。
下面是树的样子和代码和src.txt（后序遍历的结果）以及运行结果：
1 #include <iostream> 2 #include <vector> 3 #include <fstream> 4 5 using std::cin; 6 using std::cout; 7 using std::endl; 8 using std::vector; 9 10 #define MY_DEBUG11 12 struct Node13 {14 int data;15 Node* pLC;16 Node* pRC;17 };18 19 Node* creatBSTree(vector<int>& arr)20 {21 //数组里面没有元素22 if (!arr.size())23 return nullptr;24 25 Node* pNode = new Node;26 int thisData =http://www.mamicode.com/ arr.back();27 pNode->data =http://www.mamicode.com/ thisData;28 29 //只有一个元素就不要折腾了，它就是叶子节点，它没有左右孩子30 if (1 == arr.size())31 {32 pNode->pLC = pNode->pRC = nullptr;33 return pNode;34 }35 36 //下面找出左半边37 vector<int> arrLeft;38 for (int i = 0; i < arr.size() - 1; i++)39 {40 if (arr[i] < thisData)41 arrLeft.push_back(arr[i]);42 else43 break;44 }45 46 //下面找出右半边47 vector<int> arrRight;48 for (int i = arrLeft.size(); i < arr.size() - 1; i++)49 arrRight.push_back(arr[i]);50 51 #ifdef MY_DEBUG52 for (int i = 0; i < arrLeft.size(); i++)53 cout << arrLeft[i] << " ";54 cout << endl;55 56 for (int i = 0; i < arrRight.size(); i++)57 cout << arrRight[i] << " ";58 cout << endl << endl;59 #endif60 61 //递归处理左右孩子。arrLeft和arrRight可能为空，不要紧，在函数的开头处理了62 pNode->pLC = creatBSTree(arrLeft);63 pNode->pRC = creatBSTree(arrRight);64 65 return pNode;66 }67 68 69 //中序遍历70 void show(Node* pNode)71 {72 if (!pNode)73 return;74 75 show(pNode->pLC);76 cout << pNode->data << " ";77 show(pNode->pRC);78 }79 80 int main(void)81 {82 vector<int> arr;83 std::ifstream fin("src.txt");84 85 int temp;86 while (fin >> temp)87 arr.push_back(temp);88 89 Node* pHead = creatBSTree(arr);90 show(pHead);91 cout << endl;92 cin.get();93 }
2 9 8 16 15 10 25 38 42 45 30 20
由其他的遍历方式得到树的道理类似。
题目：
输入一个整数数组，判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true，否则返回false。
分析：
这不是很简单了嘛，由最后的根把输入分成三份，第一份是左孩子，第二份是右孩子，最后是树根。7、4、6、5就不能构成了，因为5是根，那么7,4,6都是右子树里面的，但是里面有小于5的4，所以不行。递归即可。
由后序遍历结果构造二叉查找树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。