| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 6419 人关注过本帖, 2 人收藏
标题:发自己写的二叉树的抽象数据类型以及相关算法的实现(采用OOP实现的),大家多 ...
只看楼主 加入收藏
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
//////////////////////////////////////////////////
//IsCompleteBinTree()公有成员函数
//判断一棵二叉树是否是完全二叉树
//////////////////////////////////////////////////
template<class T>
bool BinaryTree<T>::IsCompleteBinTree()
{
    LinkedQueue<BinTreeNode<T>*> LQ;     //层次遍历用的队列
    LQ.EnQueue(root);                    //根结点入队列
    BinTreeNode<T>* ptr;                 //游标指针
    int flag=0;                          //0表示遍历的前个结点是数据1:表示前个是空
    while(!LQ.IsEmpty())
    {
        LQ.DeQueue(ptr);                 //从队列中取出一个元素
        
        if(ptr!=NULL)
        {
            if(flag==1)                  //如果当前是数据节点但前个是空
                return false;            //说明不是完全二叉树
            LQ.EnQueue(ptr->leftChild);  //如果是空指针也可以压入队列的
            LQ.EnQueue(ptr->rightChild);
        }
        else
            flag=1;
    };
    return true;
};
///////////////////////IsCompleteBinTree()函数结束
2008-12-04 22:12
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
//////////////////////////////////////////////////
//FindWidth()公有成员函数
//求子树subTree的宽度,二叉树的宽度就是结点数最多
//的那层上的结点的个数,i是层次开始的层次数,
//count数组用于记录各层上的结点个数
//////////////////////////////////////////////////
template<class T>
void BinaryTree<T>::FindWidth(BinTreeNode<T>* subTree
                             ,int* count,int i=0)
{
    if(subTree!=NULL)
    {
        cout<<++p;
        count[i]++;
        FindWidth(subTree->leftChild,count,i+1);
        FindWidth(subTree->rightChild,count,i+1);
    };
};
///////////////////////////////FindWidth()函数结束

/////////////////////////////////////////////////
//FindWidth()
//找出当前的二叉树的宽度
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::FindWidth()
{
    int dep=Height();             //当前二叉树的深度
    int* count=new int[dep];      //按照当前二叉树的深度来开辟数组
    for(int i=0;i<dep;i++)
        count[i]=0;               //把计数数组先初始化为0
    FindWidth(root,count,0);
    int max=0;
    for(i=0;i<dep;i++)            //找出最大宽度
        if(max<count[i])
            max=count[i];
    return max;
};
//////////////////////////////FindWidth()函数结束
2008-12-04 22:12
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
/////////////////////////////////////////////////
//NumOfSons()公有成员函数
//递归:求解当前指定结点的所有的子孙的个数
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::NumOfSons(BinTreeNode<T>* p)
{
    if(p==NULL)                   //如果指针是空的则停止
        exit(1);
    int count=0;                  //计数器
    if(p->leftChild!=NULL)        //如果左子树不空
        count=count+1+NumOfSons(p->leftChild);
    if(p->rightChild!=NULL)
        count=count+1+NumOfSons(p->rightChild);
    return count;                 //返回子孙接点的个数
};
//////////////////////////////NumOfSons()函数结束
2008-12-04 22:12
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
/////////////////////////////////////////////////
//PreOrderCount()公有成员函数
//通过前序遍历来统计当前二叉树中的结点的个数
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCount(
                BinTreeNode<T>* subTree)
{
    static int count=0;               //静态计数器
    if(subTree!=NULL)                 //当前结点统计加1
    {
        count++;
        if(subTree->leftChild!=NULL)  //如果左子树不空
            PreOrderCount(
                subTree->leftChild);  //递归统计左子树的结点个数
        if(subTree->rightChild!=NULL) //如果右子树不空
            PreOrderCount(
                subTree->rightChild); //递归统计右子树的结点个数
        return count;
    }
    else
        return count;
};
//////////////////////////PreOrderCount()函数结束
2008-12-04 22:13
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
/////////////////////////////////////////////////
//PreOrderCreate()公有成员函数
//递归通过前序序列创建一棵二叉树,前序序列中
//空子树用符号'#'来代替,s是前序序列描述字符串
//返回的是创建结束后字符串停留的当前位置
/////////////////////////////////////////////////
template<class T>
int BinaryTree<T>::PreOrderCreate(
            char* s,int start,BinTreeNode<T>*& subTree)
{
    if(s[start]!='#')          //如果当前读入的不是空子树
    {
        BinTreeNode<T>* newNode//创建新结点
            =new BinTreeNode<T>(s[start]);
        subTree=newNode;       //新建立的根结点
  
        int k=PreOrderCreate(s,//从start+1位置开始递归创建左子树
            start+1,subTree->leftChild);
        PreOrderCreate(s,k+1,  //递归创建右子树
            subTree->rightChild);
    }
    else
    {
        subTree=NULL;          //创建空子树
        return start;          //当前子树最后一个'#'
    };
};
/////////////////////////PreOrderCreate()函数结束

#endif
2008-12-04 22:13
leilong
Rank: 1
等 级:新手上路
帖 子:6
专家分:0
注 册:2008-9-3
收藏
得分:0 
回复 第10楼 geninsf009 的帖子
楼主 辛苦,写这么多 谢谢了

我迷茫,所以我探索;
我无知,所以我学习。
2008-12-04 23:19
shuimiu1988
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-12-1
收藏
得分:0 
楼主真油!!!!谢谢分享
2008-12-09 19:30
很远的那颗星
Rank: 2
等 级:新手上路
威 望:4
帖 子:544
专家分:0
注 册:2008-6-30
收藏
得分:0 
晕..黑压压的一片,这代码可以卖个好价钱了,呵呵...

对你的遍历真的无话说啊,我从来没这么认真的一起写过,只是偶而写一下,刚学时都是递归,但为以后找工作着想,现在改非递归了..

Fighting~~~~~~~~
2008-12-10 19:12
flylee
Rank: 5Rank: 5
等 级:职业侠客
帖 子:309
专家分:374
注 册:2004-8-10
收藏
得分:0 
awesome
2010-01-05 23:24
xunmeng1024
Rank: 1
等 级:新手上路
帖 子:3
专家分:0
注 册:2010-4-4
收藏
得分:0 
楼主真牛!!!你是偶的偶像
2010-04-04 15:59
快速回复:发自己写的二叉树的抽象数据类型以及相关算法的实现(采用OOP实现的),大 ...
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.017114 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved