使用级别顺序遍历将节点插入二叉树

Question

我正在尝试编写一个函数，该函数将使用级别遍历将元素插入二叉树。我遇到的问题是，当我在将新节点插入树中后打印级别遍历时，它会在无限循环中打印元素。数字1 2 3 4 5 6 7 8继续在终端上竞速。我很感激任何关于如何纠正这种情况的指针和建议。

typedef struct BinaryTreeNode { 
    int data; 
    BinaryTreeNode * left; 
    BinaryTreeNode * right; 
} BinaryTreeNode; 

这是水平序遍历打印的元素：

void LevelOrder(BinaryTreeNode *root) { 
BinaryTreeNode *temp; 
std::queue<BinaryTreeNode*> Q {}; 

if(!root) return; 

Q.push(root); 

while(!Q.empty()) { 
    temp = Q.front(); 
    Q.pop(); 

    //process current node 
    printf("%d ", temp -> data); 

    if(temp -> left) Q.push(temp -> left); 
    if(temp -> right) Q.push(temp -> right); 
} 
} 

这是我通过修改电平顺序遍历技术

void insertElementInBinaryTree(BinaryTreeNode *root, int element) { 
BinaryTreeNode new_node = {element, NULL, NULL}; 

BinaryTreeNode *temp; 
std::queue<BinaryTreeNode*> Q {}; 

if(!root) { 
    root = &new_node; 
    return; 
} 

Q.push(root); 

while(!Q.empty()) { 
    temp = Q.front(); 
    Q.pop(); 

    //process current node 
    if(temp -> left) Q.push(temp -> left); 
    else { 
     temp -> left = &new_node; 
     Q.pop(); 
     return; 
    } 

    if(temp -> right) Q.push(temp -> right); 
    else { 
     temp -> right = &new_node; 
     Q.pop(); 
     return; 
    } 
} 
} 

MAIN

插入一个元素到树

int main() { 
BinaryTreeNode one = {1, NULL, NULL}; // root of the binary tree 
BinaryTreeNode two = {2, NULL, NULL}; 
BinaryTreeNode three = {3, NULL, NULL}; 
BinaryTreeNode four = {4, NULL, NULL}; 
BinaryTreeNode five = {5, NULL, NULL}; 
BinaryTreeNode six = {6, NULL, NULL}; 
BinaryTreeNode seven = {7, NULL, NULL}; 

one.left = &two; 
one.right = &three; 

two.left = &four; 
two.right = &five; 

three.left = &six; 
three.right = &seven; 

insertElementInBinaryTree(&one, 8); 

LevelOrder(&one); 
printf("\n"); 

return 0; 
} 

Answer 1

在此行中

temp -> left = &new_node; 

您正在temp->left指向一个局部变量，这将在函数返回之后不再存在。任何尝试访问它都是未定义的行为。