发帖    主题    评论    推荐    标签    作者    订阅    查搜    注册   登陆   关注
 
面向对象 设计模式 领域驱动设计 企业架构 框架 开发教程 微服务 大数据 扩展性 并发编程 事件驱动 分布式 SOA

LongTree的正确分析理解

    
2005-01-04 16:43
赞助商链接

LongTree的正确理解分析

在网上有一篇文件介绍LongTreer的原理的,但是对于leftChildren和rightSiblings的讲解似乎有些不完整。
leftChildren保存某结点儿子在keys[]中的数组索引值,同理rightSiblings保存其本结点兄弟在keys[]中的数组索引值。
通过一些测试让我理解这一功能:
下面是从JiveMessage表中截取的部分数据

messageID ParentMessageID threadID forumID
2 NULL 1 31
31 2 1 31
46 2 1 31
61 2 1 31
62 2 1 31
32 31 1 31
47 46 1 31

在LongTree中的addChild方法加入了部分代码,也修改了部分代码,目的是为了输出leftChildren 、rightSiblings的数值

public void addChild(long parentKey, long newKey)
{
// 找到一个给定的节点parentKey的父结点
char parentIndex = findKey(parentKey, (char) 1);
//System.out.println("父节点索引号:" + (int)parentIndex + "-----父结点:" + parentKey +
// "-----子结点:" + (int)newKey);
if (parentIndex == 0)
{
throw new IllegalArgumentException(
"Parent key " + parentKey +
" not found when adding child " +
newKey +
".");
}

keys[nextIndex] = newKey;
leftChildren[nextIndex] = 0;
rightSiblings[nextIndex] = 0;
System.out.println(
"keys[" + (int) nextIndex + "] = " + (int) newKey);

// Adjust references. Check to see if the parent has any children.
if (leftChildren[parentIndex] == 0)
{
// No children, therefore make the new key the first child.
leftChildren[parentIndex] = nextIndex;
System.out.println(
"leftChildren[" + (int) parentIndex + "] = " +
(int) nextIndex);
}
else
{
// The parent has children, so find the right-most child.
long siblingIndex = leftChildren[parentIndex];

while (rightSiblings[new Long(siblingIndex).intValue()] != 0)
{
siblingIndex = rightSiblings[new Long(siblingIndex).intValue()];
}

// Add the new entry as a sibling of that last child.

//rightSiblings[new Long(siblingIndex).intValue()] = nextIndex;

int tmpint = new Long(siblingIndex).intValue();
rightSiblings[tmpint] = nextIndex ;
System.out.println(
"rightSiblings[" + tmpint +"] = " + (int)nextIndex);
}

// Finally, increment nextIndex so it's ready for next add.
nextIndex++;
}

下面是输出值

keys[2] = 31
leftChildren[1] = 2
keys[3] = 32
leftChildren[2] = 3
keys[4] = 46
rightSiblings[2] = 4
keys[5] = 47
leftChildren[4] = 5
keys[6] = 61
rightSiblings[4] = 6
keys[7] = 62
rightSiblings[6] = 7

得到了这么一组值,该如何理解呢?
假设有
leftChildren[X] = Y
正确理解是
keys[Y]是keys[X]的一个儿子结点
同理
rightSiblings[X] = Y
正确理解是
keys[Y]是keys[X]的一个兄弟结点

也就是说leftChildren、rightSiblings保存的是它们子结点、兄弟结点在keys[]中的数组索引值而已,而不能说leftChildren保存的是某一结点的子结点

时间有限,懒得去好好的整理文字,大家能理解就行

愿和更多的对Jive有深入研究的朋友交流
QQ:45214493(对JIVE没有研究者勿加)


2005-01-04 16:45

愿和所有对JAVA有深入研究的朋友一起共同交流、进步

组合     

赞助商链接

赞助商链接

返回顶部

移动版 关于本站 使用帮助 联系管理员 最佳分辨率1366x768
OpenSource JIVEJDON Powered by JdonFramework Code © 2002-20 jdon.com