二叉搜索树数据结构基础：加法、删除、递归和非递归遍历

terry 2年前 (2023-09-27) 阅读数 69 #数据结构与算法

1 定义二叉搜索树

首先，我们定义二叉树的节点如下：

typedef struct BTNode {
    int value;
    struct BTNode *left;
    struct BTNode *right;
} BTNode;
复制代码

，其中有 value存储值，指针left和right分别指向左右子节点。二叉搜索树和二叉树可以使用相同的结构，但在插入或搜索时会有所不同。

2 基本操作

接下来我们看一下二叉树和二叉搜索树的一些基本操作，包括BST插入节点、BST搜索节点、BST最大值和最小值、二叉树节点的数量和高度等。二叉搜索树（BST）特有的操作通过在函数前添加前缀bst来区分，而其他函数与二叉树相同。

1) 创建节点

分配内存并初始化值。


/**
 * 创建BTNode
 */
BTNode *newNode(int value)
{
    BTNode *node = (BTNode *)malloc(sizeof(BTNode));
    node->value = value;
    node->left = node->right = NULL;
    return node;
}
复制代码

2) BST 插入节点

插入节点可以递归或非递归方式实现。如果插入的值大于根节点的值，则插入到右子树中，否则插入到左子树中。如下图所示（图片来自参考文献1、2、3）：

/**
 * BST中插入值，递归方法
 */
/**
 * BST中插入结点，递归方法
 */
BTNode *bstInsert(BTNode *root, int value)
{
    if (!root)
        return newNode(value);

    if (root->value > value) {
        root->left = bstInsert(root->left, value);
    } else {
        root->right = bstInsert(root->right, value);
    }
    return root;
}

/**
 * BST中插入结点，非递归方法
 */
BTNode *bstInsertIter(BTNode *root, int value)
{
    BTNode *node = newNode(value);

    if (!root)
        return node;

    BTNode *current = root, *parent = NULL;

    while (current) {
        parent = current;
        if (current->value > value)
            current = current->left;
        else
            current = current->right;
    }

    if (parent->value >= value)
        parent->left = node;
    else
        parent->right = node;

    return root;
}
复制代码

3）删除BST节点

删除节点有点复杂。需要考虑三种情况：

叶节点被删除。，操作方便，只需将该节点删除，并将叶子节点父节点的指针left或right置为空即可。

删除的节点有两个子节点，那么需要找到该节点的最大节点（使用后面的函数bstSearchIter）并将其值代入要删除的节点，然后递归调用删除功能删除最大的左子树节点。

如果删除的节点只有一个子节点，则移除该节点，并将其子节点的值添加到删除的节点中（需要指定是左子节点还是右子节点）。

/**
 * BST中删除结点
 */
BTNode *bstDelete(BTNode *root, int value)
{
    BTNode *parent = NULL, *current = root;
    BTNode *node = bstSearchIter(root, &parent, value);
    if (!node) {
        printf("Value not found\n");
        return root;
    }

    if (!node->left && !node->right) {
        // 情况1：待删除结点是叶子结点
        if (node != root) {
            if (parent->left == node) {
                parent->left = NULL;
            } else {
                parent->right = NULL;
            }
        } else {
            root = NULL;
        }
        free(node);
    } else if (node->left && node->right) {
        // 情况2：待删除结点有两个子结点
        BTNode *predecessor = bstMax(node->left);
        bstDelete(root, predecessor->value);
        node->value = predecessor->value;
    } else {
        // 情况3：待删除结点只有一个子结点
        BTNode *child = (node->left) ? node->left : node->right;
        if (node != root) {
            if (node == parent->left)
                parent->left = child;
            else
                parent->right = child;
        } else {
            root = child;
        }
        free(node);
    }
    return root;
}
复制代码

4) BST 搜索节点

请注意，非递归搜索中也会记录父节点。

/**
 * BST查找结点-递归
 */
BTNode *bstSearch(BTNode *root, int value)
{
    if (!root) return NULL; 

    if (root->value == value) {
        return root;
    } else if (root->value > value) {
        return bstSearch(root->left, value);
    } else {
        return bstSearch(root->left, value);
    }
}

/**
 * BST查找结点-非递归
 */
BTNode *bstSearchIter(BTNode *root, BTNode **parent, int value)
{
    if (!root) return NULL;

    BTNode *current = root;

    while (current && current->value != value) {
        *parent = current;
        if (current->value > value)
            current = current->left;
        else
            current = current->right;
    }

    return current;
}
复制代码

5）BST最小节点和最大节点

最小节点从左子树递归找到，最大节点从右子树递归找到。

/**
 * BST最小值结点
 */
BTNode *bstMin(BTNode *root)
{
    if (!root->left)
        return root;

    return bstMin(root->left);
}

/**
 * BST最大值结点
 */
BTNode *bstMax(BTNode *root)
{
    if (!root->right)
        return root;

    return bstMax(root->right);
}

复制代码

6) 二叉树节点的数量和高度

/**
 * 二叉树结点数目
 */
int size(BTNode *root)
{
    if (!root) return 0;
    
    return size(root->left) + size(root->right) + 1;
}

/**
 * 二叉树高度
 */
int height(BTNode *root)
{
    if (!root) return 0;

    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    int maxHeight = leftHeight > rightHeight ? leftHeight+1 : rightHeight+1;
    return maxHeight;
}
复制代码

3 二叉树遍历

递归遍历 - 前序、中序、后序、层序

树是二叉树的递归实现树比较简单，直接列出代码。这里值得注意的是，层序遍历首先计算二叉树的高度，然后调用辅助函数逐层遍历每一层的节点。这种方法比较容易理解，虽然会花费更多的时间。

/**
 * 二叉树先序遍历
 */
void preOrder(BTNode *root)
{
    if (!root) return;

    printf("%d ", root->value);
    preOrder(root->left);
    preOrder(root->right);
}

/**
 * 二叉树中序遍历
 */
void inOrder(BTNode *root)
{
    if (!root) return;

    inOrder(root->left);
    printf("%d ", root->value);
    inOrder(root->right);
}

/**
 * 二叉树后序遍历
 */
void postOrder(BTNode *root)
{
    if (!root) return;

    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->value);
}

/**
 * 二叉树层序遍历
 */
void levelOrder(BTNode *root)
{
    int btHeight = height(root);    
    int level;
    for (level = 1; level <= btHeight; level++) {
        levelOrderInLevel(root, level);
    }
}

/**
 * 二叉树层序遍历辅助函数-打印第level层的结点
 */
void levelOrderInLevel(BTNode *root, int level)
{
    if (!root) return;

    if (level == 1) {
        printf("%d ", root->value);
        return;
    }
    levelOrderInLevel(root->left, level-1);
    levelOrderInLevel(root->right, level-1);
}
复制代码

非递归遍历 - 前序、中序、后序、层序

前序遍历是非递归遍历中最简单的。使用栈来存储节点。先访问根节点然后添加右子节点和左子节点逐一压栈然后循环该过程。订单的进展有点复杂。它必须首先经过左子树，然后是根节点，最后是右子树。
后序遍历使用栈的方法postOrderIter()有点复杂，容易出错。所以面试时推荐使用两层版本的postOrderIterWith2Stack()，更容易理解，也更容易写。
层级顺序的遍历使用队列来帮助存储节点，相当简单。
这里我还实现了一个队列BTNodeQueue和一个堆栈BTNodeStack用于非递归bin树


/*********************/
/** 二叉树遍历-非递归 **/
/*********************/
/**
 * 先序遍历-非递归
 */
void preOrderIter(BTNode *root)
{
    if (!root) return;

    int btSize = size(root);
    BTNodeStack *stack = stackNew(btSize);

    push(stack, root);
    while (!IS_EMPTY(stack)) {
        BTNode *node = pop(stack);
        printf("%d ", node->value);

        if (node->right)
            push(stack, node->right);

        if (node->left)
            push(stack, node->left);
    }
    free(stack);
}

/**
 * 中序遍历-非递归
 */
void inOrderIter(BTNode *root)
{
    if (!root) return;

    BTNodeStack *stack = stackNew(size(root));

    BTNode *current = root;
    while (current || !IS_EMPTY(stack)) {
        if (current) {
            push(stack, current);
            current = current->left;
        } else {
            BTNode *node = pop(stack);
            printf("%d ", node->value);
            current = node->right;
        }
    }
    free(stack);
}

/**
 * 后续遍历-使用一个栈非递归
 */
void postOrderIter(BTNode *root)
{
    BTNodeStack *stack = stackNew(size(root));
    BTNode *current = root;
    do { 
        // 移动至最左边结点
        while (current) { 
            // 将该结点右孩子和自己入栈
            if (current->right) 
                push(stack, current->right); 
            push(stack, current); 
  
            // 往左子树遍历
            current = current->left; 
        } 
  
        current = pop(stack); 
  
        if (current->right && peek(stack) == current->right) { 
            pop(stack);
            push(stack, current);
            current = current->right;
        } else { 
            printf("%d ", current->value); 
            current = NULL; 
        } 
    } while (!IS_EMPTY(stack)); 
}

/**
 * 后续遍历-使用两个栈，更好理解一点。
 */
void postOrderIterWith2Stack(BTNode *root)
{
    if (!root) return;

    BTNodeStack *stack = stackNew(size(root));
    BTNodeStack *output = stackNew(size(root));

    push(stack, root);
    BTNode *node;

    while (!IS_EMPTY(stack)) {
        node = pop(stack);
        push(output, node);

        if (node->left)
            push(stack, node->left);

        if (node->right)
            push(stack, node->right);
    }

    while (!IS_EMPTY(output)) {
        node = pop(output);
        printf("%d ", node->value);
    }
}

/**
 * 层序遍历-非递归
 */
void levelOrderIter(BTNode *root)
{
    if (!root) return;

    BTNodeQueue *queue = queueNew(size(root));
    enqueue(queue, root);

    while (1) {
        int nodeCount = QUEUE_SIZE(queue);
        if (nodeCount == 0)
            break;

        while (nodeCount > 0) {
            BTNode *node = dequeue(queue);
            printf("%d ", node->value);

            if (node->left)
                enqueue(queue, node->left);

            if (node->right)
                enqueue(queue, node->right);

            nodeCount--;
        }
        printf("\n");
    }
}

作者：ssjhust
链接：https ://juejin.im /post/5ba3bb52e51d450e942f3031
来源：掘金
版权归作者所有，如需商业转载，请联系作者获得许可。非商业转载请注明来源。