利用一维数组构造二叉树

定义结构体

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);
}
本作品采用《CC 协议》,转载必须注明作者和本文链接
blabla
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!