2

一般的なツリーのバイナリ ツリー実装を使用しています。一般的なアルゴリズムでは、ノードの最初の息子は「左」であり、他の兄弟は最初の息子の「右」です。

私が答えようとしているのは、ノード p が与えられた場合、ノード p の父をどのように見つけることができるかということです。

ここにノードがあります（非再帰的な方法を使用してトラバースしているため、訪問済み属性と親属性です）

struct node {
  std::string name;
  int sons;
  bool visited;
  node * first;
  node * next;
  node * parent;    
};

次に例を示します。

GeneralTree

  A                   
 /|\       
B C D

GeneralTree の BinaryTree バージョン

  A
 /
B
 \
  C
   \
    D

したがって、B、C、および D の親ノードはすべて A です。

4

1 に答える 1

3

null 参照が見つかるまで、親リンクをたどってください。これはp、ルート ノードから開始した場合に発生します。または、元のノードを左の子として持つノードです。

var current = p;
var parent = current.parent;

while ((parent != null) && (current != parent.left))
{
    current = parent;
    parent = current.parent;
}

parentノードの親ノードが含まれるようになりました。pまたは、ルート ノードが含まれている場合null。p

于 2012-12-12T17:20:35.327 に答える