二叉树（非二进制搜索树）创建新节点和儿童

Question

我想实现一个方法来创建一个节点插入二进制树（而不是bst）。

struct node{ 
     struct node *left; 
     int data; 
     struct node *right; 
}; 

typedef struct node *n; 

void createNewNode() { 

    char r; // stands for response (whether or not a left or right child should be created) 
    int d; //data to be stored in a node 

    n newnode = new(struct node); //creates a new node 

    cout<<"Enter data for the new node:"<<endl; 
    cin>>d; 
    newnode->data = d; 

    cout<<"any left child? y/n"<<endl; 
    cin>>r; 
    switch (r) { 
      case 's': 
       createNewNode(); // I thought to make it recursive and if a child is going to be created, then the method will call itself all over again 
       break; 

      case 'n': 
       newnode->left = NULL; // if child is not created then pointer is NULL 
       break; 
      } 

    cout<<"any right child? y/n"<<endl; 
    cin>>r; 
    switch (r) { 
      case 's': 
       createNewNode(); //recursive method again 
       break; 

      case 'n': 
       newnode->right = NULL; // if child is not created then pointer is NULL 
       break; 
      } 
} 

，我面临的问题是，当我用递归的方法来创建一个向左或向右的孩子。我认为它并没有指向首先创建的父节点的值。我是对还是错？我想问题是我是否用我试图实现的方法将父节点链接到右侧或左侧子节点。

Answer 1

在createNewNode()函数中，您只需创建一个新节点并保留它，而不会将它们相互关联！你应该将它绑定到左或右指针。

这是你应该做的：

1. 变化从void这个函数的输出n
2. 在函数的最后返回新创建的节点
3. 在这两个开关语句，在递归调用该函数的位置，相应地将函数调用的输出分配给newnode->left或newnode->right。