二叉树是数据结构——树的一个重要结构，可以实现很多算法，今天就来看一下二叉树的基本实现。
#include <iostream> #include <stack> #include <queue> #include <assert.h> using namespace std; template<class T> struct BinaryTreeNode { T _data; BinaryTreeNode<T>* _left; BinaryTreeNode<T>* _right; BinaryTreeNode(const T& x) :_data(x), _left(NULL), _right(NULL) {} }; 以上为引用的头文件以及二叉树节点对象及其构造函数 template<class T> class BinaryTree { typedef BinaryTreeNode<T> Node; public: BinaryTree(T* a, size_t n,const T& invalid) //为了保证类的封装性，public的成员函数去调用protected的成员函数，意思是这里的函数全是形式上的函数 { size_t index = 0; _root = CreateTree(a,n,invalid,index); } void _PrevOrder() { PrevOrder(_root); cout << endl; } void _PrevOrderNorm() { PrevOrderNorm(_root); } void _LevelOrder() { LevelOrder(_root); } size_t Size() { return _Size(_root); } size_t LeafSize() { return _LeafSize(_root); } size_t GetKLevel(size_t k) { return _GetKLevel(k,_root); } Node* Find(const T& x) { return _Find(_root,x); } size_t Depth() { return _Depth(_root); } protected: //这里的函数才是真正算法的实现 Node* CreateTree(T* a, size_t n, const T& invalid, size_t& index) //运用递归创建一个二叉树 { Node* root = NULL; if ((a[index] != invalid)&&(index < n)) { root = new Node(a[index]); root->_left = CreateTree(a, n, invalid, ++index); root->_right = CreateTree(a, n, invalid, ++index); return root; } return root; } void PrevOrder(Node* root)// 先序遍历递归算法 { if (root == NULL) return; else { cout << root->_data << " "; //根节点 PrevOrder(root->_left);// 先序遍历左子树 PrevOrder(root->_right);// 先序遍历右子树 } } void PrevOrderNorm(Node* root) //先序遍历的非递归算法 { Node* cur = root; stack<Node*> s; while (cur || !s.empty()) { while (cur) { cout << cur->_data << " "; s.push(cur); cur = cur->_left; } Node* top = s.top(); s.pop(); //走到这，top（栈顶）节点的左子树已经遍历完毕，该访问右子树了 cur = top->_right;//访问右子树，又是先序遍历的子问题 } cout << endl; } void LevelOrder(Node* root) //使用队列先进先出的特点实现广度优先遍历 { queue<Node*> q; if (root!=NULL) q.push(root); while (!q.empty()) { Node* front = q.front(); //出队之前保存 cout << front->_data<<" "; q.pop(); if (front->_left != NULL) //出队之后将这个节点“接管”的下一层节点入队 q.push(front->_left); if (front->_right != NULL) q.push(front->_right); } cout << endl; } size_t _Size(Node* root)///获取二叉树节点个数 { if (root == NULL) return 0; else return 1 + _Size(root->_left) + _Size(root->_right); } size_t _LeafSize(Node* root) { if (root == NULL) return 0; else if ((root->_left == NULL) && (root->_right == NULL)) return 1; else return _LeafSize(root->_left) + _LeafSize(root->_right); } size_t _GetKLevel(size_t k, Node* root)//k层节点的个数 { assert(k > 0); if (root == NULL) return 0; else if (k == 1) return 1; else return _GetKLevel(k - 1, root->_left) + _GetKLevel(k - 1, root->_right); } Node* _Find(Node* root, const T& x)//查找值为x的节点 { if (root == NULL) return NULL; if (root->_data == x) return root; Node* left = _Find(root->_left, x); if (left != NULL) return left; else return _Find(root->_right, x); } size_t _Depth(Node* root)//获取深度 { if (root == NULL) return 0; else if (root->_left == NULL&&root->_right == NULL) return 1; else { size_t left = _Depth(root->_left); size_t right = _Depth(root->_right); return left > right ? 1 + left : 1 + right; } } protected: Node* _root; };以上就是一些简单的二叉树操作，其中遍历包括前序中序和后序，但是算法都基本一致，在此不在赘述。其余各算法要领均已经在注释中写明。
以下为测试代码：
void testbinarytree() { int a[10] = {1,2,3,'#','#',4,'#','#',5,6}; BinaryTree<int> t1(a,sizeof(a)/sizeof(a[0]),'#'); t1._PrevOrder(); t1._PrevOrderNorm(); t1._LevelOrder(); cout<<t1.Size()<<endl; cout << t1.LeafSize() << endl; cout << t1.GetKLevel(2) << endl; cout << t1.Find(3) << endl; cout << t1.Depth() << endl; }