特征
1.左子树上所有结点的值均小于或等于它的根结点的值
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
如下就是一棵典型的二叉查找树
因为查找使用二分查找法，所以查询时间复杂度是 O(lg2)
操作
二叉树的操作也就是增删查、遍历
查找就是二分查找。增添节点和删除节点的时候，要保持二叉树的性质。
遍历分为前序遍历(preorder travel)、中序遍历(inorder travel)、后续遍历(postorder travel)
前序遍历就是根节点第一个被遍历，按照“中左右”顺序，子树也按照这个顺序。中序按照“左中右”顺序。后续按照“左右中”顺序。
可以看到，前序就是根节点第一个被遍历，中序就是根节点在中间被遍历，后续就是根节点最后被遍历。都是针对根节点的。
通过前序+中序、后序+中序 可以还原一棵树。
比如上面这棵树，前序遍历：3102645，中序遍历：0123465
通过前序可以看到3是根节点，再看中序，3前面的 012 就是左子树，3后面的 456 就是右子树。继续看前序，1是左子树的根节点，6是右子树的根节点...依次类推，递归下去。
#include#include #include #include #include #include
#include enum EColor{ WHITE = 0, BLACK,};template struct stTreeNode{ T d; int color; struct stTreeNode *left, *right; stTreeNode(T data):d(data),color(WHITE),left(NULL),right(NULL) {}};template class CTree{public: typedef T value_type; typedef T& reference; typedef T* pointer; typedef stTreeNode node_type; typedef node_type* node_pointer; CTree():root(NULL){} CTree(const pointer arr, int len); void insert(value_type data); void del(value_type data); node_pointer find(value_type data); bool empty() { return root == NULL;}; int height(); void preorderTravel(); void inorderTravel(); void postorderTravel(); void layerTravle();private: node_pointer root; void _insert(node_pointer *root, value_type data); int _height(node_pointer root);};template CTree ::CTree(const CTree ::pointer arr, int len){ root = NULL; for (int i = 0; i < len; ++i) { _insert(&root, arr[i]); }}template void CTree ::_insert(CTree ::node_pointer *root, CTree ::value_type data){ if (*root == NULL) { *root = new CTree ::node_type(data); } else if (data > (*root)->d) { _insert(&(*root)->right, data); } else { _insert(&(*root)->left, data); }}template void CTree ::insert(CTree ::value_type data){ _insert(&this->root, data);}template typename CTree ::node_pointer CTree ::find(CTree ::value_type data){ CTree ::node_pointer tmp = root; while (tmp != NULL) { if (tmp->d == data) { return tmp; } else if (data > tmp->d) { tmp = tmp->right; } else { tmp = tmp->left; } } return tmp;}template void CTree ::del(CTree ::value_type data){ CTree ::node_pointer parent = root; CTree ::node_pointer tmp = root; int left = -1; while (tmp != NULL && tmp->d != data) { parent = tmp; if (data > tmp->d) { tmp = tmp->right; left = 0; } else { tmp = tmp->left; left = 1; } } if (!tmp) { return; } // 要删除的节点没有左子树 if (!tmp->left) { if (left) { parent->left = tmp->right; } else { parent->right = tmp->right; } } else { CTree ::node_pointer cur = tmp; parent = tmp; tmp = tmp->left; while (tmp->right != NULL) { parent = tmp; tmp = tmp->right; } cur->d = tmp->d; if (parent->left == tmp) { parent->left = tmp->left; } else { parent->right = tmp->left; } delete tmp; }}template void CTree ::preorderTravel(){ std::stack ::node_pointer, std::list ::node_pointer> > S; if (root) { S.push(root); } while (!S.empty()) { CTree ::node_pointer node = S.top(); std::cout << node->d << " "; S.pop(); if (node->right) { S.push(node->right); } if (node->left) { S.push(node->left); } } std::cout << std::endl;}template void CTree ::inorderTravel(){ std::stack ::node_pointer, std::list ::node_pointer> > S; if (root) { S.push(root); } while (!S.empty()) { CTree ::node_pointer node = S.top(); if (node->left && node->left->color == WHITE) { S.push(node->left); } else { std::cout << node->d << " "; node->color = BLACK; S.pop(); if (node->right) { S.push(node->right); } } } std::cout << std::endl;}template void CTree ::postorderTravel(){ std::stack ::node_pointer, std::list ::node_pointer> > S; if (root) { S.push(root); } while (!S.empty()) { CTree ::node_pointer node = S.top(); int nextTra = 1; if (node->right && node->right->color == WHITE) { S.push(node->right); nextTra = 0; } if (node->left && node->left->color == WHITE) { S.push(node->left); nextTra = 0; } if (nextTra) { std::cout << node->d << " "; node->color = BLACK; S.pop(); } } std::cout << std::endl;}template void CTree ::layerTravle(){ std::queue ::node_pointer, std::list ::node_pointer> > Q; if (root) { Q.push(root); } while (!Q.empty()) { CTree ::node_pointer node = Q.front(); std::cout << node->d << " "; Q.pop(); if (node->left) { Q.push(node->left); } if (node->right) { Q.push(node->right); } } std::cout << std::endl;}template int CTree ::_height(CTree ::node_pointer root){ if (root == NULL) { return 0; } int lh = _height(root->left); int rh = _height(root->right); return lh > rh ? lh + 1 : rh + 1;}template int CTree ::height(){ return _height(root);}int main(){ int arr[] = { 6,3,4,1,3,8,9,7,6,0,2}; int len = sizeof(arr)/sizeof(int); CTree tree(arr, len); tree.preorderTravel(); tree.postorderTravel(); tree.layerTravle(); printf("%d\n", tree.height()); return 0;}