c++ - 如何按级别顺序构造二叉树

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

如果要按级别顺序创建树，则在创建的任何步骤中，树都将是完整的二叉树(请注意完整和完整的二叉树之间的区别)。您可以有效地使用此不变式。这里有两种可能的方法

使用数组:数组可以有效地表示完整的二叉树。
int data [] = {1,2,3,4,5,6,7,8,9,10};
如果在一个级别节点中从左到右插入并且索引运行从1开始(根在索引1处)，
对于索引为n的任何节点，子节点的索引为(2 * n)和(2 * n +1)
对于索引为n的任何节点，父节点的索引为n / 2
因此，如果您想明智地创建树级别，只需继续在树尾添加新节点即可。
数组。
如果您遵循Cormen编写的Algorithmbook，请检查heapsort有关此表示形式的更多详细信息

使用链接结构:如果要使用链接结构(具有父，左，右子指针的节点结构)，您仍然可以使用以下事实:如果节点通过级别遍历(从左到右)标记，则在完整的二叉树中，索引为n的节点的父节点将为索引n / 2。因此，在插入新节点之前，您可以从根目录计算路径。例如，添加11时，遍历路径应为root-> 2-> 5->11。