二叉树

二叉树的先序遍历，后续遍历，中序遍历，层序遍历

#include <iostream> using namespace std; #include<deque> template <class T> class TreeNode { public: TreeNode<T>* pLeft; TreeNode<T>* pRight; T data; TreeNode(T t) :data(t), pLeft(NULL), pRight(NULL) {} ~TreeNode() {}; }; template <class T> class BinaryTree { public: TreeNode<T>* root; BinaryTree() { root = new TreeNode<T>(0); } void InOrder(); void InOrder(TreeNode<T>*); void PreOrder(); void PreOrder(TreeNode<T>*); void PostOrder(); void PostOrder(TreeNode<T>*); void LevelOrder(); void Visit(TreeNode<T>*current) { cout << current->data << " "; } }; //中序 template <class T> void BinaryTree<T>::InOrder() { InOrder(root); } //先序 template <class T> void BinaryTree<T>::PreOrder() { PreOrder(root); } //后序 template <class T> void BinaryTree<T>::PostOrder() { PreOrder(root); } //层序 template <class T> void BinaryTree<T>::LevelOrder() { deque<TreeNode<T>*> q; TreeNode<T>* currentNode = root; while (currentNode) { Visit(currentNode); if (currentNode->pLeft) q.push_back(currentNode->pLeft); if (currentNode->pRight) q.push_back(currentNode->pRight); if (q.empty())return; currentNode = q.front(); q.pop_front(); } } template <class T> void BinaryTree<T>::InOrder(TreeNode<T>* current) { if (!current) return; InOrder(current->pLeft); Visit(current); InOrder(current->pRight); } template <class T> void BinaryTree<T>::PreOrder(TreeNode<T>* current) { if (!current) return; Visit(current); PostOrder(current->pLeft); PostOrder(current->pRight); } template <class T> void BinaryTree<T>::PostOrder(TreeNode<T>* current) { if (!current) return; PreOrder(current->pLeft); PreOrder(current->pRight); Visit(current); } int main() { BinaryTree<int> bt; bt.root->data = 100; TreeNode<int> left(10); bt.root->pLeft = &left; TreeNode<int> right(1000); bt.root->pRight = &right; TreeNode<int> rright(1500); bt.root->pRight->pRight = &rright; TreeNode<int> lleft(8); bt.root->pLeft->pLeft = &lleft; TreeNode<int> lright(80); bt.root->pLeft->pRight = &lright; TreeNode<int> rleft(500); bt.root->pRight->pLeft = &rleft; bt.InOrder(); cout << endl; bt.PreOrder(); cout << endl; bt.PostOrder(); cout << endl; bt.LevelOrder(); cout << endl; while (1); return 0; }

执行结果