二叉树首先要解决构建问题，才能考虑后续的遍历，这里贴出通过先序构建二叉树，同时包含四种二叉树的遍历方法（先序，中序，后序，逐层）
第一、定义BinaryTreeNode 类
1 #include <iostream> 2 #include <string> 3 #include <queue> 4 using namespace std; 5 6 template<typename T >class BinaryTree; 7 template <typename T> class BinaryTreeNode { 8 public: 9 friend class BinaryTree<T>;10 BinaryTreeNode() {11 data = NULL;12 lChild = rChild = NULL;13 }14 BinaryTreeNode(T newdata) {15 this->data = newdata;16 lChild = rChild = NULL;17 }18 T getData() {19 return data;20 }21 BinaryTreeNode<T> * getLeftNode() {22 return lChild;23 }24 BinaryTreeNode<T> * getRightNode() {25 return rChild;26 }27 T data;28 BinaryTreeNode<T>* lChild;29 BinaryTreeNode<T>* rChild;30 private:31 32 };
第二、定义BinaryTree 类
1 template <typename T> class BinaryTree { 2 public: 3 BinaryTreeNode<T> *root; 4 char* p; 5 BinaryTree() { root = NULL; } 6 BinaryTree(T data) { 7 root = new BinaryTreeNode<T>(data); 8 root->lChild = NULL; 9 root->rChild = NULL; 10 } 11 ~BinaryTree() { 12 delete root; 13 } 14 15 //构建二叉树并返回 16 BinaryTreeNode<T>* CreateTree() { 17 BinaryTreeNode<int>* bt = NULL; 18 char t; 19 cin >> t; 20 if (t == '#') 21 { 22 return NULL; 23 } 24 else { 25 int num = t - '0'; 26 bt = new BinaryTreeNode<T>(num); 27 bt->lChild = CreateTree(); 28 bt->rChild = CreateTree(); 29 } 30 return bt; 31 } 32 33 //先序构建二叉树 34 BinaryTreeNode<T>* PreCreateTree() { 35 BinaryTreeNode<int>* bt = NULL; 36 if (this->root == NULL) 37 { 38 cout << "请输入根节点（#代表空树）:"; 39 } 40 else { 41 cout << "请输入节点（#代表空树）:"; 42 } 43 char t; 44 cin >> t; 45 if (t == '#') 46 { 47 return NULL; 48 } 49 else { 50 int num = t - '0'; 51 bt = new BinaryTreeNode<T>(num); 52 if (this->root == NULL) 53 { 54 this->root = bt; 55 } 56 cout << bt->data << "的左孩子"; 57 bt->lChild = PreCreateTree(); 58 59 cout << bt->data << "的右边孩子"; 60 bt->rChild = PreCreateTree(); 61 } 62 return bt; 63 } 64 65 void preOderTraversal(BinaryTreeNode<T> *bt); //先序遍历 66 void inOrderTraversal(BinaryTreeNode<T> *bt); //中序遍历 67 void postOrderTraversal(BinaryTreeNode<T> *bt);//后序遍历 68 void levelTraversal(BinaryTreeNode<T> *bt); //逐层遍历 69 70 private: 71 72 }; 73 74 template <typename T> 75 void BinaryTree<T>::preOderTraversal(BinaryTreeNode<T> *bt) { 76 if (bt) 77 { 78 cout << bt->data; 79 BinaryTree<T>::preOderTraversal(bt->getLeftNode()); 80 BinaryTree<T>::preOderTraversal(bt->getRightNode()); 81 } 82 } 83 84 template <typename T> 85 void BinaryTree<T>::inOrderTraversal(BinaryTreeNode<T> *bt) { 86 if (bt) 87 { 88 BinaryTree<T>::inOrderTraversal(bt->getLeftNode()); 89 cout << bt->data; 90 BinaryTree<T>::inOrderTraversal(bt->getRightNode()); 91 } 92 } 93 94 template <typename T> 95 void BinaryTree<T>::postOrderTraversal(BinaryTreeNode<T> *bt) { 96 if (bt) 97 { 98 BinaryTree<T>::postOrderTraversal(