二叉树遍历以枚举所有斐波那契值的排列

Question

我正在进行这个项目的工作，这是我的兴趣所在，并且一直在回来这个项目…… 我试图创建一个算法来枚举斐波那契值的二叉树的值集：算法我将用于打印此树的排列：

1. 打印根节点的值（结果：([root 0]=5)） 2. 下降到左子节点[left 1] 3. 打印新的左节点[left 1]和右兄弟节点的值（结果：([left 1] 3，[right 1] 2)） 4. 如果右兄弟节点[right 1]有子节点，则遍历该右节点[right 1]，枚举其值以及其兄弟左节点[left 1]（结果：[left 1] 3，[left 3] 1，[right 3] 1） 5. 下降到左子节点[left 2]，如第2步 6. 打印公共左父节点[left 1]的新左节点值[left 2] 2和右兄弟节点值[right 2] 1；同时遍历并枚举根节点的每个级别的右节点的结果。因此，在上述树示例中，遍历树以获取排列的枚举结果为：([left 2] 2，[right 2] 1，[right 1] 2)，([left 2] 2，[right 2] 1，[left 3] 1，[right 3] 1)) 7. 没有左子节点可下降，因此停止

每个集合的值应该加起来等于根节点的值。我认为我尝试描述算法中的每个步骤的方法可能不是完全清晰的 - 对于编写算法步骤的最佳实践的任何帮助对我也很有用。

我期望的结果是，枚举上面的树将是：([root 0] 5)，([left 1] 3，[right 1] 2)，([left 1] 3，[left 3] 1，[right 3] 1)，([left 2] 2，[right 2] 1，[right 1] 2)，([left 2] 2，[right 2] 1，[left 3] 1，[right 3] 1)

我想采用递归方法，并将其作为方法并入我创建的二进制结构的类中。所以这不是关于构建树结构，而是按照上述方法遍历它，或者产生相同的结果的方法。

有谁能帮我进一步？任何帮助都将不胜感激。

向我的`FibTree Class`添加集合打印方法：

FibTree头文件（代码片段）：

class FibTree {

public:
    class Node {
    public:
    int data;
        Node const* left;
        Node const* right;
        Node const* parent;
        int n;
        int level;
        int index;

        Node (void);

    };

    Node const* root; // 'root' pointer to constant Node
    FibTree (int);
    Node const* getRoot(void);

    void startWriteSets(Node const* root); // Write all sets of tree

private:
    static Node* buildTree( int n, int level = 0, int i = 1, Node* parent = NULL );
    // Used by startWriteSets
    void writeSets(std::vector<Node const*> &setsList, Node const* cur);

FibTree CPP文件（代码片段）：

// FibTree Constructor
FibTree::FibTree(int n) {
    this->root = buildTree( n );
};

// Getters
FibTree::Node const* FibTree::getRoot(void) {
    return this->root;
}

// Write sets of tree
void FibTree::startWriteSets(Node const* root) {
    std::vector<Node const*> setsList;
    std::cout << root->data;
    writeSets(setsList, root);
}

// Private FibTree methods
FibTree::Node* FibTree::buildTree( int n, int level, int i, Node* parent ) { // Build Tree structure
    Node* thisNode = new Node();
    thisNode->n = n;
    thisNode->level = level;
    thisNode->index = i;
    thisNode->parent = parent;
    if (n < 2) {
         thisNode->left = NULL;
         thisNode->right = NULL;
         thisNode->data = n;
         return thisNode;
    } else {
         thisNode->left = buildTree( n - 1 , level + 1, i*2, thisNode );
         thisNode->right = buildTree( n - 2, level + 1, i*2+1, thisNode );
         thisNode->data = thisNode->left->data + thisNode->right->data;
         return thisNode;
    }
}

void FibTree::writeSets(std::vector<Node const*> &setsList, Node const* cur) {
    std::vector<Node const*>::iterator nodeIterator;

    // Displays all preceding left values
    for (nodeIterator = setsList.begin();
        nodeIterator != setsList.end(); nodeIterator++) {
        std::cout << *nodeIterator->data;
    }   
    std::cout << cur->left->data;
    std::cout << cur->right->data;

    setsList.push_back(cur->left);
    writeSets(setsList,cur->right);
    setsList.pop_back();
}


// FibTree Node constructor
FibTree::Node::Node()
: data( 0 ),
left( NULL ),
right( NULL ),
parent( NULL ),
n( 0 ),
level( 0 ),
index( 0 )
{
};

我在`void FibTree::writeSets`中的`std::cout << *nodeIterator->data;`处遇到编译错误，错误提示为：

_error: request for member 'data' in '* nodeIterator. __gnu_cxx::__normal_iterator<_Iterator, _Container>::operator-> with _Iterator = const FibTree::Node**, Container = std::vector >', which is of non-class type 'const FibTree::Node*'

。请帮我查找此错误，谢谢！

- Alex2134

---

清楚地解释第6步。 - nikhil_vyas

@nikhil_vyas 我已经对我要解决的问题增加了更多的明确性。我不是专业程序员，所以你可能需要将任何建议的方法分解成可理解的块。非常感谢 Alex - Alex2134

你不能递归地遍历节点并按照你描述的顺序输出节点。你可以进行两次遍历来完成遍历。你对使用标准容器（如maps）有任何限制吗？ - Ian Thompson

我认为你的树还没有完成，或者你计划根据算法添加某种额外的遍历搜索（Left2必须有2个更多的子节点[左4] 1，[右4] 1），如果是这样的话，那么我想我可能有你需要的答案。 - Opsenas

@Opsenas 感谢您的评论，您是正确的，因为 f(n)=f(n-1)+f(n-2) [left 2] 应该有左孩子=1和右孩子=1；同样 [left 3] 应该有左孩子=1和右孩子=0，但我对零不感兴趣。 - Alex2134

Answer 1

这里的问题不是需要遍历B-Tree，这很直接。问题在于需要跟踪另一半方程的状态。也就是说，当你进入右链的第二层时，仍然需要知道[左1] = 3。

一个可能的解决方法是在向量（或其他结构）中跟踪左节点，以便...

void start(void) {
  vector<NODE*> list;
  cout << head->val;
  visit(list, head);
}

void visit(vector<NODE*> &list, NODE *cur) {
  // Displays all preceding left values.
  for (vector<NODE*> it = list.begin(); it != list.end(); it++) {
    cout << *it->val;
  }
  cout << cur->left->val;
  cout << cur->right->val;

  list.push_back(cur->left);
  visit(list, cur->right);
  list.pop_back();
}

这将为您提供正确方向上所需的内容。您需要添加适当的安全检查和另一个方向，但它应该可以让您开始。

- Aumnayan

---

谢谢。我在尝试将您上面的建议融入我的Class FibTree时遇到了麻烦。在类中，我有Node const* root;，root被传递给：void FibTree::writeSets(std::vector<Node const*> &setsList, Node const* cur){... 错误 _conversion from '__gnu_cxx::__normal_iterator<const FibTree::Node**, std::vector<const FibTree::Node*, std::allocator<const FibTree::Node*> > >' to non-scalar type 'std::vector<const FibTree::Node*, std::allocator<const FibTree::Node*> >' requested_。 - Alex2134

能否让它适用于 Node const* root 而不是 Node*？谢谢 Alex。 - Alex2134

抱歉耽搁了。你的for循环不应该是这样的吗？for(vector<Node const *>::iterator it = setsList.begin()...) { ? 转换错误似乎表明它是一个独立的向量类。 - Aumnayan

Answer 2

任何树都可以视为指向头节点的指针。节点构造函数：

Node(int val，Node* left，Node* right)

树构造函数：

Node* Tree(int n){
    return new Node(fib(n),Tree(n-1),Tree(n-2));
}

这样做可以实现，但时间复杂度呈指数级增长，建议使用动态规划来保存之前的树。

现在要实现集合，你说它们必须加起来等于根节点，例如5=3+2。在其他集合中，只需找到以3和2为集合的方式。要找到将3写成集合的方法，可以递归调用与5相同的函数。

vector < vector <int> > SetOfSets(Node * root){
    vector < vector <int> > leftSets = SetOfSets(root.left);
    vector < vector <int> > rightSets = SetOfSets(root.right);
    vector < vector <int> > ans;
    for(int i=0;i<leftSets.size();i++){
        for(int j=0;i<rightSets.size();j++){
            ans.push_back(leftSets[i].insert(leftSet[i].end(),rightSet[j].begin(),rightSet[j].end()));
        }
    }
    return ans;
}

添加代码以处理终止情况（root.val == 1），然后您就完成了。

- nikhil_vyas

---

非常感谢Nikhil，我已经构建了树形结构，我认为这样做是构建树形结构。这会返回我在示例中列出的所有集合吗？抱歉，我只是试图理解它。谢谢Alex。 - Alex2134

Answer 3

考虑到节点的结构是：

struct SNode
{
    int m_iValue;
    SNode* m_psLeft;
    SNode* m_psRight;
};

我认为最接近你想要的是：

//returns true if there are still not visited children
bool Traverse(SNode* psNode, int iDepth)
{
    if(iDepth > 0)
    {
        bool bLeftRes;
        if(psNode->m_sLeft != NULL)
        {
            bLeftResult = Traverse(psNode->m_psLeft, iDepth - 1);
        }
        else
        {
            bLeftResult = false;
        }
        bool bRightRes;
        if(psNode->m_sLeft != NULL)
        {
            bRightRes =  Traverse(psNode->m_psRight, iDepth - 1);
        }
        else
        {
            bRightRes = false;
        }
        return bLeftRes || bRightRes;
    }
    else
    {
        printf("%d ", psNode->m_iValue);
        return psNode->m_psLeft || psNode->m_psRight;
    }
}

因此，遍历调用将如下所示：

int i = 0;
printf("(");
while(Traverse(psRoot, i))
{
    printf(")\n(");
    ++i;
}
printf(")");

输出将与您的树一起显示： （5） （3 2） （2 1 1 1）

- Opsenas

---

感谢您提供的解决方案，输出结果为：(5) (3 2) (2 1 1 1)，这表明需要进行层序广度优先遍历。我需要的解决方案应该有以下预期输出：(5)(3,2)(3,1,1)(2,1,2)(2,1,1,1)。@Aumnayan建议使用向量来跟踪左节点。 - Alex2134