数据结构示例(五)——二叉搜索树.doc

#includeusing namespace std;templatestruct TreeNode T data; TreeNode *left, *right;templateclass BSTree /: public BinaryTree public: BSTree():root(NULL); BSTree() destroy(root); TreeNode *Find(const T &x);/ TreeNode *Find(const T &x) return Find(root, x) void Delete(TreeNode*& node); void FindAndDelete(const T &x); void Insert(const T &x); / void Insert(const T &x) Insert(root, x); void PreOrder() PreOrder(root); void InOrder() InOrder(root); private: TreeNode *root; void destroy(TreeNode *t); void PreOrder(TreeNode *t); void InOrder(TreeNode *t);/ void Insert(TreeNode* &ptr, const T &x);/ TreeNode *Find(TreeNode *t, const T &x); ;templateTreeNode* BSTree:Find(const T &x) TreeNode *temp = root; while(temp) if(temp-data = x) return temp; else if(temp-data right; else temp = temp-left; return NULL;/查找的递归写法templateTreeNode* BSTree:Find(TreeNode* t, const T &x) if(t = NULL) return NULL; if(t-data = x) return t; else if(t-data x) return Find(t-left, x); else return Find(t-right, x); templatevoid BSTree:Insert(const T &x) TreeNode *p = root, *q = 0; while(p) q = p; if(p-data = x) return; else if(p-data right; else p = p-left; TreeNode *r = new TreeNode; r-data = x; r-left = r-right = NULL; if(root) if(x data) q-left = r; else q-right = r; else root = r;/插入的递归程序templatevoid BSTree:Insert(TreeNode* &ptr, const T &x) if(ptr = NULL) ptr = new TreeNode; ptr-data = x; else if(x data) Insert(ptr-left, x); else Insert(ptr-right, x);templatevoid BSTree:Delete(TreeNode*& node) TreeNode *p, *q=node; if(node-right=0) node=node-left; else if(node-left=0) node=node-right; else p = node; q = node-left; while(q-right) p = q; q = q-right; node-data = q-data; if(p=node) p-left = q-left; else p-right = q-left; delete q;templatevoid BSTree:FindAndDelete(const T &x) TreeNode *node = root, *p = 0; while(node) if(node-data = x) break; p = node; if(node-data right; else node = node-left; if(node != 0 & node-data = x) if(node = root) Delete(root); else if(p-left=node) Delete(p-left); else Delete(p-right); else if(root != 0) coutx不在二叉树中n; else cout二叉树为空n;templatevoid BSTree:destroy(TreeNode *t) if(t) destroy(t-left); destroy(t-right); delete t; templatevoid BSTree:PreOrder(TreeNode *t) if(t) coutdataleft); PreOrder(t-right); templatevoid BSTree:InOrder(TreeNode *t) if(t) InOrder(t-left); coutdataright); int main() BSTree a; a.Insert(50); a.Insert(40); a.Insert(70); a.Insert(10); a.Insert(