# 二叉树递归遍历

xiaoxiao2021-03-25  8

#include<bits/stdc++.h> using namespace std; /*定义二叉树*/ typedef struct node { char data; struct node *left; struct node *right; }node,*BT; /*创建二叉树*/ void CreatBiTree(BT &T) { char ch; cin>>ch; if(ch=='#') T=NULL; else{ T=new node; T->data=ch; CreatBiTree(T->left); CreatBiTree(T->right); } } /*先序遍历*/ void PreVisit(BT T) { if(T){ cout<<T->data<<' '; PreVisit(T->left); PreVisit(T->right); } } /*中序遍历*/ void InVisit(BT T) { if(T){ PreVisit(T->left); cout<<T->data<<' '; PreVisit(T->right); } } /*后序遍历*/ void PostVisit(BT T) { if(T){ PreVisit(T->left); PreVisit(T->right); cout<<T->data<<' '; } cout<<endl; } /*层次遍历*/ void BfsVisit(BT T) { queue<BT> q; q.push(T); while(!q.empty()) { BT t=q.front(); cout<<t->data; q.pop(); if(t->left) q.push(t->left); if(t->right) q.push(t->right); } cout<<endl; } int main() { BT T; CreatBiTree(T); cout<<endl<<"Build BiTree Finish"<<endl<<endl; /*先序遍历*/ cout<<"PreOrder"<<endl; PreVisit(T); cout<<endl<<endl; /*中序遍历*/ cout<<"InOrder"<<endl; InVisit(T); cout<<endl<<endl; /*后序遍历*/ cout<<"PostOrder"<<endl; PostVisit(T); cout<<endl<<endl; /*层序遍历*/ cout<<"BfsOrder"<<endl; BfsVisit(T); cout<<endl<<endl; return 0; }