Функция Void для вычисления веса узла, на который указывает
Мне нужно написать функцию 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
Решение
Прежде всего,
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.
Другие решения
Попробуйте что-то вроде:
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 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;
}
}
Ответ на
- использование рекурсия и
- использование целочисленный тип возврата.
Это будет полностью аналогично (уже существует) 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. В этом случае пожалуйтесь учителю (я это имею в виду!) И перепишите вышеприведенный код — изменения тривиальны, кроме лямбды. Подробнее об этом:
Мой код использует алгоритм (std::accumulate) а не петля. Существует общее мнение, что это не так, поскольку он абстрагирует ненужные детали и должен быть изучен в первую очередь на C ++. Но опять же, это идеалистично и, вероятно, не так. Заменить его петлей достаточно легко:
int weight{};
for (iterator i{p}, end{}; i != end; ++i)
weight += n->weight;
Вау, это еще короче. Но это хуже по ряду причин, среди которых тот факт, что мы больше не можем сделать weight const,
Наконец, почему я рекомендую использовать рекурсию? — Потому что концептуально это намного проще и почти наверняка более эффективно. Конечно, теоретически это может привести к переполнению стека. Однако на практике это требует огромный (или чрезвычайно вырожденное) дерево, чтобы вызвать переполнение стека здесь. Это, конечно, не неслыханно, и надежная библиотека общего назначения позволит избежать этого, но для большинства практических приложений это вполне приемлемо.