| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2730 人关注过本帖
标题:求孩子兄弟链表的创建并输出的程序
只看楼主 加入收藏
huangch
Rank: 1
来 自:肇庆学院网络工程系
等 级:新手上路
帖 子:62
专家分:0
注 册:2008-7-21
收藏
 问题点数:0 回复次数:3 
求孩子兄弟链表的创建并输出的程序
来鸟,求孩子兄弟链表的创建并输出的程序!!
我想了很久了!
搜索更多相关主题的帖子: 链表 兄弟 孩子 输出 
2008-11-26 23:59
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
你指的是firstChild-nextSibling链表结构的树的创建和输出吗?

这是我写的通过广义表描述字符串s来非递归创建一棵树的代码:
这个函数你可以在GenTree<T>的带参数的构造函数里调用
/////////////////////////////////////////////////////
//CreateTree私有成员函数
//通过广义表形式的树的描述字符串建立
//树的子女-兄弟链表的存储结构(s以'#'号结尾)
/////////////////////////////////////////////////////
template<class T>
void Tree<T>::CreateTree(char* s)
{
    //树的结点变量
    TreeNode<T>* p=NULL;
    //取出的栈顶元素
    TreeNode<T>* top=NULL;
    //用于保存同行前一个结点的指针
    TreeNode<T>* pre=NULL;
    //创建树过程中用到的堆栈,元素是结点指针
    LinkedStack<TreeNode<T>*> LS;
    //计数器
    int i=0;
    //标志是连在上个结点的firstChild域还是nextSibling域
    int flag=0;//0:第一个结点 1:表示连在firstChild 2:表示连在nextSibling

    while(s[i]!='#')
    {
        switch(s[i])
        {
        //如果取出的是'('左括号
        case '(':
            {
                flag=1;                    //表示开始要延伸当前结点的长子结点
                LS.Push(p);                //当前结点入栈
                break;
            }

        //如果取出的是','逗号
        case ',':
            {
                pre=p;                     //保留当前结点
                flag=2;                    //表示开始要延伸当前结点的兄弟结点
                break;
            }

        //如果取出的是')'右括号
        case ')':
            {
                LS.Pop(p);                 //回到父结点开始延伸
                flag=2;                    //表示开始要延伸当前结点的兄弟结点
                break;
            }

        //如果取出的是字母
        default:
            {
                p=new TreeNode<T>(s[i]);   //依据取出的字母新建一个结点

                //表示新建的结点是上个结点的长子结点
                if(flag==1)
                {
                    LS.getTop(top);        //取栈顶结点
                    top->firstChild=p;     //挂上长子结点
                }
                else if(flag==2)
                    pre->nextSibling=p;    //兄弟结点的连接
                else
                    root=p;                //第一个创建的是根结点
            }
        }
        i++;
    }
};
/////////////////////////////////CreateTree()函数结束
2008-11-27 09:37
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
关于GenTree<T>树对象的输出,我觉得看采取怎样的格式,
首先你可以根据当前的存储结构仍然通过广义表的形式输出,
这样就可以写成递归的形式了,写的代码如下:
/////////////////////////////////////////////////////
//私有成员函数Display()
//以广义表的形式显示以p为根的树的内容
/////////////////////////////////////////////////////
template<class T>
void Tree<T>::Display(TreeNode<T>* p)
{
    cout<<p->data;              //显示根结点
    int k;                      //用于表示是否需要加括号
    if(p->firstChild!=NULL)     //如果该结点有长子结点就显示括号
    {
        cout<<"(";              //显示左括号
        k=1;                    //k用于标记括号的成队显示
    }
    else
        k=0;                    //标记后面可以不用显示

    p=p->firstChild;            //进入长子树
    while(p!=NULL)
    {
        Display(p);             //递归显示子树
        if(p->nextSibling!=NULL)//如果兄弟结点不空就显示','逗号
            cout<<",";
        p=p->nextSibling;       //进入下一棵子树
    };

    if(k==1)
        cout<<")";              //显示右括号
};
////////////////////////////////////Display()函数结束
2008-11-27 09:42
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
或者你还可以通过缩进的格式来显示一棵树的内容,
随进的格式即孩子结点总比父结点向后缩进显示,即很像已经展开的TreeViewList,
写的递归代码如下:

/////////////////////////////////////////////////////
//PrintTab()私有递归成员函数
//以缩进的格式来显示子树subTree的先根结构
/////////////////////////////////////////////////////
template<class T>
void Tree<T>::PrintTab(TreeNode<T>* subTree,int tab)
{
    if(subTree!=NULL)
    {
        //显示缩进的空格
        for(int i=0;i<=tab;i++)
            cout<<"----";
        //显示当前子树的根结点
        cout<<subTree->data<<endl;
    
        //游标指针,从长子结点开始
        TreeNode<T>* ptr=subTree->firstChild;
        //循环递归PrintTab显示subTree的所有子树
        while(ptr!=NULL)
        {
            PrintTab(ptr,tab+1);
            //指向下个兄弟子树
            ptr=ptr->nextSibling;
        };
    };
};
///////////////////////////////////PrintTab()函数结束

当然我觉得以上的代码也可以通过非递归的方式来实现,我想,在非递归遍历
该树的过程中,当前堆栈中元素的个数,可以认为是当前递归的深度,也可以
认为是当前结点应该缩进的空格的个数,这个代码就不给你了,想必你也可以
编写出来,另外只是给你成员函数,没有给你整个完整的类的实现,你可以通
过我的代码里的思想应该可以写出属于自己的代码的,大家共勉!
2008-11-27 09:47
快速回复:求孩子兄弟链表的创建并输出的程序
数据加载中...
 
   



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

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