二叉排序樹又稱二叉查找樹

非遞歸實現BST的查找操作空間復雜度為O(1)，但是遞歸實現的空間復雜度為O(h)?，h為樹的高度

#include <iostream> using namespace std; typedef struct BSTNode{int key;struct BSTNode *lchild,*rchild; }BSTNode,*BSTree;//非遞歸，空間復雜度為O(1) BSTNode *BST_Search(BSTree T,int key){while(T!=NULL&&key!=T->key){if(key<T->key)T=T->lchild;elseT=T->rchild;}return T; }//遞歸，空間復雜度為O(h) BSTNode *BSTSearch(BSTree T,int key){if(T==NULL)return NULL;if(key==T->key)return T;else if(key<T->key)return BSTSearch(T->lchild,key);elsereturn BSTSearch(T->rchild,key); }

?

總結

以上是生活随笔為你收集整理的递归和非递归实现二叉排序树（BST）的查找操作的全部內容，希望文章能夠幫你解決所遇到的問題。

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