c语言建立二叉树的算法代码

以下是C语言建立二叉树的算法代码：

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

typedef char tree_datatype;

typedef struct tree_t {
    tree_datatype data; // 数据域
    struct tree_t *lchild; // 指向左子树的结构体指针
    struct tree_t *rchild; // 指向右子树的结构体指针
} bitree_t;

// 创建二叉树
bitree_t *create_bitree() {
    bitree_t *root = NULL;
    tree_datatype ch;
    scanf("%c", &ch);
    if (ch == '#') {
        root = NULL;
    } else {
        root = (bitree_t *) malloc(sizeof(bitree_t));
        root->data = ch;
        root->lchild = create_bitree();
        root->rchild = create_bitree();
    }
    return root;
}

相关问题

使用c语言建立二叉树的算法

在C语言中创建二叉树通常涉及以下几个步骤：

1. **定义数据结构**：首先，你需要定义二叉树节点的数据结构，包括节点值、左孩子指针和右孩子指针。例如：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

2. **基本操作**：
- **初始化**：创建一个新的节点，分配内存并设置初始值。
- **插入**：通过递归的方式将新值插入到正确的子树位置，通常是先比较大小，然后选择左或右子树。
- **删除**：删除指定节点需要考虑多种情况，如无子节点、单子节点和双子节点。
- **查找**：同样递归遍历直到找到目标值或遇到空节点。

3. **构建函数**：
- **创建空树**：`TreeNode* createTree()` 或 `void insertIntoTree(TreeNode** root, int value)`。
- **插入节点**：`void insertNode(TreeNode** root, int value)`。
- **遍历树**：可以有前序、中序和后序等遍历方法，如`void inOrderTraversal(TreeNode* root)`.
- **查找**：`int searchNode(TreeNode* root, int value)`。

4. **示例代码片段**：

TreeNode* insertNode(TreeNode** root, int value) {
    if (*root == NULL) {
        *root = (TreeNode*)malloc(sizeof(TreeNode));
        (*root)->val = value;
        (*root)->left = (*root)->right = NULL;
    } else if (value < (*root)->val) {
        insertNode(&(*root)->left, value);
    } else {
        insertNode(&(*root)->right, value);
    }
    return *root;
}

C语言建立二叉树，并实现二叉树的遍历，先序遍历采用递归算法实现，层次遍历用非递归算法来实现。

以下是 C 语言实现建立二叉树和二叉树遍历的代码示例：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 建立二叉树
TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
    if (preorderSize == 0) {
        return NULL;
    }
    // 前序遍历的第一个节点是根节点
    int root_val = preorder[0];
    TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
    root->val = root_val;
    // 在中序遍历中找到根节点的位置
    int idx = 0;
    while (inorder[idx] != root_val) {
        idx++;
    }
    // 递归构建左右子树
    root->left = buildTree(preorder+1, idx, inorder, idx);
    root->right = buildTree(preorder+idx+1, preorderSize-idx-1, inorder+idx+1, inorderSize-idx-1);
    return root;
}

// 先序遍历（递归实现）
void preorderTraversal(TreeNode* root) {
    if (!root) {
        return;
    }
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

// 层次遍历（非递归实现）
void levelOrder(TreeNode* root) {
    if (!root) {
        return;
    }
    TreeNode* queue[1000];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        TreeNode* node = queue[front++];
        printf("%d ", node->val);
        if (node->left) {
            queue[rear++] = node->left;
        }
        if (node->right) {
            queue[rear++] = node->right;
        }
    }
}

// 测试代码
int main() {
    int preorder[] = {1, 2, 4, 5, 3, 6, 7};
    int inorder[] = {4, 2, 5, 1, 6, 3, 7};
    int n = sizeof(preorder) / sizeof(preorder[0]);
    TreeNode* root = buildTree(preorder, n, inorder, n);
    preorderTraversal(root);
    printf("\n");
    levelOrder(root);
    return 0;
}

以上代码中，`buildTree` 函数通过递归方式构建二叉树，`preorderTraversal` 函数通过递归方式实现先序遍历，`levelOrder` 函数通过队列实现二叉树的层次遍历。注意在 C 语言中，需要手动分配和释放内存空间。