思路

?叉搜索樹是?個有序樹：
若它的左?樹不空，則左?樹上所有結點的值均?于它的根結點的值；
若它的右?樹不空，則右?樹上所有結點的值均?于它的根結點的值；
它的左、右?樹也分別為?叉搜索樹

遞歸法

class Solution { public:TreeNode* searchBST(TreeNode* root, int val) {if(root==nullptr||val==root->val) return root;//遞歸終止條件，如果root為空，或者找到這個數值了，就返回root節點。if(val>root->val){return searchBST(root->right,val);}elsereturn searchBST(root->left,val);} };

迭代法

?叉搜索樹的特殊性，也就是節點的有序性，可以不使?輔助棧或者隊列就可以寫出迭代法。
對于?般?叉樹，遞歸過程中還有回溯的過程，例如??個左?向的分??到頭了，那么要調頭，在?右分?。?對于?叉搜索樹，不需要回溯的過程，因為節點的有序性就幫我們確定了搜索的?向。
例如要搜索元素為3的節點，我們不需要搜索其他節點，也不需要做回溯，查找的路徑已經規劃好了。

/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/ class Solution { public:TreeNode* searchBST(TreeNode* root, int val) {while(root!=nullptr){if(val==root->val) return root;else if(val>root->val) root=root->right;else if(val<root->val) root=root->left; }return NULL;} };

總結

本篇我們介紹了?叉搜索樹的遍歷?式，因為?叉搜索樹的有序性，遍歷的時候要?普通?叉樹簡單很多。但是?些同學很容易忽略?叉搜索樹的特性，所以寫出遍歷的代碼就未必真的簡單了。
所以針對?叉搜索樹的題?，?樣要利?其特性。

總結

以上是生活随笔為你收集整理的二叉搜索树中的搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。