C语言深入浅出解析二叉树

C语言深入浅出解析二叉树攻略

什么是二叉树

二叉树是一种树形数据结构，其每个节点最多只有两个子节点，分别称为其左子节点和右子节点。一般采用链式存储方式来实现二叉树，也可以使用数组来存储。

二叉树的遍历

二叉树的遍历分为三种方式：前序遍历，中序遍历和后序遍历。

前序遍历

前序遍历的顺序是先遍历根节点，然后遍历左子树，最后遍历右子树。可以使用递归或栈来实现。

void preorder(BTNode *root){
    if(root == NULL){
        return;
    }
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

中序遍历

中序遍历的顺序是先遍历左子树，然后遍历根节点，最后遍历右子树。同样可以使用递归或栈来实现。

void inorder(BTNode *root){
    if(root == NULL){
        return;
    }
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

后序遍历

后序遍历的顺序是先遍历左子树，然后遍历右子树，最后遍历根节点。同样可以使用递归或栈来实现。

void postorder(BTNode *root){
    if(root == NULL){
        return;
    }
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

二叉树的操作

创建二叉树

可以先通过前序遍历或中序遍历的结果来创建二叉树。

BTNode* buildTree(char *preorder, char *inorder, int len){
    if(len <= 0){
        return NULL;
    }
    BTNode *root = (BTNode *)malloc(sizeof(BTNode));
    root->data = *preorder;
    int root_pos;
    for(root_pos = 0; root_pos < len; root_pos++){
        if(*(inorder + root_pos) == *preorder){
            break;
        }
    }
    root->left = buildTree(preorder + 1, inorder, root_pos);
    root->right = buildTree(preorder + root_pos + 1, inorder + root_pos + 1, len - root_pos - 1);
    return root;
}

插入节点

向二叉树中插入节点时，需要先找到要插入的位置，然后将节点插入到该位置。插入节点的方式有两种，一种是插入左子树，一种是插入右子树。

void insertNode(BTNode *root, int data, int direction){
    BTNode *new_node = (BTNode *)malloc(sizeof(BTNode));
    new_node->data = data;
    new_node->left = NULL;
    new_node->right = NULL;
    if(direction == 0){  //左子树
        if(root->left == NULL){
            root->left = new_node;
        }else{
            insertNode(root->left, data, direction);
        }
    }else{  //右子树
        if(root->right == NULL){
            root->right = new_node;
        }else{
            insertNode(root->right, data, direction);
        }
    }
}

示例

下面是一个建立二叉树并进行遍历的示例。

int main(){
    char *preorder = "ABDFGCEH";
    char *inorder = "BFDGACEH";
    BTNode *root = buildTree(preorder, inorder, strlen(preorder));
    printf("preorder: ");
    preorder(root);
    printf("\n");
    printf("inorder: ");
    inorder(root);
    printf("\n");
    printf("postorder: ");
    postorder(root);
    printf("\n");
    return 0;
}

输出结果为：

preorder: A B D F G C E H 
inorder: B F D G A C E H 
postorder: B F G D H E C A 

下面是一个插入节点的示例。

int main(){
    char *preorder = "ABDFGCEH";
    char *inorder = "BFDGACEH";
    BTNode *root = buildTree(preorder, inorder, strlen(preorder));
    insertNode(root, 1, 0);
    printf("preorder: ");
    preorder(root);
    printf("\n");
    return 0;
}

输出结果为：

preorder: A B D F G C E H 1