首页 > 代码库 > 二叉查找树-查找的函数
二叉查找树-查找的函数
二叉查找树的定义是：
树中每一个根节点的左子树上的数据全部都小于根节点的数据，右子树都大于根节点的数据。
例图（XMind）：
现在没看到二叉查找树如何动态构建，因此先手动构造了上述树，先把递归查找的函数贴出来
SearchTree.cpp
1 #include "iostream" 2 #include "stdlib.h" 3 4 #define log(s); std::cout<<s; 5 6 typedef struct _btree_ 7 { 8 int data; 9 struct _btree_ *left;10 struct _btree_ *right;11 }BTree;12 13 BTree *createNode(int data)14 {15 BTree *p = (BTree *)malloc(sizeof(BTree));16 p->data =http://www.mamicode.com/ data;17 p->left = nullptr;18 p->right = nullptr;19 return p;20 }21 22 BTree *findKey(BTree *father,int data)23 {24 if (father->data < data)25 return findKey(father->right, data);26 else if (father->data>data)27 return findKey(father->left, data);28 else29 return father;30 }31 32 BTree *findMax(BTree *root)33 {34 if (root->right == nullptr)35 return root;36 else37 return findMax(root->right);38 }39 40 BTree *findMin(BTree *root)41 {42 if (root->left == nullptr)43 return root;44 else45 return findMin(root->left);46 }47 48 BTree *createTree(BTree *&root)49 {50 BTree *t1, *t2, *t3, *t4, *t6, *t7, *t8, *t9, *t10;51 t1 = createNode(1);52 t2 = createNode(4);53 t3 = createNode(3);54 t4 = createNode(2);55 t6 = createNode(7);56 t7 = createNode(5);57 t8 = createNode(9);58 t9 = createNode(8);59 t10 = createNode(12);60 root->left = t4;61 root->right = t6;62 t4->left = t1;63 t4->right = t2;64 t2->left = t3;65 t6->left = t7;66 t6->right = t8;67 t8->left = t9;68 t8->right = t10;69 return root;70 }71 72 void showResult(BTree *node)73 {74 if (node == nullptr)75 return;76 std::cout << node->data << std::endl;77 }78 79 int main(void)80 {81 BTree *root = nullptr;82 BTree *result = nullptr;83 root = createNode(6);84 root = createTree(root);85 result = findKey(root,6);86 log("查找结果：");87 showResult(result);88 result = findMax(root);89 log("最大值：");90 showResult(result);91 result = findMin(root);92 log("最小值：");93 showResult(result);94 system("pause");95 return 0;96 }
因为二叉查找树是在数据已经排序好的基础上进行构建的，因此我认为等到学了排序算法后应该能实现一个动态实现的查找树。
补充一下，对于最大最小的查找还有一种非递归查找的方法，函数如下：
1 BTree *findMax(BTree *root)2 {3 if (root != nullptr)4 while (root->right != nullptr)5 root = root->right;6 return root;7 }
以上函数未经严格测试，如有错误希望读者不吝赐教，不胜感激。
以上。
二叉查找树-查找的函数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。