二叉树的制作

Question

我得到了完整二叉树的链表表示，格式如下：

我必须将链表转换为完整的二进制 tree.I 我正在使用队列来执行 same.I 我正在将根存储在队列中，将其存储在一个变量中，将其指向一个新节点我正在制作然后存储左指针和右指针并再次执行此操作但是当对自制 tree.For 例如进行预序遍历时我只得到一个节点作为输出。链表是 1->2->3->4->5->NULL 但在预序遍历时我得到 1 作为输出。

void convert(node *head,TreeNode * &root)
 {
     if(head==NULL){
        root=NULL;
        return;
    }
    queue<struct TreeNode* >Q;
    Q.push(root);     // Pushing root which is Null at start.
    while(head!=NULL){
        struct TreeNode * x=Q.front();     // storing
        Q.pop();                   //Popping
        x=new TreeNode;           //pointing this null pointer to a new node 
        x->data=head->data;      // storing data
        x->left=NULL;           //Making left of this point to NuLL
        x->right=NULL;         //Making right of this point to NuLL
        if(!root)root=x;      // If root is null point it to x.
        Q.push(x->left);      // Push the left child pointer which is NULL
        Q.push(x->right);     // Push the right child pointer which is NULL
        head=head->next;    // Move further in linked list.
     }
  }

Answer 1

我不会post一个完整的答案，但我会提供一些调试帮助。

这是循环的第一个树迭代，以及关于变量如何变化的注释。
（当你在脑海中跟踪程序时，把这样的东西写在纸上是一个很好的主意。它比调试器视图更短暂，并且能够在调试时及时回溯是很有价值的。）

queue<struct TreeNode* >Q;          // Q: []
Q.push(root);                       // Q: [NULL]
while(head!=NULL){
    struct TreeNode * x=Q.front();  // x = NULL, Q: [NULL]
    Q.pop();                        // Q: []
    x=new TreeNode;                 // x: -> TreeNode {}
    x->data=head->data;             // 
    x->left=NULL;                   // 
    x->right=NULL;                  // x: ->TreeNode {data: data of initial head, 
                                    //                left: NULL, right:NULL}
    if(!root)root=x;                // root: ->TreeNode {data: data of initial head, 
                                    //                   left: NULL, right:NULL}
    Q.push(x->left);                // Q: [NULL]
    Q.push(x->right);               // Q: [NULL, NULL]
    head=head->next;                // Move further in linked list.
}
{
    struct TreeNode * x=Q.front();  // x = NULL, Q: [NULL, NULL]
    Q.pop();                        // Q: [NULL]
    x=new TreeNode;                 // x: -> TreeNode {}
    x->data=head->data;             // 
    x->left=NULL;                   // 
    x->right=NULL;                  // x: ->TreeNode {data: head->data, left: NULL, right:NULL}
    if(!root)root=x;                // root: still ->TreeNode {data: data of initial head, 
                                    //                         left: NULL, right:NULL}
    Q.push(x->left);                // Q: [NULL, NULL]
    Q.push(x->right);               // Q: [NULL, NULL, NULL]
    head=head->next;                // Move further in linked list.
}
{
    struct TreeNode * x=Q.front();  // x = NULL, Q: [NULL, NULL, NULL]
    Q.pop();                        // Q: [NULL, NULL]
    x=new TreeNode;                 // x: -> TreeNode {}
    x->data=head->data;             // 
    x->left=NULL;                   // 
    x->right=NULL;                  // x: ->TreeNode {data: head->data, left: NULL, right:NULL}
    if(!root)root=x;                // root: still ->TreeNode {data: data of initial head, 
                                    //                         left: NULL, right:NULL}
    Q.push(x->left);                // Q: [NULL, NULL, NULL]
    Q.push(x->right);               // Q: [NULL, NULL, NULL, NULL]
    head=head->next;                // Move further in linked list.
}

如您所见，您正在向队列中推送和弹出一系列空指针。
您永远不会将队列中的值用于任何事情。

为了澄清问题，假设您有一个整数队列并执行了以下操作：

struct S { int x; };
S s;
s.x = 0;
queue<int> q;
q.push(s.x);
int y = q.front();
y = 96;

我很确定您不会期望 s.x 的值突然变成 96 而不是 0。
指针的工作方式完全相同。

你也永远不会修改你创建的根节点，这就是为什么你只能得到一个单节点树（其他节点只是内存泄漏）。

你可以

弹出一个树节点指针
从列表中获取接下来的两个个元素（如果它们存在）
根据需要从列表元素中创建新节点
将弹出节点的左右指针设置为这两个新的
将新指针推入队列
重复

二叉树的制作

Making of a binary tree

c++

binary-tree