利用一维数组构造二叉树

blabla 的个人博客 / 0 / 0 / 创建于 5年前 / 更新于 5年前

定义结构体#

typedef struct TreeNode{
    int data;
    struct TreeNode *lChild, *rChild;
} TreeNode, *BinaryTree;

创建结点#

TreeNode *newTreeNode(int data){
    auto node = new TreeNode;
    node->data = data;
    node->lChild = node->rChild = NULL;
    return node;
}

构造二叉树#

若从 0 开始编号，结点 i 的左孩子序号为 2 i + 1，右孩子序号为 2 i + 2

BinaryTree BinaryTreeBuilder(int arr[], BinaryTree &root, int i, int n){
    if (i < n){
        root = newTreeNode(arr[i]);
        BinaryTreeBuilder(arr, root->lChild, 2 * i + 1, n);
        BinaryTreeBuilder(arr, root->rChild, 2 * i + 2, n);
    }
    return root;
}

中序遍历#

void inOrder(BinaryTree root){
    if (root){
        inOrder(root->lChild);
        cout << root->data << "  ";
        inOrder(root->rChild);
    }
}

main 函数#

int main(){
        BinaryTree root;
        int arr[] = {1, 2, 3, 4, 5, 6, 6, 6, 6};
        int len = sizeof(arr) / sizeof(int);
        BinaryTreeBuilder(arr, root, 0, len);
        inOrder(root);
}