C++数据结构--二叉树的前序遍历，中序遍历，后序遍历

旧城等待， 2021-11-26 23:52 291阅读 0赞

**1.二叉树的抽象模型和相应的node对象表示  
![20130801080518843][]  
  
  
  
2.遍历二叉树  
Example：对下图给出的二叉树进行前，中，后序遍历结果  
![20130801080532984][]  
  
  
  
  
  
  
  
  
  
本示例所用到的二叉树  
![20130801080602843][]  
实现代码：  
  
  
  
  
  
  
template<typename T>  
class node  
\{  
public:  
T val; //节点值  
 node<T>\* left; //左节点   
 node<T>\* right; //右节点  
  
 node():val(T()),left(nullptr),right(nullptr)\{\}  
 node(T v, node<T>\* l=nullptr, node<T>\* r=nullptr):val(v),left(l),right(r)\{\}  
\};  
  
  
  
  
  
  
node<char>\* createBTree() //构建一棵示例二叉树   
 \{   
node<char>\* d=new node<char>('D');  
node<char>\* e=new node<char>('E');  
node<char>\* b=new node<char>('B',nullptr,d);  
node<char>\* c=new node<char>('C',e,nullptr);  
node<char>\* a=new node<char>('A',b,c);  
  
 \}  
  
 void preOrderTravel(node<char>\* root) //前序遍历   
\{   
if(!root) //根节点为空时结束递归   
\{   
 return;  
\}  
else  
\{   
cout<<root->val<<ends;  
preOrderTravel(root->left);  //递归遍历左子树  
 preOrderTravel(root->right); //递归遍历右子树  
  
\}   
\}   
  
  
void inOrderTravel(node<char>\* root)  
\{   
if(!root) //根节点为空时结束递归   
\{   
 return;  
\}  
else  
\{   
inOrderTravel(root->left);  
cout<<root->val<<ends;  
inOrderTravel(root->right);  
  
\}   
\}   
  
  
  
 void postOrderTravel(node<char>\* root)  
\{   
if(!root) //根节点为空时结束递归   
\{   
 return;  
\}  
else  
\{   
postOrderTravel(root->left);  
postOrderTravel(root->right);  
 cout<<root->val<<ends;  
\}   
\}   
  
  
  
  
  
int main()  
\{   
 node<char>\* root=createBTree();  
cout<<"preOrderTravel :" ;  
 preOrderTravel(root);  
 cout<<endl;  
  
 cout<<"inOrderTravel :" ;  
 inOrderTravel(root);  
 cout<<endl;  
  
 cout<<"postOrderTravel :" ;  
 postOrderTravel(root);  
 cout<<endl;  
return 0;  
\}  
  
  
  
  
  
  
运行结果：  
![Center][]  
  
  
  
  
解析：以后序遍历为例，前序和中序遍历类似  
![20130801080550812][]**

[20130801080518843]: /images/20211126/aecbe6fdaec341439d88d93782f8e50f.png
[20130801080532984]: /images/20211126/b465362dd4894bbd889e2bef85bff07d.png
[20130801080602843]: /images/20211126/cfd18458a3ab41ad8f7186acab3376c5.png
[Center]: /images/20211126/3ef642f121d0471fbec4423fbecb2952.png
[20130801080550812]: /images/20211126/0f0476102bbf4a3ba946ad9796093397.png