数据结构-二叉树的遍历实现笔记C++

二叉树的遍历实现，可以用递归的方法也可以用非递归的方法。非递归的方法可以借助栈（前序遍历，中序遍历，后序遍历），也可以借助队列（层次遍历）。本次笔记只使用了递归的方法来进行前序遍历，中序遍历，后序遍历，借助队列进行层次遍历。想要更细致的看一下二叉树的遍历推荐http://c.biancheng.net/data_structure/tree/。

要遍历的二叉树如下：

中序遍历：A/B*C-D+E
前序遍历：+-*/ABCDE
后序遍历：AB/C*D-E+
层次遍历：+-E*D/CAB

头文件代码

  1 #ifndef _BINARYTREE_H
  2 #define _BINARYTREE_H
  3 
  4 #include<iostream>
  5 #include<queue>
  6 
  7 template<class T> class BinaryTree;
  8 
  9 template<class T>
 10 class TreeNode
 11 {
 12 public:
 13     TreeNode()
 14     {
 15         leftChild = NULL;
 16         rightChild = NULL;
 17     }
 18     T data;
 19     TreeNode<T> *leftChild;
 20     TreeNode<T> *rightChild;
 21 };
 22 
 23 template<class T>
 24 class BinaryTree
 25 {
 26 public:
 27     //二叉树可以进行的操作
 28     void InOrder();//中序遍历
 29     void InOrder(TreeNode<T>* currentNode);
 30 
 31     void PreOrder();//前序遍历
 32     void PreOrder(TreeNode<T>* currentNode);
 33 
 34     void PostOrder();//后续遍历
 35     void PostOrder(TreeNode<T>* currentNode);
 36 
 37     void LevelOrder();//层次遍历
 38     void Visit(TreeNode<T>* currentNode);
 39 public:
 40     TreeNode<T> *root;//为方便使用将根节点设为公有
 41 };
 42 
 43 template<class T>
 44 void BinaryTree<T>::LevelOrder()
 45 {
 46     std::queue<TreeNode<T>*> q;//借用队列，先把每层元素放进队列再进行遍历
 47     TreeNode<T>* currentNode = root;
 48     while (currentNode)
 49     {
 50         Visit(currentNode);
 51         //由于队列先进先出，所以先放左子树，再放右子树
 52         if (currentNode->leftChild) q.push(currentNode->leftChild);
 53         if (currentNode->rightChild) q.push(currentNode->rightChild);
 54         if (q.empty()) return;
 55         currentNode = q.front();
 56         q.pop();//遍历之后要取走接着下一个
 57     }
 58 }
 59 
 60 template<class T>
 61 void BinaryTree<T>::Visit(TreeNode<T>* currentNode)
 62 {
 63     std::cout << currentNode->data;
 64 }
 65 
 66 template<class T>
 67 void BinaryTree<T>::InOrder()
 68 {
 69     InOrder(root);
 70 }
 71 
 72 template<class T>
 73 void BinaryTree<T>::InOrder(TreeNode<T>* currentNode)
 74 {
 75     if (currentNode)
 76     {
 77         InOrder(currentNode->leftChild);
 78         Visit(currentNode);
 79         InOrder(currentNode->rightChild);
 80     }
 81 }
 82 
 83 template<class T>
 84 void BinaryTree<T>::PreOrder()
 85 {
 86     PreOrder(root);
 87 }
 88 
 89 template<class T>
 90 void BinaryTree<T>::PreOrder(TreeNode<T>* currentNode)
 91 {
 92     if (currentNode)
 93     {
 94         Visit(currentNode);
 95         PreOrder(currentNode->leftChild);
 96         PreOrder(currentNode->rightChild);
 97     }
 98 }
 99 
100 template<class T>
101 void BinaryTree<T>::PostOrder()
102 {
103     PostOrder(root);
104 }
105 
106 template<class T>
107 void BinaryTree<T>::PostOrder(TreeNode<T>* currentNode)
108 {
109     if (currentNode)
110     {
111         PostOrder(currentNode->leftChild);
112         PostOrder(currentNode->rightChild);
113         Visit(currentNode);
114     }
115 }
116 
117 
118 
119 #endif

源文件代码

 1 #include<iostream>
 2 #include"binarytree.h"
 3 
 4 using namespace std;
 5 
 6 int main()
 7 {
 8     BinaryTree<char> tree;
 9     TreeNode<char> 加, 减, 乘, 除, a, b, c, d, e;
10     加.data = '+';
11     减.data = '-';
12     乘.data = '*';
13     除.data = '/';
14     a.data = 'A';
15     b.data = 'B';
16     c.data = 'C';
17     d.data = 'D';
18     e.data = 'E';
19 
20     tree.root = &加;
21     加.leftChild = &减;
22     加.rightChild = &e;
23     减.leftChild = &乘;
24     减.rightChild = &d;
25     乘.leftChild = &除;
26     乘.rightChild = &c;
27     除.leftChild = &a;
28     除.rightChild = &b;
29 
30     cout << "中序遍历：" ;
31     tree.InOrder();//中序遍历
32     cout << endl;
33 
34     cout << "前序遍历：" ;
35     tree.PreOrder();//前序遍历
36     cout << endl;
37 
38     cout << "后序遍历：" ;
39     tree.PostOrder();//后序遍历
40     cout << endl;
41 
42     cout << "层次遍历：";
43     tree.LevelOrder();//层次遍历
44     cout << endl;
45     return 0;
46 }