数据结构树4-二叉搜索树2

二叉搜索树.h:  

#ifndef _二叉查找树_H #define _二叉查找树_H #include<iostream> #include<string> enum Boolean{ FALSE,TRUE}; template<class Type> class Element { public: Type key; //方便添加更新数据 }; // 错误我的写法：template<class Type> BinaryTree; template<class Type> class BinaryTree; //前置声明 template<class Type> class BinaryNode { friend class BinaryTree<Type>; public: Element<Type> data; BinaryNode* leftChild; BinaryNode* rightChild; void display(int i); }; template<class Type> class BinaryTree { private: BinaryNode<Type> * root; public: BinaryTree(BinaryNode<Type> *init = 0) { root = init; } Boolean Insert(const Element<Type>& x); BinaryNode<Type>* Search(const Element<Type>& x); BinaryNode<Type>* Search(BinaryNode<Type>*,const Element<Type>&); BinaryNode<Type>* IterSearch(const Element<Type>&); //增加删除 //增加遍历 void display() { cout << "\n"; if (root) root->display(1); else cout << "这是一棵空树" << "\n"; } }; //显示当前结点的数据及左子树右子树中的数据 template<class Type> void BinaryNode<Type>::display(int i) { std::cout << "Position:" << i << ",key:" << data.key << "\n"; if (leftChild) leftChild->display(2 * i); if (rightChild) rightChild->display(2 * i + 1); } //我写的 //template<class Type> //Boolean BinaryTree<Type>::Insert(const Element<Type>& x) //{ // BinaryNode<Type> *p = root; // BinaryNode<Type> *q =0; //q指向p的父结点 // if (x == p->data.key) return; // while (p) // { // q = p; // if (x > p->rightChild->data.key) // p = p->rightChild; // else // p = p->leftChild; // } // BinaryNode<Type>* newNode = new BinaryNode<Type>; // newNode->data.key = x; // newNode->rightChild = 0; // newNode->leftChild = 0; // if (x > q->data.key) // q->rightChild = newNode; // else // q->leftChild = newNode; //} template<class Type> Boolean BinaryTree<Type>::Insert(const Element<Type> &x) { BinaryNode<Type> *p = root; BinaryNode<Type> *q = 0; //q指向p的父结点 //insert前先查找 while (p) { q = p; if (x.key == p->data.key) return FALSE; //发生重复，失败返回FALSE if (x.key > p->data.key) p = p->rightChild; else p = p->leftChild; } //找到的位置就是q BinaryNode<Type> *newNode = new BinaryNode<Type>; newNode->data = x; newNode->rightChild = newNode->leftChild = 0; if (!root) root = newNode; else if (x.key > q->data.key) q->rightChild = newNode; else q->leftChild = newNode; return TRUE; } //我写的 //template<class Type> //BinaryNode<Type>* BinaryTree<Type>::IterSearch(const Element<Type>& x) //{ // BinaryNode<Type>* node, // node = root; // while (node) 用while错误？？？不知道为什么 // { // if (node->data.key == x) // return node; // if (node->data.key > x) // node = node->rightChild; // else // node = node->leftChild; // } // //} template<class Type> BinaryNode<Type>* BinaryTree<Type>::IterSearch(const Element<Type>& x) { for (BinaryNode<Type>* node = root; node;) { if (x.key==node->data.key ) return node; if (x.key>node->data.key) node = node->rightChild; else node = node->leftChild; } return 0; } //完全不会 template<class Type> BinaryNode<Type>* BinaryTree<Type>::Search(const Element<Type>&x) //查找某个数--》从root结点开始的树中的数 { return Search(root, x); } template<class Type> BinaryNode<Type>* BinaryTree<Type>::Search(BinaryNode<Type>* node, const Element<Type>&x) { if (!node) return 0; else if (x.key == node->data.key) return node; else if (x.key < node->data.key) return Search(node->leftChild, x); else return Search(node->rightChild, x); } #endif

test.h:

#include<iostream> #include<string> #include"二叉查找树.h" using namespace std; int main() { //我的错误写法 Element<Type> a; BinaryTree<int> m; Element<int> a,b,c,d,e,f,g,h,i,j,k,l; a.key = 5; b.key = 3; c.key = 11; d.key = 3; e.key = 15; f.key = 2; g.key = 8; h.key = 22; i.key = 20; j.key = 9; cout<<m.Insert(a)<<endl; cout<<m.Insert(b)<<endl; cout << m.Insert(c) << endl; cout << m.Insert(d) << endl; cout << m.Insert(e) << endl; cout << m.Insert(f) << endl; cout << m.Insert(g) << endl; cout << m.Insert(h) << endl; cout << m.Insert(i) << endl; cout << m.Insert(j) << endl; m.display(); BinaryNode<int> *node=m.IterSearch(f); cout << "node->data.key:" << node->data.key << endl; BinaryNode<int> *node1 = m.Search(e); cout << "node1->data.key:" << node1->data.key << endl; return 0; }

运行结果：