Как построить двоичное дерево в порядке уровней

Question

Я изучаю структуры данных и пытаюсь построить бинарное дерево, вставляя узлы в порядке уровней, но при этом у меня мало проблем. Я хочу вставить узлы в двоичное дерево, просто зная количество узлов, которые есть в дереве в данный момент, путем прямого перехода к родительскому узлу без возврата. Это то, что я написал до сих пор

Дерево. cpp

#include <iostream>
#include <cstdlib>
#include <cmath>


struct treeStruct {
    int data;

    struct treeStruct* parent;
    struct treeStruct* left;
    struct treeStruct* right;

    treeStruct() {
        data = 0;

        parent = NULL;
        left = NULL;
        right = NULL;
    }
};

void printInOrder(treeStruct* root) {
    if(root != NULL) {
        std::cout << root->data << "\t";
        printInOrder(root->left);
        printInOrder(root->right);
    }
}


void printPreOrder(treeStruct* root) {
    if(root != NULL) {
        printPreOrder(root->left);
        std::cout << root->data << "\t";
        printPreOrder(root->right);
    }   
}


void printPostOrder(treeStruct* root) {
    if(root != NULL) {
        printPostOrder(root->left);
        printPostOrder(root->right);
        std::cout << root->data << "\t";
    }
}


treeStruct* insertNode(treeStruct* parent, int data, int dir) {
    treeStruct* node = new treeStruct();

    if(parent == NULL) {
        node->data = data;
    }
    else {
        if(dir == 1) {
            node->data = data;
            node->parent = parent;
            parent->left = node;
        }
        else if(dir == 2) {
            node->data = data;
            node->parent = parent;
            parent->right = node;
        }
    }   

    return node;
}


treeStruct* constructInLevelTree(int* data, int len) { //having trouble in here
    int level = -1;
    int noOfNodes = 0;
    treeStruct* root = NULL;

    for(int i = 0; i < len; ++i) {
        if(level == -1) {
            root = insertNode(NULL, data[i], 0);
            ++level;
            ++noOfNodes;
        }
        else if(pow(2, level) >= noOfNodes) {
            treeStruct* node = root;
            treeStruct* parent = root->parent;
            int scanCount = 0;

            while(scanCount < noOfNodes) {
                if((scanCount % 2) == 0) {
                    if(node != NULL) {
                        parent = node;
                        node = node->left;
                    }
                }
                else {
                    if(node != NULL) {
                        parent = node;
                        node = node->right;
                    }
                }

                ++scanCount;
            }

            if((scanCount % 2) == 0)
                insertNode(parent, data[i], 1);
            else
                insertNode(parent, data[i], 2);

            ++noOfNodes;
        }
        else {
            ++level;
        }
    }

    return root;
}


int main(int argc, char* argv[]) {
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    treeStruct* root = constructInLevelTree(data, sizeof(data) / sizeof(int));

    printInOrder(root);
    printPreOrder(root);
    printPostOrder(root);

    return EXIT_SUCCESS;
}

Answer 1

Если вы хотите создать дерево в порядке уровней, на любом этапе создания ваше дерево будет полным двоичным деревом (обратите внимание на разницу между полным и полным двоичным деревом). Вы можете использовать этот инвариант эффективно. Здесь возможны два подхода

1. Использование массивов: массив можно использовать для эффективного представления полного двоичного дерева. int data [] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}; если в узле уровня вставлены слева направо и прогоны индекса начинаются с 1 (root в индексе 1), для любого узла в индексе n дочерние элементы имеют индекс (2 * n) и (2 * n + 1) для любой узел с индексом n, родительский с индексом n / 2. Так что, если вы хотите создать на уровне дерева, просто продолжайте добавлять новый узел в конец массива. Если вы следуете книге Алгоритмов по Cormen, проверьте heapsort для более подробной информации об этом представлении
2. Использование связанной структуры: Если вы хотите использовать связанную структуру (структура узла, имеющая родительский, левый и правый дочерние указатели), вы можете все еще используется тот факт, что в полном двоичном дереве, если узлы отмечены обходом уровня (слева направо), родительский узел в индексе n будет иметь индекс n / 2. Поэтому, прежде чем вставить новый узел, вы можете вычислить путь от root. Например, при добавлении 11 путь прохождения должен быть root -> 2 -> 5 -> 11.

Answer 2

Это то, что я написал после предложений @ Md Golam Rahman Tushar и @ nkvns

Tree. cpp

#include <iostream>
#include <cstdlib>
#include <cmath>
#include <vector>


struct treeStruct {
    int data;

    struct treeStruct* parent;
    struct treeStruct* left;
    struct treeStruct* right;

    treeStruct() {
        data = 0;

        parent = NULL;
        left = NULL;
        right = NULL;
    }
};

void printInOrder(treeStruct* root) {
    if(root != NULL) {
        std::cout << root->data << "\t";
        printInOrder(root->left);
        printInOrder(root->right);
    }
}


void printPreOrder(treeStruct* root) {
    if(root != NULL) {
        printPreOrder(root->left);
        std::cout << root->data << "\t";
        printPreOrder(root->right);
    }   
}


void printPostOrder(treeStruct* root) {
    if(root != NULL) {
        printPostOrder(root->left);
        printPostOrder(root->right);
        std::cout << root->data << "\t";
    }
}


void insertNode(treeStruct** parent, int data, int dir) {
    treeStruct* node = new treeStruct();

    if(*parent != NULL) {
        if(dir == 1) {
            node->data = data;
            node->parent = *parent;
            (*parent)->left = node;
        }
        else if(dir == 0) {
            node->data = data;
            node->parent = *parent;
            (*parent)->right = node;
        }
    }
    else {
        node->data = data;
        *parent = node;
    }
}


void getStackTrace(int nodeNo, std::vector<char>& stackTrace) {
    stackTrace.clear();
    int res;

    do {
        nodeNo = nodeNo / 2;
        if((nodeNo == 1) || (nodeNo == 0))
            stackTrace.push_back('T');
        else if(nodeNo % 2 == 0)
            stackTrace.push_back('L');
        else
            stackTrace.push_back('R');
    } while(nodeNo > 1);
}


treeStruct* constructInLevelTree(int* data, int len) {
    int noOfNodes = 0;
    treeStruct* root = NULL;
    std::vector<char> stackTrace;

    for(int i = 0; i < len; ++i) {
        if(i == 0) {
            insertNode(&root, data[i], -1);
            std::cout << "\ninserted root node" << std::endl;
        }
        else {
            getStackTrace(noOfNodes + 1, stackTrace);
            treeStruct* parentNode;
            std::vector<char>::reverse_iterator stackItr = stackTrace.rbegin();

            std::cout << "\nfor data " << data[i] << " taverse is:" << std::endl;
            while(stackItr != stackTrace.rend()) {
                std::cout << (*stackItr) << "\t";
                if((*stackItr) == 'T')
                    parentNode = root;
                else if((*stackItr) == 'L')
                    parentNode = parentNode->left;
                else
                    parentNode = parentNode->right;

                ++stackItr;
            }

            insertNode(&parentNode, data[i], (i % 2));
        }

        ++noOfNodes;
    }

    return root;
}


int main(int argc, char* argv[]) {
    int data[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for(int i = 0; i < sizeof(data) / sizeof(int); ++i)
        std::cout << data[i] << "\t";

    std::cout << "\n" << std::endl;

    treeStruct* root = constructInLevelTree(data, sizeof(data) / sizeof(int));

    std::cout << "\nIn Order traversal" << std::endl;
    printInOrder(root);

    std::cout << "\nPre Order traversal" << std::endl;
    printPreOrder(root);

    std::cout << "\nPost Order traversal" << std::endl;
    printPostOrder(root);

    std::cout <<"\n" << std::endl;

    return EXIT_SUCCESS;
}