Skip to main content

Recursive Creation of a Binary Tree

1. Binary Tree Definition​

First, we define the node structure and binary tree type:

typedef char ElemType;

typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

2. Recursively Creating a Binary Tree from an Extended Preorder Sequence​

Given the extended preorder sequence +-A##*F##G##C##, we can recursively create a binary tree. The specific implementation code is as follows:

#include <stdio.h>
#include <stdlib.h>

typedef char ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// Function declaration
BiTree CreateBiTree();

// Global variable for traversing the extended preorder sequence
char *preOrderSeq;

// Main function
int main() {
    // Initialize the extended preorder sequence
    preOrderSeq = "+-A##*F##G##C##";
    // Create binary tree
    BiTree tree = CreateBiTree();
    return 0;
}

// Recursively create binary tree
BiTree CreateBiTree() {
    char ch = *preOrderSeq++;
    if (ch == '#') {
        return NULL;
    } else {
        BiTree node = (BiTree)malloc(sizeof(BiTNode));
        node->data = ch;
        node->lchild = CreateBiTree();
        node->rchild = CreateBiTree();
        return node;
    }
}