c++ - 如何修复二叉树级订单打印的以下代码

Question

我已经实现了以下代码，用于二叉树中节点的级别顺序打印。但是，当节点同时具有左右子节点时，它会失败。

例如，下面是我的二叉树。

 1
  \
   2
    \
     5
    /  \
   3    6
    \
     4  

预期输出为:1 2 5 3 6 4但是，我的代码打印:1 2 5 3 4 4

我做错了什么？感觉有些指针出错了。

下面是我写的函数:

void printNodes(Node *arr[], int numOfNodes)
    {
        Node *outputArr[]={NULL};

        int j=0;

        for(int i=0; i<numOfNodes; i++)
        {
            printf("%d ",arr[i]->data);

            if(arr[i]->left!=NULL)
            {
                outputArr[j++]=arr[i]->left;
            }

            if(arr[i]->right!=NULL)
            {
                outputArr[j++]=arr[i]->right;
            }
        }

        if(j>0)
            printNodes(outputArr, j);
        else 
            return;
    }

    void levelOrder(Node * root) {
        Node *list[]={NULL};
        int ctr=0;

        if(root == NULL)
            return;

        printf("%d ",root->data);

        if(root->left != NULL)
            list[ctr++]=root->left;
        if(root->right != NULL)
            list[ctr++]=root->right;

        printNodes(list, ctr);
    }

我将在下面粘贴一些驱动程序代码:

main() {

    Example myTree;
    Node* root = NULL;

    int t;
    int data;

    std::cin >> t;

    while(t-- > 0) {
        std::cin >> data;
        root = myTree.insert(root, data);
    }

    myTree.levelOrder(root);
    return 0;
}

Answer 1

假设您出于某种原因(教育或其他原因)正在做您正在做的事情，只需对其进行最低限度的修改以执行我认为您希望您的方法执行的操作，请尝试以下操作:

void printNodes(std::vector<Node*> list) {
    std::vector<Node*> newList;

    for(int i=0; i<list.size(); i++) {
        printf("%d ",list[i]->data);

        if(list[i]->left) newList.push_back(list[i]->left);
        if(list[i]->right) newList.push_back(list[i]->right);
    }

    if(!newList.empty()) printNodes(newList);
    else return;
}

void levelOrder(Node * root) {
    if(!root) return;
    std::vector<Node*> list;

    printf("%d ",root->data);

    if(root->left) list.push_back(root.left);
    if(root->right) list.push_back(root.right);;

    printNodes(list);
}

更好的解决方案可能是根本不使用递归并执行通常的广度第一次遍历 IMO。