C语言链表实现二叉树

链表实现二叉树是一种常见的数据结构，可以用于存储和操作树形结构的数据。下面是C语言链表实现二叉树的方法：

定义结构体：

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

初始化：

TreeNode *root = NULL;

先序遍历创建二叉树方法一：

void createTree(TreeNode **node) {
    int data;
    scanf("%d", &data);
    if (data == -1) {
        *node = NULL;
    } else {
        *node = (TreeNode *)malloc(sizeof(TreeNode));
        (*node)->data = data;
        createTree(&((*node)->left));
        createTree(&((*node)->right)));
    }
}

测试：

int main() {
    createTree(&root);
    return 0;
}

方法二：根据所给的字符串序列创建

void createTree(TreeNode **node, char *str, int *index) {
    if (str[*index] == '\0' || str[*index] == '#') {
        *node = NULL;
        (*index)++;
    } else {
        *node = (TreeNode *)malloc(sizeof(TreeNode));
        (*node)->data = str[*index] - '0';
        (*index)++;
        createTree(&((*node)->left), str, index);
        createTree(&((*node)->right), str, index);
    }
}

其他方法：

- 树的结点大小

int size(TreeNode *node) {
    if (node == NULL) {
        return 0;
    } else {
        return size(node->left) + 1 + size(node->right);
    }
}

- 树的高

int height(TreeNode *node) {
    if (node == NULL) {
        return 0;
    } else {
        int leftHeight = height(node->left);
        int rightHeight = height(node->right);
        return (leftHeight > rightHeight) ? (leftHeight + 1) : (rightHeight + 1);
    }
}

- 判断树是否为空

int isEmpty(TreeNode *node) {
    return node == NULL;
}

- 找某个结点的左孩子和右孩子

TreeNode *leftChild(TreeNode *node) {
    if (node == NULL) {
        return NULL;
    } else {
        return node->left;
    }
}

TreeNode *rightChild(TreeNode *node) {
    if (node == NULL) {
        return NULL;
    } else {
        return node->right;
    }
}

- 找某个结点的父节点

TreeNode *parent(TreeNode *root, TreeNode *node) {
    if (root == NULL || root == node) {
        return NULL;
    } else if (root->left == node || root->right == node) {
        return root;
    } else {
        TreeNode *p = parent(root->left, node);
        if (p != NULL) {
            return p;
        } else {
            return parent(root->right, node);
        }
    }
}

- 查找元素

TreeNode *find(TreeNode *node, int data) {
    if (node == NULL) {
        return NULL;
    } else if (node->data == data) {
        return node;
    } else {
        TreeNode *p = find(node->left, data);
        if (p != NULL) {
            return p;
        } else {
            return find(node->right, data);
        }
    }
}

- 拷贝树

TreeNode *copy(TreeNode *node) {
    if (node == NULL) {
        return NULL;
    } else {
        TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
        newNode->data = node->data;
        newNode->left = copy(node->left);
        newNode->right = copy(node->right);
        return newNode;
    }
}

- 清空树

void clear(TreeNode **node) {
    if (*node != NULL) {
        clear(&((*node)->left));
        clear(&((*node)->right));
        free(*node);
        *node = NULL;
    }
}