大家好。本例是一个扩展二叉树。实现了树的构造、前序遍历、中序遍历、后序遍历,计算叶子个数等操作。请大家参考。并能举一反三,灵活掌握程序思想。
#include <iostream> using namespace std; struct BiNode //二叉树的结点结构 { char data; BiNode *lchild,*rchild; }; class BiTree { public: BiTree( ){root = Creat(root);} //构造函数,建立一棵二叉树 ~BiTree( ){Release(root);} //析构函数,释放各结点的存储空间 void PreOrder( ){PreOrder(root);} //前序遍历二叉树 void InOrder( ){InOrder(root);} //中序遍历二叉树 void PostOrder( ){PostOrder(root);} //后序遍历二叉树 void CountLeaf(){CountLeaf(root);} void PrintLeafCount(); private: BiNode *root; //指向根结点的头指针 int LeafCount; BiNode *Creat(BiNode *bt); //构造函数调用 void Release(BiNode *bt); //析构函数调用 void PreOrder(BiNode *bt); //前序遍历函数调用 void InOrder(BiNode *bt); //中序遍历函数调用 void PostOrder(BiNode *bt); //后序遍历函数调用 void CountLeaf(BiNode *bt); }; BiNode *BiTree::Creat(BiNode *bt) { char ch; cout<<"请输入创建一棵二叉树的结点数据"<<endl; cin>>ch; if (ch=='#') return NULL; else{bt = new BiNode; //生成一个结点 bt->data=ch; bt->lchild = Creat(bt->lchild); //递归建立左子树 bt->rchild = Creat(bt->rchild); //递归建立右子树 } LeafCount=0; return bt; } void BiTree::Release(BiNode *bt) { if (bt != NULL)
{ Release(bt->lchild); //释放左子树 Release(bt->rchild); //释放右子树 delete bt; } } void BiTree::CountLeaf(BiNode *bt) { if (bt != NULL) {if (bt->lchild==NULL && bt->rchild==NULL) LeafCount++; CountLeaf(bt->lchild); CountLeaf(bt->rchild); //右子树 } } void BiTree::PrintLeafCount() { cout<<LeafCount; } void BiTree::PreOrder(BiNode *bt) { if(bt==NULL) return; else?
{ cout<<bt->data<<" "; PreOrder(bt->lchild); PreOrder(bt->rchild); } } void BiTree::InOrder(BiNode *bt) { if (bt==NULL) return; //递归调用的结束条件 else { InOrder(bt->lchild); //中序递归遍历root的左子树 cout<<bt->data<<" "; //访问根结点的数据域 InOrder(bt->rchild); //中序递归遍历root的右子树 } } void BiTree::PostOrder(BiNode *bt) { if (bt==NULL) return; //递归调用的结束条件 else { PostOrder(bt->lchild); //后序递归遍历root的左子树 PostOrder(bt->rchild); //后序递归遍历root的右子树 cout<<bt->data<<" "; //访问根结点的数据域 } } void main() { BiTree T; //创建一棵树 //cout<<"------前序遍历------ "<<endl; T.PreOrder( ); cout<<endl; cout<<"------中序遍历------ "<<endl; T.InOrder( ); cout<<endl; cout<<"------后序遍历------ "<<endl; T.PostOrder( ); cout<<endl; cout<<"------叶子个数------ "<<endl; T.CountLeaf(); T.PrintLeafCount(); cout<<endl; }
? ? ?程序运行后,可以参照课本P119页,输入一个字符序列,建立如图5-26的二叉树。将分别输出各个遍历结点序列,和叶子的个数。
叶子个数为2.
? ? 大家可以输入其它树序列进行检验。
? ? 祝大家调试程序成功。