《数据结构》第五章 树和二叉树 扩展二叉实现代码示例

大家好。本例是一个扩展二叉树。实现了树的构造、前序遍历、中序遍历、后序遍历，计算叶子个数等操作。请大家参考。并能举一反三，灵活掌握程序思想。

#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.

? ? 大家可以输入其它树序列进行检验。

? ? 祝大家调试程序成功。