Нерекурсивная функция добавления в двоичном дереве с использованием c ++ - PullRequest
Новая
       26

Нерекурсивная функция добавления в двоичном дереве с использованием c ++

1 голос
/ 10 июля 2011

Я пишу функцию Add для добавления рекурсивных узлов в двоичное дерево. Я столкнулся с проблемой создания только одного уровня двоичного дерева. Я отладил его, и я знаю, где проблема, но не могу понять, как это исправить. Может быть, свежая пара глаз увидит что-то, чего я не ... Проблема в том, что мой временный узел сбрасывается до корневого значения при каждом новом вызове функции и, следовательно, линейно добавляется узел. В любом случае, вот функция: 

   void BinaryTreeNonRec::add(int num){
        treeNode *temp, *parent;

        if (root==NULL) {
            root = new treeNode;
            root->data=num;
            root->left=0;
            root->right=0;
            temp=root;
            printf("value is root \n");
        } else {
            temp=root;
            while (temp!=NULL) {
                if (num <= temp->data){
                    parent = temp;
                    temp=temp->left;
                    //root =temp;
                    printf("value is to the left \n");
                } else {
                    parent =temp;
                    temp=temp->right;
                    //root=temp;
                    printf("value is to the right \n");
                }               
            }   
            parent = new treeNode;
            parent->data=num;
            parent->left=NULL;
            parent->right=NULL;
            temp=parent;
        }   
}

Спасибо за любую помощь.

Ответы [ 3 ]

2 голосов
/ 10 июля 2011

Вы не добавляете новый узел в дерево, просто запускаете дерево и заполняете родительский узел новым узлом, но никогда не добавляете его в дерево, измените код ниже: 

parent = new treeNode;
parent->data=num;
parent->left=NULL;
parent->right=NULL;
temp=parent;

Кому: 

treeNode *newNode = new treeNode;
newNode->data = num;
newNode->left = NULL;
newNode->right = NULL;

//Now insert the new node BELOW parent
if(num <= parent->data)
    parent->left = newNode;
else
    parent->right = newNode;
1 голос
/ 10 июля 2011

Проблема может заключаться в том, что вы никогда не добавляете новый узел в дерево. 

  parent = new treeNode;
  parent->data=num;
  parent->left=NULL;
  parent->right=NULL;
  temp=parent;

Вы присваиваете свой новый узел temp и parent, которые являются временными переменными и, следовательно, не существуют вне функции. Что вам нужно сделать, это назначить ваш новый узел либо родительскому -> левому, либо родительскому -> правому, в зависимости от того, с какой стороны находится ваш новый ввод, чтобы связать его с деревом. Поэтому то, что вы хотите сделать, это что-то вроде следующего: 

  temp = new treeNode;
  temp->data=num;
  temp->left=NULL;
  temp->right=NULL;
  if(num < parent->data)
     parent->left = temp;
  else
     parent->right = temp;
0 голосов
/ 08 июля 2017

Algo

  1. if root == null Создать новый узел, назначенный для Root
  2. Продолжайте итерации, основанные на сравнении с rootNode, пока не дойдете до любого конечного узла
  3. проверить, если num <= родитель (лист) Вставить в левую вставку ELSE в правую </li>

Код 

private void insertItrInBST(int num){
    Node temp = root,parent = root;

    if(root == null){
        root = getNewNode(num);
    }else{
        temp = root;

        while(temp != null){
            if(num <= root.data){
                parent = temp;
                temp = temp.left;   
            }else{
                parent = temp;
                temp = temp.right;
            }
        }
        Node newNode = getNewNode(num);
        if(num <= parent.data){
            parent.left = newNode;
        }else{
            parent.right = newNode;
        }
    }
}
...