C++ - 指定された順序と事前順序を持つバイナリ ツリーを見つけようとしました。再帰的アプローチに従っていますが、間違った出力が得られます。

閉まっている。この質問にはデバッグの詳細が必要です。現在回答を受け付けておりません。

質問を編集して、目的の動作、特定の問題またはエラー、問題の再現に必要な最短のコードを含めます。これは他の人が質問に答えるのに役立ちます。

閉鎖

3 年間前

。

この質問を改善してください

私は問題を解決するために再帰的アプローチに従っています。コードに構文エラーはありません

/**************** **We are given Inorder and Preorder . We have to find the Binary Tree.** ***************/

#include <iostream>
using namespace std;
#include <queue>
template<typename T>
/* Class Defination */
class BinaryTreeNode
{
public:
    T data;
    BinaryTreeNode *left;
    BinaryTreeNode *right;

    BinaryTreeNode(T data)
    {
        this->data = data;
        left = NULL;
        right = NULL;
    }
    
    ~BinaryTreeNode()
    {
        delete left;
        delete right;
    }
};

/* *Function to print to the Tree* */
void printTreeLevelWise(BinaryTreeNode<int> *root)
{
    if (root == NULL)
    { //Base case
        return;
    }
    queue<BinaryTreeNode<int>*> pendingNodes;
    pendingNodes.push(root);
    while (pendingNodes.size() != 0)
    {
        BinaryTreeNode<int> *front = pendingNodes.front();
        pendingNodes.pop();
        cout << front->data << ":";
        if (front->left != NULL)
        {
            cout << "L" << front->left->data;
            pendingNodes.push(front->left);
        }
        if (front->right != NULL)
        {
            cout << "R" << front->right->data;
            pendingNodes.push(front->right);
        }
        cout << endl;
    }
    
}

/* **Building the  Tree** */
BinaryTreeNode<int>* buildTreeHelper(int *in,
                                     int *pre,
                                     int inS,
                                     int inE,
                                     int preS,
                                     int preE)
{
    
    if (inS > inE)
    {
        return NULL;
    }
    
    int rootData = pre[preS];
    int rootIndex = -1;
    for (int i = inS; i <= inE; i++)
    {
        if (in[i] == rootData)
        {
            rootIndex = i;
            break;
        }
    }
    
    int lInS = inS;
    int lInE = rootIndex - 1;
    int lPreS = preS + 1;
    int lPreE = lInE - lInS + lPreS;
    int rPreS = lPreE + 1;
    int rPreE = preE;
    int rInS = rootIndex + 1;
    int rInE = inE;
    
    BinaryTreeNode<int> *root = new BinaryTreeNode<int>(rootData);
    root->left = buildTreeHelper(in, pre, lInS, lInE, lPreS, lPreE);
    root->left = buildTreeHelper(in, pre, rInS, rInE, rPreS, rPreE);
    return root;
}

BinaryTreeNode<int>* buildTree(int *in, int *pre, int size)
{
    return buildTreeHelper(in, pre, 0, size - 1, 0, size - 1);
}

int main()
{
    
    int in[] = { 4, 2, 5, 1, 8, 6, 9, 3, 7 };
    int pre[] = { 1, 2, 4, 5, 3, 6, 8, 9, 7 };
    BinaryTreeNode<int> *root = buildTree(in, pre, 9);
    printTreeLevelWise(root);
    delete root;
    return 0;
}

コードが適切にフォーマットされていることを確認することをお勧めします。編集ウィンドウで生のコードを確認する前に、コンパイルするために大槌で作業を開始しました。フォーマッタで叩いてみたのですが、クリーンアップしてコンパイルできるようになりましたが、元のバージョンを見てゴミのように見えたために質問をスルーしたすべての人々のことを考えてください。

– user4581301

2020 年 9 月 4 日 21:47

1

間違った期待される出力を質問に追加することを強くお勧めします。これは、潜在的な回答者をあなたが解決しようとしているバグに導くのに役立ちます。

– user4581301

20 年 9 月 4 日20 21:50

------------------------

少なくとも 2 行目は root->right = ...: である必要があります。

root->left = buildTreeHelper(in, pre, lInS, lInE, lPreS, lPreE);
root->left = buildTreeHelper(in, pre, rInS, rInE, rPreS, rPreE);

1

1

なんて愚かなことだ。このような小さな間違いは見つけるのが難しくなります。ところで、ありがとうございます。

– ジェイ・プラタップ

2020 年 9 月 5 日 16:55