二叉树的构建和前中后序遍历

代码分为二叉树的构建，以及三种遍历方法：先序遍历、中序遍历和后序遍历。

#include <iostream> #include <stdio.h> #include <string.h> using namespace std; //树的节点结构体定义 //这里主要要加上typedef，不然创建T的时候会显示没有生命BiTree类型 typedef struct TreeNode { //如果改为int char;那么就会输出有问题； char val; struct TreeNode *left; struct TreeNode *right; }*BiTree; //创建二叉树 int creatBiTree(BiTree &T){ char ch; cin>>ch; if(ch=='0') T=NULL; else { T=(TreeNode*)malloc(sizeof(TreeNode)); T->val=ch; creatBiTree(T->left); creatBiTree(T->right); } return 1; } //先序遍历 void PreShowBiTree(BiTree T){ if(T){ cout<<T->val<<" "; PreShowBiTree(T->left); PreShowBiTree(T->right); } } //中序遍历 void MidShowBiTree(BiTree &T){ if(T){ PreShowBiTree(T->left); cout<<T->val<<" ";; PreShowBiTree(T->right); } } //后序遍历 void BehShowBiTree(BiTree &T){ if(T){ PreShowBiTree(T->left); PreShowBiTree(T->right); cout<<T->val<<" ";; } else{ cout<<"后序遍历不成功！"; } } int main(){ TreeNode *T; //BiTree T; cout<<"请输入二叉树："; creatBiTree(T); cout<<"中序遍历："; MidShowBiTree(T); cout<<endl; cout<<"先序遍历:"; PreShowBiTree(T); cout<<endl; cout<<"后序遍历:"; BehShowBiTree(T); cout<<endl; system("pause"); return 0; }

树的创建和遍历，很适合用递归算法，但是递归次数加多的话就会导致效率下降。因此一般如果树比较大，那么还是使用非递归的方法还是比较好的。