(C/C++学习)31.二叉树的遍历

说明：二叉树是一种非常重要的数据结构。对于二叉树，有两种遍历方式：深度遍历和广度遍历。其中深度遍历有前序、中序以及后序三种遍历方式。而广度遍历及常说的层次遍历。

1. 四种基本遍历的思想：

前序遍历：根节点－>左子树－>右子树

中序遍历：左子树－>根节点－>右节点

后续遍历：左子树－>右子树－>根节点

广度遍历：从上至下从左至右依次遍历

需要注意的是：对于每一子树也应该按照相应的遍历思想进行递归遍历。

举例，如下二叉树：

前序遍历：ABDECF （根左右）

中序遍历：DBEAFC （左根右）

后续遍历：DEBFCA （左右根）

广度遍历：ABCDEF （从上至下从左至右）

2. 面试常考点：根据遍历结果确定一棵二叉树

a. 已知前序遍历和中序遍历的结果，可以确定一棵唯一的二叉树结构，

b. 已知后续遍历和中序遍历的结果，可以确定一棵唯一的二叉树结构，

c. 已知前序遍历和后续遍历的结果，不能确定一棵唯一的二叉树结构。

3. 程序示例：

  1 #include<iostream>
  2 #include<queue>
  3 #include<stack>
  4 using namespace std;
  5 /*二叉树树节点*/
  6 class BT {
  7 public:
  8     BT(int data=0,BT* left=0,BT* right=0):_data(data),_left(left),_right(right) {}
  9     int _data;
 10     BT* _left;
 11     BT* _right;    
 12 };
 13 /*创建二叉树*/
 14 void CreatBT(BT *&root) {
 15     int data = 0;
 16     cin>>data;
 17     if(data != -1) {
 18         root = new BT(data,0,0);
 19         CreatBT(root->_left);
 20         CreatBT(root->_right);
 21     }    
 22 }
 23 /*删除二叉树*/
 24 void DeleteBT(BT* root){
 25     if(!root) 
 26         return ;
 27     DeleteBT(root->_left);
 28     DeleteBT(root->_right);
 29     delete root;        
 30 }
 31 /*二叉树前序遍历*/
 32 void ForTrans(BT* root) {
 33     if(!root)
 34         return ;    
 35     cout<<root->_data<<" ";
 36     ForTrans(root->_left);
 37     ForTrans(root->_right);    
 38 }
 39 /*二叉树中序遍历*/
 40 void CenTrans(BT* root) {
 41     if(!root)
 42         return ;
 43     CenTrans(root->_left);
 44     cout<<root->_data<<" ";
 45     CenTrans(root->_right);    
 46 }
 47 /*二叉树后序遍历*/
 48 void NexTrans(BT* root) {
 49     if(!root)
 50         return ;
 51     NexTrans(root->_left);
 52     NexTrans(root->_right);
 53     cout<<root->_data<<" ";    
 54 }
 55 
 56 /*二叉树深度遍历非递归版*/
 57 void DepTrans(BT *root) {
 58     if(!root)
 59         return ;
 60     stack<BT*> s;
 61     s.push(root);
 62     while(!s.empty()) {
 63         BT *temp = s.top();
 64         s.pop();
 65         cout<<temp->_data<<" ";
 66         if(temp->_right)
 67             s.push(temp->_right);
 68         if(temp->_left)
 69             s.push(temp->_left);    
 70     }     
 71 }
 72 /*二叉树广度遍历*/
 73 void BroTrans(BT *root) {
 74     if(!root)
 75         return; 
 76     queue<BT*> q;
 77     q.push(root);
 78     while(!q.empty()) {
 79         BT *temp = q.front();
 80         q.pop();
 81         cout<<temp->_data<<" ";
 82         if(temp->_left)
 83             q.push(temp->_left);
 84         if(temp->_right)
 85             q.push(temp->_right);     
 86     }
 87 }
 88 /*计算二叉树的最大深度*/
 89 int maxDepth(BT* root) {
 90     if(!root)
 91         return 0;
 92     else
 93         return max(maxDepth(root->_left),maxDepth(root->_right))+1;    
 94 }
 95 /*计算叶子节点数*/
 96 int numLeaf(BT* root) {
 97     if(!root)
 98         return 0;
 99     else if(!root->_left && !root->_right)
100         return 1;
101     else 
102         return numLeaf(root->_left)+numLeaf(root->_right);      
103 }
104 /*计算二叉树的最小深度*/
105 int minDepth(BT* root) {
106     if(!root)
107         return 0;
108     else if(!root->_left && root->_right)
109         return minDepth(root->_right)+1;
110     else if(root->_left && !root->_right)   
111         return minDepth(root->_left)+1;
112     else if(!root->_left && !root->_right)
113         return 1;
114     else
115         return min(minDepth(root->_right),minDepth(root->_left))+1;    
116 }
117 /*二叉树复制*/
118 BT* CopyBT(BT* root) {
119     if(!root)
120         return 0;
121     BT* left = CopyBT(root->_left);               
122     BT* right = CopyBT(root->_right);
123     BT* temp = new BT(root->_data,0,0);
124     temp->_left = left;
125     temp->_right = right;
126     return temp;
127 }
128 int main() {
129     BT* root = NULL;
130     CreatBT(root);
131     cout<<"-----------------ROOT---------------"<<endl;
132     cout<<"PreOrder: ";    ForTrans(root);  cout<<endl;
133     cout<<"CenOrder: ";    CenTrans(root);  cout<<endl;
134     cout<<"NexOrder: ";    NexTrans(root);  cout<<endl;   
135     cout<<"BroOrder: ";    BroTrans(root);  cout<<endl;
136     cout<<"DepOrder: ";    DepTrans(root);  cout<<endl;
137     cout<<"Max depth: "<<maxDepth(root)<<endl;
138     cout<<"Num Leafs: "<<numLeaf(root)<<endl;
139     cout<<"Min depth: "<<minDepth(root)<<endl;
140     cout<<"-------------COPYROOT---------------"<<endl;
141     BT* copyroot = CopyBT(root);
142     DeleteBT(root);
143     cout<<"PreOrder: ";    ForTrans(copyroot);  cout<<endl;
144     cout<<"CenOrder: ";    CenTrans(copyroot);  cout<<endl;
145     cout<<"NexOrder: ";    NexTrans(copyroot);  cout<<endl;   
146     cout<<"BroOrder: ";    BroTrans(copyroot);  cout<<endl;
147     cout<<"DepOrder: ";    DepTrans(copyroot);  cout<<endl;
148     cout<<"Max depth: "<<maxDepth(copyroot)<<endl;
149     cout<<"Num Leafs: "<<numLeaf(copyroot)<<endl;
150     cout<<"Min depth: "<<minDepth(copyroot)<<endl;
151     DeleteBT(copyroot);
152     return 0;
153 }

View Code