| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4487 人关注过本帖
标题:求树类的查找双亲结点的函数
只看楼主 加入收藏
zhanghj
Rank: 1
来 自:江苏盐城
等 级:新手上路
帖 子:56
专家分:0
注 册:2007-11-24
结帖率:100%
收藏
 问题点数:0 回复次数:7 
求树类的查找双亲结点的函数
这个树类是孩子兄弟表示法,
int Tree::Parent(TreeNode* r,TreeNode* v)
{
    TreeNode*q=r->FirstChild;
    while(q!=NULL&&q!=v)
    {
        if((Parent(q,v))!=0) return 0;
        q=q->NextSibling;
    }
    return 1;
}
int Tree::Parent()
{
    TreeNode*p=current;
    if(current==NULL&&current==root)
    {
        current=NULL;
        return 0;
    }
    int k=Parent(root,p);
    return k;
}
这个是书上的例子,它返回的是判断是否有双亲结点,我想要的是返回的是双亲这个结点,
请大家帮我写下。
搜索更多相关主题的帖子: 双亲结点 树类 函数 Parent TreeNode 
2008-07-28 10:14
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
struct Node{
    Data_t data;
    Node* firs_chirld;//第一个孩子
    Node* last_chirld;//最后一个孩子
    Node* next_brother;//下一个兄弟
    Node* prev_brother;//前一个兄弟
    Node* father;//父亲
};
直接把节点搞成这种结构,不就可以用O(1)的时间找到父亲了
2008-07-28 15:37
zhanghj
Rank: 1
来 自:江苏盐城
等 级:新手上路
帖 子:56
专家分:0
注 册:2007-11-24
收藏
得分:0 
这树是孩子兄弟表示法,没有指向双亲的指针,你这样也可以,关键是学习方法,
2008-07-28 18:00
leeco
Rank: 4
等 级:贵宾
威 望:10
帖 子:1029
专家分:177
注 册:2007-5-10
收藏
得分:0 
我给的就是孩子兄弟树的结构,你没看到我的注释吗?
要活学活用。
你把这题过掉基本可以肯定你掌握了孩子兄弟树
http://acm.zju.
2008-07-28 23:45
zhanghj
Rank: 1
来 自:江苏盐城
等 级:新手上路
帖 子:56
专家分:0
注 册:2007-11-24
收藏
得分:0 
哦,谢了.应该活学活用.你下面那网站是干什么的,全英文
2008-07-29 09:20
kuba813
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-7-28
收藏
得分:0 
都是高手哦
2008-07-29 09:31
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
好了,刚帮你写好一个满足你的要求的递归函数,试验一下吧:

/////////////////////////////////////////////////////
//getParent()私有成员函数
//递归:在子树subTree中找指定结点p的父结点
//如果找到就返回该结点指针,否则返回NULL
/////////////////////////////////////////////////////
template<class T>
TreeNode<T>* Tree<T>::getParent(TreeNode<T>* subTree,TreeNode<T>* p)
{
    //如果要找的不是是根结点而且子树不空
    if(subTree!=NULL && p!=subTree
        && subTree->firstChild!=NULL)
    {
        //游标指针,遍历subTree的所有子结点
        TreeNode<T>* ptr=subTree->firstChild;
        //在subTree的所有子女中找看是否是结点p
        while(ptr!=NULL)
        {
            //如果p是subTree的子结点
            if(ptr==p)
                //返回父结点
                return subTree;
            else
            {
                //在子树中递归寻找
                TreeNode<T>* temp=getParent(ptr,p);
                //如果没有
                if(temp!=NULL)
                    return temp;
                else
                    ptr=ptr->nextSibling;
            };
        };
        //所有子树中都没有找到
        return NULL;
    }
    else
        return NULL;
};
//////////////////////////////getParent()私有函数结束

[[it] 本帖最后由 geninsf009 于 2008-8-25 23:19 编辑 [/it]]
2008-08-25 22:38
geninsf009
Rank: 3Rank: 3
等 级:论坛游民
威 望:8
帖 子:613
专家分:95
注 册:2008-8-16
收藏
得分:0 
对了,还得告诉你我的树的结点的定义:
/////////////////////////////////////////////////////
//TreeNode<T>结构体的定义
//树的子女-兄弟链表表示法的结点结构定义
/////////////////////////////////////////////////////
template<class T>
struct TreeNode
{
    T data;                   //结点的数据域
    TreeNode<T>* firstChild;  //长子结点的指针
    TreeNode<T>* nextSibling; //下一个兄弟结点的指针
    //结点结构体的构造函数
    TreeNode(T value=0,TreeNode<T>* fc=NULL,TreeNode<T>* ns=NULL)
    {
        data=value;           //数据域初始化为0
        firstChild=fc;        //初始化长子结点
        nextSibling=ns;       //初始化下一个兄弟结点
    };
};
////////////////////////////TreeNode<T>结构体定义结束
2008-08-25 22:42
快速回复:求树类的查找双亲结点的函数
数据加载中...
 
   



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

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