0

各サブツリーのノード数を計算できる void 関数を作成する必要があります。多くのサンプル コードを読みましたが、それらはすべて整数を返します。そして、非再帰的な void 関数を使用してそれらの int 関数と同じ機能を実行する方法がわかりません。

これは私がこれまでに持っているものです:

void computeWeight(treeNode<treeInfo> *p)
{
//compute the weight of the node pointed at by p    
//weight of a node is equal to the number of nodes in the correspodning subtree
if(p == NULL)
    p->info.weight = 0;
else
    p->info.weight = 1 + p->left->info.weight + p->right->info.weight;
//note that this is not a recursive function
}

これはtreeInfoの構造体です:

struct treeInfo
{   
char symb;
int weight;
};

これは、通常のバイナリ ツリー ヘッダーである binaryTree.h です。

template<class Type>
struct treeNode
{
Type info;
treeNode<Type> *left;
treeNode<Type> *right;
};
template<class Type>
class treeIterator
{
protected:
treeNode<Type> *current;
stack<treeNode<Type>*> s;

public:
treeIterator(treeNode<Type> *p)
{
    current = NULL;

    while (p != NULL)
    {
        s.push(p);
        p = p->left;
    }

    if (!s.empty())
    {
        current = s.top();
        s.pop();
    }
}

treeIterator(const treeIterator<Type>& other)
{
    current = other.current;
    s = other.s;
}

Type& operator*() 
{   return current->info;  }


treeIterator<Type>& operator++()  //pre-increment operator
{
    if (current != NULL)
    {
        current = current->right;
        while (current != NULL)
        {
            s.push(current);
            current = current->left;
        }
        if (!s.empty())
        {
            current = s.top();
            s.pop();
        }
    }
    else
        cerr << "Error: treeIterator gets out of bound" << endl;

    return *this;
}

bool operator==(const treeIterator<Type>& other)
{  return current == other.current;  }

bool operator!=(const treeIterator<Type>& other)
{  return current != other.current;  }

};

template<class Type>
class binaryTree
{
protected:
treeNode<Type> *root;

public:
binaryTree()
{   root = NULL; }

binaryTree(const binaryTree<Type>& other);
~binaryTree();

const binaryTree<Type>& operator=(const binaryTree<Type>& other);

bool empty()
{   return root == NULL;  }

int height();
int nodeCount();
int leavesCount();

void inorderTraversal(void (*visit)(treeNode<Type> *));
void preorderTraversal(void (*visit)(treeNode<Type> *));
void postorderTraversal(void (*visit)(treeNode<Type> *));

void destroy();

treeIterator<Type> begin();
treeIterator<Type> end();

void print(int inc);
void buildTreeFromArray(Type a[], int n, Type nullSymbol);  

private:
treeNode<Type>* copyTree(const treeNode<Type> *other);
void destroy(treeNode<Type> *p);
int height(treeNode<Type> *p);
int nodeCount(treeNode<Type> *p);
int leavesCount(treeNode<Type> *p);
void inorder(treeNode<Type> *p, void (*visit)(treeNode<Type> *));
void postorder(treeNode<Type> *p, void (*visit)(treeNode<Type> *));

void printTree(const treeNode<Type> *p, int indent, int inc);
treeNode<Type>* buildTree(Type a[], int n, int i, Type nullSymbol);
};

template<class Type>
void binaryTree<Type>::preorderTraversal(void (*visit)(treeNode<Type> *p))
{
//implement a non-recrusive preorder traversal of the binary tree
stack<treeNode<Type>*> stack_tree;

stack_tree.push(root);
treeNode<Type> *p = root;
while(!stack_tree.empty())
{
    treeNode<Type>* temp = stack_tree.top();
    (*visit)(temp);

    stack_tree.pop();
    if(temp ->right)
        stack_tree.push(temp ->right);
    if(temp ->left)
        stack_tree.push(temp ->left);
}
} 

template<class Type>
treeNode<Type>* binaryTree<Type>::buildTree(Type a[], int n, int i, Type nullSymbol)
{
treeNode<Type> *p = NULL;

if (i < n && a[i] != nullSymbol)
{
    p = new treeNode<Type>;
    p->info = a[i];
    p->left = buildTree(a, n, 2*i+1, nullSymbol);
    p->right = buildTree(a, n, 2*(i+1), nullSymbol);
}

return p;
}

template<class Type>
void binaryTree<Type>::buildTreeFromArray(Type a[], int n, Type nullSymbol)
{
root = buildTree(a, n, 0, nullSymbol);
}

template<class Type>
void binaryTree<Type>::printTree(const treeNode<Type> *p, int indent, int inc)
{
if (p != NULL)
{
    printTree(p->right, indent+inc, inc);
    cout << setw(indent) << p->info << endl;
    printTree(p->left, indent+inc, inc);
}
}

template<class Type>
void binaryTree<Type>::print(int inc)
{
printTree(root, 4, inc);
}

template<class Type>
int binaryTree<Type>::height(treeNode<Type> *p) 
{
if (p == NULL)
    return 0;
int HL = height(p->left);
int HR = height(p->right);
if (HL >= HR)
    return 1+HL;
else
    return 1+HR;
}

template<class Type>
int binaryTree<Type>::height()  
{
return height(root);
}

template<class Type>
int binaryTree<Type>::nodeCount(treeNode<Type> *p)  
{
if (p == NULL)
    return 0;

return 1 + nodeCount(p->left) + nodeCount(p->right);
}

template<class Type>
int binaryTree<Type>::nodeCount()  
{
return nodeCount(root);
}

template<class Type>
int binaryTree<Type>::leavesCount(treeNode<Type> *p)  
{
if (p == NULL)
    return 0;

if (p->left == NULL && p->right == NULL)
    return 1;

return leavesCount(p->left) + leavesCount(p->right);
}

template<class Type>
int binaryTree<Type>::leavesCount()  
{
return leavesCount(root);
}

template<class Type>
void binaryTree<Type>::inorder(treeNode<Type> *p, void (*visit)(treeNode<Type> *))
{
if (p != NULL)
{
    inorder(p->left, visit);
    (*visit)(p);
    inorder(p->right, visit);
}
}

template<class Type>
void binaryTree<Type>::postorder(treeNode<Type> *p, void (*visit)(treeNode<Type> *))
{
if (p != NULL)
{
    postorder(p->left, visit);      
    postorder(p->right, visit);
    (*visit)(p);
}
}

template<class Type>
void binaryTree<Type>::inorderTraversal(void (*visit)(treeNode<Type> *))
{
inorder(root, visit);
}

template<class Type>
void binaryTree<Type>::postorderTraversal(void (*visit)(treeNode<Type> *))
{
postorder(root, visit);
}

template<class Type>
treeNode<Type>* binaryTree<Type>::copyTree(const treeNode<Type> *other)
{
    if (other == NULL)
    return NULL;

treeNode *p = new treeNode<Type>;
p->info = other->info;
p->left = copyTree(other->left);
p->right = copyTree(other->right);
}

template<class Type>
binaryTree<Type>::binaryTree(const binaryTree<Type>& other)
{
root = copyTree(other.root);
}

template<class Type>
const binaryTree<Type>& binaryTree<Type>::operator=(const binaryTree<Type>& other)
{
if (this != &other)
{
    destroy(root);
    root = copyTree(other.root);
}
}

template<class Type>
void binaryTree<Type>::destroy(treeNode<Type> *p)
{
if (p != NULL)
{
    destroy(p->left);
    destroy(p->right);
    delete p;
}
}


template<class Type>
void binaryTree<Type>::destroy()
{
destroy(root);
root = NULL;
}


template<class Type>
binaryTree<Type>::~binaryTree()
{
destroy(root);
}


template<class Type>
treeIterator<Type> binaryTree<Type>::begin()
{
return treeIterator<Type>(root);
}

template<class Type>
treeIterator<Type> binaryTree<Type>::end()
{
return treeIterator<Type>(NULL);
}

#endif
4

4 に答える 4

0

初めに、

if(p == NULL)
    p->info.weight = 0;

はトラブルを求めています - 逆参照は許可されていませんNULL。

あなたがすべきことは次のようなものです：

void computeWeight(treeNode<treeInfo> *p)
{
    if (p != NULL)
    {
        int leftWeight = p->left != NULL ? p->left->info.weight : 0;
        int rightWeight = p->right != NULL ? p->right->info.weight : 0;
        p->info.weight = 1 + leftWeight + rightWeight;
    }
}

サブツリーの重みが最初に計算されることを保証するトラバーサルを利用します。
すでに実装されているため、適切なものを選択するだけで済みます。

それを使用すると、次のようになります

binaryTree<treeInfo> tree;
// ...  
// build the tree
// ...
tree.someTraversal(computeWeight);
// The weights are now computed.
于 2013-11-12T14:24:43.903 に答える
0

答えは

  • 再帰を使用し、
  • 整数の戻り値の型を使用してください。

これは、(既存の)binaryTree<Type>::height実装と完全に類似しています。

次に、非再帰的なvoid戻り関数内からその関数を呼び出して、結果に対して何かを行うことができます。

void computeWeight(treeNode<treeInfo> *p) {
    int weight = getWeight(p);
    // Do something with it.
}

int getWeight(treeNode<treeInfo>* p) {
    return p == nullptr ? 0 : p->weight + getWeight(p->left) + getWeight(p->right);
}

もちろん、演習の具体的な目的がこれを非再帰的に解決することである場合、その解決策は役に立ちません。手動で管理されたスタックを使用して再帰をエミュレートする必要があります。あなたが持っているので、treeIterator私はそれを疑っていますが、イテレータはそれを些細で無意味な演習にします:

void computeWeight(treeNode<treeInfo> *p) {
    using iterator = treeIterator<treeInfo>;
    int weight const = std::accumulate(iterator{p}, iterator{nullptr}, 0,
            [](int acc, treeNode<treeInfo>* n) { return acc + n->weight; });
}

コードに関するいくつかのメモ。

コードは C++11 を使用しています。C++11 は、言語を非常に簡単かつ安全にするため、教育の標準となるはずであり、現在 2 年間使用されており、(ここで使用されている範囲で) すべての最新のコンパイラに実装されています。ただし、プログラミング レッスンの品質を知っていると、まだ C++11 を使用することを想定していない可能性があります。その場合は、先生に文句を言って (つまり!)、上記のコードを書き直してください。ラムダ以外の変更は簡単です。これについての詳細：

std::accumulate私のコードは、ループではなくアルゴリズム ( ) を使用しています。これは ᴛʜᴇ ʀɪɢʜᴛ ᴛʜɪɴɢ™ であるというコンセンサスがあります。これは、無関係な詳細を抽象化するためであり、C++ の最初の早い段階で教えられるべきです。しかし、これも理想論であり、おそらくそうではありません。これは簡単にループに置き換えることができます:

int weight{};
for (iterator i{p}, end{}; i != end; ++i)
    weight += n->weight;

うわー、それはさらに短いです。しかし、それはいくつかの理由でさらに悪化しています。その中にはweight、const.

最後に、なぜ再帰の使用を推奨するのでしょうか? – 概念的に非常に簡単で、ほぼ確実に効率的だからです。確かに、理論的にはスタック オーバーフローが発生しがちです。ただし、実際には、ここでスタック オーバーフローをトリガーするには、巨大な(または非常に縮退した) ツリーが必要です。これは確かに前例のないことではなく、堅牢な汎用ライブラリであればここでは回避できますが、ほとんどの実用的なアプリケーションでは完全に受け入れられます。

于 2013-11-12T14:50:18.740 に答える
0

次のようなものを試してください：

 void computeWeight(treeNode<treeInfo> *p)
 {    
     std::list<treeNode<treeInfo>*> nodesToVisit;
     std::list<treeNode<treeInfo>*> nodesVisited;

     nodesToVisit.push_back(p);

     while(!nodesToVisit.empty())
     {
        treeNode<treeInfo>* parent = nodesToVisit.front();
        nodesToVisit.pop_front();


        if (parent->left != NULL)
           nodesToVisit.push_back(parent->left);

        if (parent->right != NULL)
           nodesToVisit.push_back(parent->right);

        nodesVisited.push_back(parent);
     }

     int numberOfNodes = nodesVisited.size();
  }

これの効率についてはわかりませんが、各サブツリーのノード数を計算する void 関数です。

于 2013-11-12T14:12:04.553 に答える