目录

树结构及其算法-二叉排序树

C++代码

---

树结构及其算法-二叉排序树

事实上，二叉树是一种很好的排序应用模式，因为在建立二叉树的同时，数据已经经过初步的比较，并按照二叉树的建立规则来存放数据，规则如下：

1. 第一个输入数据当作此二叉树的树根。
2. 之后的数据以递归的方式与树根进行比较，小于树根置于左子树，大于树根置于右子树。

从上面的规则可以知道，左子树内的值一定小于树根，而右子树的值一定大于树根。因此，只要利用中序遍历方式就可以得到从小到大排序好的数据，如果想从大到小排序，那么可将最后的结果置于堆栈内，再依次弹出即可。

C++代码

#include<iostream>
using namespace std;struct TreeNode {int data;TreeNode* leftNode;TreeNode* rightNode;TreeNode() {data = 0;leftNode = nullptr;rightNode = nullptr;}TreeNode(int tempData, TreeNode* tempLeftNode = nullptr, TreeNode* tempRightNode = nullptr) {this->data = tempData;this->leftNode = tempLeftNode;this->rightNode = tempRightNode;}
};namespace Tree {TreeNode* CreateTree(int* tempData, int tempSize) {TreeNode* tempTreeNode = nullptr;for (int i = 0; i < tempSize; i++) {TreeNode* currentNode;TreeNode* newNode;int flag = 0;newNode = new TreeNode(tempData[i]);if (tempTreeNode == nullptr)tempTreeNode = newNode;else {currentNode = tempTreeNode;while (!flag) {if (tempData[i] < currentNode->data) {if (currentNode->leftNode == nullptr) {currentNode->leftNode = newNode;flag = 1;}elsecurrentNode = currentNode->leftNode;}else {if (currentNode->rightNode == nullptr) {currentNode->rightNode = newNode;flag = 1;}elsecurrentNode = currentNode->rightNode;}}}}return tempTreeNode;}void Inorder(TreeNode* tempTree) {if (tempTree != nullptr) {Inorder(tempTree->leftNode);cout << tempTree->data << " ";Inorder(tempTree->rightNode);}}
};int main() {int data[]{ 6, 3, 5, 9, 7, 8, 4, 2 };cout << "原始数据：" << endl;for (int i = 0; i < 8; i++)cout << data[i] << " ";cout << endl;TreeNode* treeNode = nullptr;treeNode = Tree::CreateTree(data, 8);cout << "排序结果：" << endl;Tree::Inorder(treeNode);return 0;
}

输出结果