当前位置：首页 > article >正文

面试整理 - 二叉排序树 c语言及java 例子

article 2024/9/20 22:27:35

什么是二叉排序树？

二叉排序树（binary search tree，bst）是一种特殊的二叉树，其中每个节点具有一个键值，并且满足一下两个要求：

对于任何节点x,其左子树上所有节点的关键字值小于x的关键字值。
对于任何节点x,其有子树上所有节点的关键字值大于x的关键字值。

由于以上这两个性质，因此二叉排序树也被称为有序二叉树。在执行查找，**，删除等操作时，二叉排序树都可以保持平衡，使得时间复杂度变为o(log n)级别，极大的提高了操作效率。

二叉排序树原理

二叉排序树中每个结点最多有两个子树，且左子树的所有关键字（节点值）小于当前结点的关键字，右子树的所有关键字大于当前结点的关键字。
左右子树也都是二叉排序树。
当某个结点被查找时，比较待查找关键字与当前结点的关键字大小，若相等，则说明查找成功；否则根据大小关系向左或向右子树递归查找，直到找到对应的结点或者确认结点不存在。
当一个新的结点时，从根结点开始将待结点与当前结点进行比较，根据大小关系向左或向右递归到叶子结点停止。然后把新结点**到该叶子结点的左或右子树上。
当删除一个结点时，按照查找的方式找到需要删除的结点，如果该结点没有子结点，则直接删除即可；如果只有左子树或右子树，则将左子树或右子树直接替换到该结点位置；如果既有左子树又有右子树，则找到该结点的前驱或后继（中序遍历时大于当前结点的最小节点或者小于当前结点的最大节点），然后用其值来替换需要删除的结点的值，并删除前驱或后继。

使用Java实现二叉树排序的示例代码：

// 节点类
class Node {
    int value;
    Node left, right;

    public Node(int item) {
        value = item;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    // 将给定节点的值插入到二叉树中
    private Node insertNode(Node root, int value) {
        if (root == null) {
            root = new Node(value);
            return root;
        }

        if (value < root.value) {
            root.left = insertNode(root.left, value);
        } else if (value > root.value) {
            root.right = insertNode(root.right, value);
        }

        return root;
    }

    // 中序遍历，将节点的值按升序返回。
    private void traverseInOrder(Node root, List<Integer> values) {
        if (root != null) {
            traverseInOrder(root.left, values);
            values.add(root.value);
            traverseInOrder(root.right, values);
        }
    }

    // 对外的排序方法，接收一个整数数组并返回升序排列后的结果。
    public List<Integer> sort(int[] arr) {
        for (int i : arr) {
            root = insertNode(root, i);
        }

        List<Integer> sortedList = new ArrayList<>();
        traverseInOrder(root, sortedList);

        return sortedList;
    }

    // 测试代码
    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        int[] arr = {5, 3, 7, 1, 9};

        List<Integer> sortedList = tree.sort(arr);
        System.out.println(sortedList); // Output: [1, 3, 5, 7, 9]
    }
}

该示例中，我们使用节点类Node表示二叉树中的每个节点。二叉树类BinaryTree包含插入节点、中序遍历和排序三个方法

C 语言实现二叉搜索树排序（Binary Search Tree Sorting）的示例代码：

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

// 定义二叉树节点结构体
struct Node {
    int data;           // 数据
    struct Node* left;  // 左子节点指针
    struct Node* right; // 右子节点指针
};

// 创建新节点
struct Node* newNode(int data) {
    struct Node* node = (struct Node*)malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 插入节点
struct Node* insert(struct Node* node, int data) {
    if(node == NULL)
        return newNode(data);
    if(data < node->data)
        node->left = insert(node->left, data);
    else if(data > node->data)
        node->right = insert(node->right, data);
    return node;
}

// 遍历节点并按序排列输出结果 
void inorderTraversal(struct Node* node) {
    if(node != NULL) {
        inorderTraversal(node->left);
        printf("%d ", node->data);
        inorderTraversal(node->right);
    }
}

// 测试示例
int main() {
    int arr[] = {7, 5, 1, 8, 3, 6, 0, 9, 4, 2};
    int n = sizeof(arr)/sizeof(arr[0]);
    struct Node* root = NULL;

    for(int i=0; i<n; i++)
        root = insert(root, arr[i]);

    inorderTraversal(root);

    return 0;
}