0 
#ifndef __TREE_H
#define __TREE_H
#include <cstdlib>
#include<string>

// structure of a tree node

struct TreeNode{
        string str;
        TreeNode *parent;
        TreeNode *leftChild;
        TreeNode *nextSibling;

        TreeNode(string str1){
                this->str = str1;
                this->parent = NULL;
                this->leftChild = NULL;
                this->nextSibling = NULL;
        }

};

class Tree{

        TreeNode* root;
        int size;

public:

        Tree();         //constructor

        void insert(string str1);       //insert a node

        string locate(string str1);     //locate a node

        TreeNode *ancestor(string str1, string str2);   //get lowest common ancestor
};


#endif

これはジェネリック ツリーのクラスです (バイナリ ツリーではありません)。位置特定機能を実装する最速の方法は何ですか? 最初にすべての子供を調べてから、兄弟を調べる必要がありますか?

4

3 に答える 3

1

ツリーが順序付けされていない場合、すべてのノードのブルートフォーステスト以外のアルゴリズムはなく、要素が見つかったときに発生します（見つかった場合）。木を扱う場合、通常、再帰が最も簡単なアプローチです。疑似アルゴリズムは次のようになります。

find(current_node,value):

if current_node.value == value
   return found
else 
   if find(current_node.left,value) == found
      return found
   else if find(current_node.right,value) == found
      return found
   else
      return not_found

もちろん、これを実際に実装するときは、nullポインタなどをテストする必要があります。ツリーに他の制約がなければ、漸近的な複雑さを減らすことはできません。定数係数を改善する可能性のある非再帰的アプローチまたは末尾再帰アルゴリズム（上記に基づく）を使用できる場合がありますが、そこでは大幅な改善は期待できません。

于 2013-02-22T15:49:06.733 に答える
0

ノードが順序付けられている場合、つまり、子がこのノードよりも小さく、兄弟がこのノードよりも大きい場合、比較しstr、結果に応じて、このノードを結果として取得するか、子を下方向に検索するか、兄弟と比較します

const TreeNode *TreeNode::locate(const string &str1) const
{
    int c = str.compare(str1);
    if (c == 0)
        return this;

    if (c > 0) {
        if (leftChild)
            return leftChild->locate(str1);

        return 0;
    }

    if (nextSibling)
        return nextSibling->locate(str1);

    return 0;
}

そしてツリーで

const TreeNode *Tree::locate(const string &str1) const
{
    return root->locate(str1);
}
于 2013-02-22T14:57:50.483 に答える