用递归的方法进行二叉树创建、遍历和输出。
这个算法最主要的就是注意输入格式,如果输入格式不对,也就不能正常输出遍历二叉树的结果。也就反映了没有彻底理解这个递归遍历二叉树的算法。
#include<iostream> using namespace std; typedef struct BiTNode { char data;//字符型的内容 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; int CreateBiTree(BiTree &T)//先序创建 { char ch; cin>>ch; if(ch=='*') T=NULL;//如果该结点为空的话,就输入'*'表示为空 else { if(!(T=(BiTNode *)malloc(sizeof(BiTNode)))) return 0; T->data = ch;//生成根结点 CreateBiTree(T->lchild);//构造左子树 CreateBiTree(T->rchild);//构造右子树 } return 1; } //递归算法来遍历二叉树 int PrintInt(char e) { cout<<e<<" "; return 1; } int PreOrderTraverse(BiTree T,int(*PrintInt)(char e)) { if(T)//先序遍历 { if(PrintInt(T->data)) if(PreOrderTraverse(T->lchild,PrintInt)) if(PreOrderTraverse(T->rchild,PrintInt)) return 1; return 0; } else return 1; } int main() { BiTree T;//定义一个二叉树T cout<<"请按先序排列数序创建二叉树,当结点为空时,请用'*'表示!\n"; CreateBiTree(T);//先序排列顺序创建二叉树,不按规定输入会有异常 PreOrderTraverse( T,PrintInt);//先序遍历并输出结果 return 0; }
运行图示:
创建和遍历一个下图所示的简单二叉树:
实际操作图示和结果: