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。在这种情况下，向老师抱怨（我是认真的！）并重写上面的代码——除了 lambda 之外，这些变化都是微不足道的。更多关于这个：

我的代码使用算法 ( 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 回答
0

是否允许递归？如果是这样，我想我可以像这样简单：

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 corresponding sub-tree
    if(p) {
        // compute the weights of both children first
        computeWeight(p->left);
        computeWeight(p->right);

        // compute the weight of this node, taking into account its children
        int l_weight = p ? p->left->info.weight: 0;
        int r_weight = p ? p->right->info.weight: 0;
        p->info.weight = 1 + l_weight + r_weight;
    }

}
于 2013-11-12T14:16:59.977 回答