二叉查找树（二叉排序树、二叉搜索树）的查找CC++

既然名字都叫二叉查找树，是不是肯定得用来查找嘛。

递归和非递归的

//递归查找 BSTNode* RecursionBSTSearch(BSTNode *root, int ele) { if (root == NULL) { return NULL; } if (ele == root->data) { return root; } if (ele < root->data) { RecursionBSTSearch(root->lChild,ele); } RecursionBSTSearch(root->rChild,ele); } //非递归查找 BSTNode* noRecursionBSTSearch(BSTNode *root, int ele) { BSTNode *cur = root; while (cur != NULL && ele != cur->data) { if (ele < root->data) { cur = cur->lChild; } else { cur = cur->rChild; } } return cur; }

 

全部代码：

#include<stdio.h> #include<stdlib.h> typedef struct BinarySortTreeNode { int data; //数据 struct BinarySortTreeNode * lChild; //左子树 struct BinarySortTreeNode * rChild; //右子树 }BSTNode; //插入节点 void insertNode(BSTNode *&node, int element) { if (NULL == node) { node = new BSTNode; node->data = element; node->lChild = NULL; node->rChild = NULL; } if (element == node->data) { return; } if (element < node->data) { insertNode(node->lChild, element); } if (element > node->data) { insertNode(node->rChild, element); } } //通过 节点数组 初始化二叉查找树 void initBST(BSTNode *&root, int ele[], int len) { if (NULL == ele || 0 == len) { return; } for (int i = 0; i < len; i++) { insertNode(root, ele[i]); } } //释放二叉树 void freeBST(BSTNode *&root) { if (NULL == root) { return; } freeBST(root->lChild); freeBST(root->rChild); delete root; root = NULL; } //递归查找 BSTNode* RecursionBSTSearch(BSTNode *root, int ele) { if (root == NULL) { return NULL; } if (ele == root->data) { return root; } if (ele < root->data) { RecursionBSTSearch(root->lChild,ele); } RecursionBSTSearch(root->rChild,ele); } //非递归查找 BSTNode* noRecursionBSTSearch(BSTNode *root, int ele) { BSTNode *cur = root; while (cur != NULL && ele != cur->data) { if (ele < root->data) { cur = cur->lChild; } else { cur = cur->rChild; } } return cur; } int main() { int eleArr[] = { 5,3,8,7,2,9,1,10,6,4 }; int len = sizeof(eleArr) / sizeof(eleArr[0]); BSTNode *root = NULL; initBST(root, eleArr, len); int element = 10; BSTNode *findNode = RecursionBSTSearch(root,element); if (findNode) { printf("%d - 找到了\n",element); } else { printf("%d - 没找到\n", element); } findNode = noRecursionBSTSearch(root,element); if (findNode) { printf("%d - 找到了\n", element); } else { printf("%d - 没找到\n", element); } freeBST(root); system("pause"); return 0; }

结果：