algorithm - 如何创建也将祖 parent 与孙子女联系起来的二叉树？

Question

是否有某种算法可以到达二叉树的孙子？喜欢这个例子吗？

在图中，有连接祖 parent 和孙子的节点，而普通的二叉树只连接 child 和 parent 。可以使用什么算法链接到祖 parent ？

编辑:每个节点都有一个索引和两个值。[指数][值(value)值(value)];

我想做什么:

index[3] and index[4] = value[0]; 
index[5] and index[6] = value[1]; 
index[7] and index[8] = value[2]; 
index[9] and index[10] = value[3]; 
.... ETC 

Answer 1

通常，您使用两个指针构造二叉树中的每个节点:左子指针“node.left”和右子指针节点“node.right”。然后一个节点的四个孙节点可以用表达式“node.left.left”、“node.left.right”、“node.right.left”和“node.right.right”定位。这些表达式的计算速度非常快。

通过这种技术访问孙子将使必须维护您的代码的人的一切变得更加简单，甚至可能是在您有时间忘记您曾经进行过此讨论后十个月后的您。

如果您坚持冗余存储孙指针，那么每个节点将需要四个额外的指针:'node.leftleft'、'node.leftright'、'node.rightleft' 和 'node.rightright'。

这感觉就像是一个坏主意的定义。这棵树不仅会变得又大又笨拙，而且每次添加或删除节点时，您都​​会发现自己更新了指针的度量标准。为了收回你将花在调试这样一团乱麻上的时间，你将不得不使用该程序大约九千年。