树结构及其算法-二叉查找树

目录

树结构及其算法-二叉查找树

C++代码

树结构及其算法-二叉查找树

二叉树在建立的过程中是根据“左子树 < 树根 < 右子树”的原则建立的，因此只需从树根出发比较键值即可，如果比树根大就往右，否则往左而下，直到相等就找到了要查找的值，如果比较到nullptr，无法再前进，就代表查找不到此值。

    TreeNode* Find(TreeNode* tree, int value) {while (true) {if (tree == nullptr)return nullptr;if (tree->data == value)return tree;else if (tree->data > value)tree = tree->leftNode;elsetree = tree->rightNode;}}

C++代码

#include<iostream>
using namespace std;struct TreeNode {int data;TreeNode* leftNode;TreeNode* rightNode;TreeNode(int tempData, TreeNode* tempLeftNode = nullptr, TreeNode* tempRightNode = nullptr) {this->data = tempData;this->leftNode = tempLeftNode;this->rightNode = tempRightNode;}
};class Tree {
private:TreeNode* treeNode;
public:Tree() {treeNode = nullptr;}TreeNode* GetTreeNode() {return this->treeNode;}void AddNodeToTree(int* tempData, int tempSize) {for (int i = 0; i < tempSize; i++) {TreeNode* currentNode;TreeNode* newNode;int flag = 0;newNode = new TreeNode(tempData[i]);if (treeNode == nullptr)treeNode = newNode;else {currentNode = treeNode;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;}}}}}void Inorder(TreeNode* tempTree) {if (tempTree != nullptr) {Inorder(tempTree->leftNode);cout << tempTree->data << " ";Inorder(tempTree->rightNode);}}TreeNode* Find(TreeNode* tree, int value) {while (true) {if (tree == nullptr)return nullptr;if (tree->data == value)return tree;else if (tree->data > value)tree = tree->leftNode;elsetree = tree->rightNode;}}
};int main() {int data[]{ 7,4,1,5,16,8,11,12,15,9,2 };cout << "原始数据：" << endl;for (int i = 0; i < 11; i++)cout << data[i] << " ";cout << endl;Tree* tree = new Tree;tree->AddNodeToTree(data, 11);cout << "中序遍历：" << endl;tree->Inorder(tree->GetTreeNode());cout << endl;cout << "请输入要查找的值：";int value;cin >> value;if ((tree->Find(tree->GetTreeNode(), value)) != nullptr)cout << "您要找的值[" << tree->Find(tree->GetTreeNode(), value)->data << "]找到了" << endl;elsecout << "您要找的值没有找到" << endl;return 0;
}

输出结果