在树中插入新节点

Question

我想编写一个名为 tree 的 class 来创建 Data Type Tree。我想要 class tree 中的一个函数，它将自动创建节点并在节点中逐级（逐行）插入值。为此，我还创建了 Queue 数据类型来存储节点的 left 和 right 的地址正在填充。但是当我使用 preOrder Traversal 遍历树时，我刚刚发现 1 打印在我的屏幕上。 ❤️ 在这方面帮助我。

#include<iostream>
using namespace std;

struct treeNode;

struct node{
    treeNode * address;
    node * next;
};

class queue{
    node *front, *rear;
    public:
    queue(){
        front=NULL;
        rear=NULL;
    }
    void enQueue(treeNode *& item){
        node *temp=new node;
        temp->address=item;
        temp->next=NULL;
        if(front==NULL){
            front=temp;
            rear=temp;
        }
        else{
            rear->next=temp;
            rear=temp;
        }
    }
    treeNode *& deQueue(){
        treeNode *& temp=front->address;
        front=front->next;
        return(temp);
    }
} Q;

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

class tree{
  public:
    treeNode * root;
    tree(){
        root=NULL;
    }
    void iTree(int item){
        treeNode *temp=new treeNode;
        temp->data=item;
        temp->left=NULL;
        temp->right=NULL;
        if(root==NULL){
            root=temp;
            Q.enQueue((root->left));
            Q.enQueue((root->right));
        }
        else{
            treeNode *& Temp=Q.deQueue();
            Temp=temp;
            Q.enQueue(Temp->left);
            Q.enQueue(Temp->right);
        }
    }
};

void preOrder(treeNode *root){
    if(root!=NULL){
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

void main(){
    tree T;
    T.iTree(1);
    T.iTree(2);
    T.iTree(3);
    T.iTree(4);
    
    preOrder(T.root);
    
}

Answer 1

#include<iostream>
using namespace std;

// Prortotypes
struct treeNode;

// Queue required for Tree
struct node{
    treeNode *address;
    node *next;
};

class queue{
    node *front, *rear;
  public:
    queue(){
        front=NULL;
        rear=NULL;
    }
    void enQueue(treeNode *);
    treeNode * deQueue();
} Q;
void queue::enQueue(treeNode *item){
    node *temp=new node;
    temp->address=item;
    temp->next=NULL;
    if(front==NULL){
        front=temp;
        rear=temp;
    }
    else{
        rear->next=temp;
        rear=temp;
    }
}
treeNode * queue::deQueue(){
    treeNode *temp=front->address;
    front=front->next;
    return(temp);
}

// Node of Tree
struct treeNode{
    int data;
    treeNode *left;
    treeNode *right;
};

// Implementating TREE Data Structure
class tree{
    treeNode *root;
  public:
    tree(){
        root=NULL;
    }
    void insertTree(int);
    treeNode * rtnRoot();
    
};

// Insert function 
// (To insert new nodes in Tree)
void tree::insertTree(int item){
    treeNode *temp=new treeNode;
    temp->data=item;
    temp->left=NULL;
    temp->right=NULL;
    if(root==NULL){
        root=temp;
        Q.enQueue(root);
        Q.enQueue(root);
    }
    else{
        treeNode *TEMP=Q.deQueue();
        if(TEMP->left==NULL){
            TEMP->left=temp;
            Q.enQueue(TEMP->left);
            Q.enQueue(TEMP->left);
        }
        else{
            TEMP->right=temp;
            Q.enQueue(TEMP->right);
            Q.enQueue(TEMP->right);
        }
    }
}
// root return function
treeNode * tree::rtnRoot(){
    return(root);
}

// preOrder Traversal
void preOrder(treeNode *root){
    if(root!=NULL){
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// Main function
void main(){
    tree T;
    for(int i=1;i<=10;i++){
        T.insertTree(i);
    }
    
    preOrder(T.rtnRoot());
}

我之前做错了。我正在存储节点的左侧和右侧，它们总是初始化为 NULL 指针。这次我将节点的地址存储在队列中两次，以便我可以在该节点的左侧和右侧存储值。请参阅代码以获得更清晰的信息。抱歉荒谬的解释，但我想通了。感谢社区的支持。

在树中插入新节点

Insertion of new nodes in a Tree

c++

tree

insertion