基础的数据结构一般都会包含插入、删除、查找和修改等几个基本的操作。对于搜索二叉树而言，数据的插入和删除操作都是在叶子结点进行。搜索二叉树主要方便于数据的查找，其查找算法复杂度为O(h)，h表示其树高，而二叉树的高度h在lgN和N之间，因此，查找算法强烈依赖于树形的好坏，而树形的好坏与数据的增长有关。对于好的数据输入，二叉树可以是平衡的高度为lgN，然而很难保证都是这种情况。对于坏的数据输入二叉树甚至可能退化成链表，其查找的复杂度为N，这是我们最不希望看到的。
本文以C++作为算法语言编写二叉树的一个模版BinarySearchTree<T>，T可以是任何基础数据类型，在linux环境下g++编译通过。
#ifndef _BINARYSEARCHTREE_#define _BINARYSEARCHTREE_#include#include template struct Node{ T data; Node* left; Node* right; Node (T node=0):data(node){}};template class BinarySearchTree{private: Node * root; unsigned int size; int num;public: BinarySearchTree();//:root(NULL){} ~BinarySearchTree();private: void destroyTree(Node *);public: Node * getRootNode(); unsigned int getSize(); bool createTree(T d); bool addNode(T d); const Node * findNode(T d,Node * &) const; void preorderdisplayNode(Node *); void inorderdisplayNode(Node *); void postorderdisplayNode(Node *);};template BinarySearchTree ::BinarySearchTree():root(NULL),size(0),num(0){} template BinarySearchTree ::~BinarySearchTree(){ destroyTree(getRootNode());} template Node * BinarySearchTree ::getRootNode(){ Node * rootNode=this->root; return rootNode;}template unsigned int BinarySearchTree ::getSize(){ return this->size;}template void BinarySearchTree ::destroyTree(Node * node){ if(!node){ delete node; destroyTree(node->left); destroyTree(node->right); }}template bool BinarySearchTree ::createTree(T d){ if(!this->root){ this->root=new Node (d); size++; this->root->left=NULL; this->root->right=NULL; return true; } else{ return true; } }template bool BinarySearchTree ::addNode(T d){ Node * parent= this->getRootNode(); if(!parent){ printf("error,the tree is empty!\n"); return false; } Node * iPtr=parent; Node * tmp=NULL; while(iPtr){ if(d<=iPtr->data){ tmp=iPtr; iPtr=iPtr->left; } else if(d>iPtr->data){ tmp=iPtr; iPtr=iPtr->right; } else{ throw "something error!"; } } if(d>tmp->data){ tmp->right=new Node (d); size++; } else{ tmp->left= new Node (d); size++; } return true; }template const Node * BinarySearchTree ::findNode(T d,Node * &node) const{ Node * tmpNode=node; if(!tmpNode) return tmpNode; if(d>tmpNode->data){ tmpNode=tmpNode->right; findNode(d,tmpNode); return tmpNode; } else if(d data){ tmpNode=tmpNode->left; findNode(d,tmpNode); return tmpNode; } else if(d==tmpNode->data){ return tmpNode; } else { return NULL; }}template void BinarySearchTree ::inorderdisplayNode(Node * node){ Node * tmpPtr=node; if(tmpPtr){ inorderdisplayNode(tmpPtr->left); printf("%d ",tmpPtr->data); inorderdisplayNode(tmpPtr->right); } num=0;}template void BinarySearchTree ::preorderdisplayNode(Node * node){ Node * tmpPtr=node; if(tmpPtr){ printf("%d ",tmpPtr->data); preorderdisplayNode(tmpPtr->left); preorderdisplayNode(tmpPtr->right); } num=0;}template void BinarySearchTree ::postorderdisplayNode(Node * node){ Node * tmpPtr=node; if(tmpPtr){ postorderdisplayNode(tmpPtr->left); postorderdisplayNode(tmpPtr->right); printf("%d ",tmpPtr->data); } num=0;}#endif //binarysearchtree.h
#include#include"searchbinarytree.h"using namespace std;int main(){ BinarySearchTree Tree1; Tree1.createTree(5); Tree1.addNode(4); Tree1.addNode(7); Tree1.addNode(1); Tree1.addNode(2); Tree1.addNode(0); Tree1.addNode(3); Tree1.addNode(6); Tree1.addNode(8); Tree1.addNode(9); cout<<"inorder display node:"<
对于一组数据，这里以0~9为例，不同的输入将造成树形的不同，从而影响查找数据的效率。
高度为4
高度为10，此时二叉树退化成链表，其查找算法复杂度和链表一样。