c 语言之二叉树

2023-12-15 18:37:06

????????二叉树是一种常见的数据结构,它每个节点最多有两个子节点,通常称为左子节点和右子节点。下面是一个简单的二叉树结构和相关操作的示例:

????????首先,我们需要定义二叉树节点的结构。这通常包含一个数据元素以及两个指向左子节点和右子节点的指针。

#include <stdio.h>  
#include <stdlib.h>  
  
// 定义二叉树节点结构  
typedef struct Node {  
    int data;  
    struct Node* left;  
    struct Node* right;  
} Node;

接下来,我们可以编写一些基本的二叉树操作,如创建新节点、插入节点和遍历节点。

// 创建新节点  
Node* createNode(int data) {  
    Node* newNode = (Node*)malloc(sizeof(Node));  
    newNode->data = data;  
    newNode->left = NULL;  
    newNode->right = NULL;  
    return newNode;  
}  
  
// 插入节点(这里使用简单的插入方式,实际应用中可能需要更复杂的逻辑)  
Node* insertNode(Node* root, int data) {  
    if (root == NULL) {  
        root = createNode(data);  
    } else if (data <= root->data) {  
        root->left = insertNode(root->left, data);  
    } else {  
        root->right = insertNode(root->right, data);  
    }  
    return root;  
}

遍历二叉树有三种基本方法:前序遍历、中序遍历和后序遍历。以下是这些遍历方法的实现:

// 前序遍历  
void preOrderTraversal(Node* root) {  
    if (root == NULL) {  
        return;  
    }  
    printf("%d ", root->data); // 访问根节点  
    preOrderTraversal(root->left); // 遍历左子树  
    preOrderTraversal(root->right); // 遍历右子树  
}  
  
// 中序遍历  
void inOrderTraversal(Node* root) {  
    if (root == NULL) {  
        return;  
    }  
    inOrderTraversal(root->left); // 遍历左子树  
    printf("%d ", root->data); // 访问根节点  
    inOrderTraversal(root->right); // 遍历右子树  
}  
  
// 后序遍历  
void postOrderTraversal(Node* root) {  
    if (root == NULL) {  
        return;  
    }  
    postOrderTraversal(root->left); // 遍历左子树  
    postOrderTraversal(root->right); // 遍历右子树  
    printf("%d ", root->data); // 访问根节点  
}

最后,我们可以编写一个简单的main函数来测试这些功能:

int main() {  
    Node* root = NULL; // 初始化一个空的二叉树  
    root = insertNode(root, 5); // 插入节点,这里我们插入5个节点,值为1到5  
    insertNode(root, 3);  
    insertNode(root, 2);  
    insertNode(root, 4);  
    insertNode(root, 7);  
    printf("Pre-order traversal: "); // 前序遍历输出应为:5 3 2 4 7   
    preOrderTraversal(root);   
    printf("\nIn-order traversal: "); // 中序遍历输出应为:2 3 4 5 7   
    inOrderTraversal(root);   
    printf("\nPost-order traversal: "); // 后序遍历输出应为:2 4 3 7 5   
    postOrderTraversal(root);   
    return 0; // 结束程序,返回0表示成功执行。记得在实际应用中释放分配的内存!这里为了简单起见省略了内存释放。请务必注意!。  
}

文章来源:https://blog.csdn.net/A185822153/article/details/135022665
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。