二叉树查找

介绍

二叉树是树的一种特殊情况，规定一个根节点只能有两个孩子节点。如果再规定，左子数中的所有元素都要小于父亲节点的元素，右子树中所有的元素都要大于父亲节点的元素，这样的二叉树就是二叉查找树。找到一个元素的时间复杂度就是 O(logN)。

二叉树的定义是一个递归定义。

定义

我们定义它的数据结构。

/*
    二叉查找树的ADT实现
*/
#include<stdio.h>
#include<stdlib.h>
#define ElementType int
typedef struct TreeNode *Position;
typedef Position SearchTree;

SearchTree MakeEmpty( SearchTree T );
Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Ertrieve( Position P );

struct TreeNode {
    ElementType Element;
    SearchTree Left;
    SearchTree Right;
};

值得注意的是删除(Delete)函数的实现。

这里有三种情况，

叶子节点，直接删除即可
有一个子孩子，将父节点删除，并操作指针将子孩子接上即可
有两个子结点，这时，需要使用它右子树中最小的元素节点来替换将要删除的节点的值，并删除那个节点，这是一个递归的过程。

SearchTree
Delete(ElementType X, SearchTree T) {
    Position TmpCell;
    if (T == NULL) {
        fprintf(stderr, "Not Found.");
    }
    else if (X < T->Element) {
        T->Left = Delete(X, T->Left);
    }
    else if (X > T->Element) {
        T->Right = Delete(X, T->Right);
    }
    // Found element to be deleted
    // if have two children
    else if (T->Left && T->Right) {
        // 找到右子树中拥有最小元素的节点
        TmpCell = FindMin(T->Right);
        // 替换值
        T->Element = TmpCell->Element;
        // 删除那个在右子树中重复的节点
        T->Right = Delete(TmpCell->Element, T->Right);
    }
    // if zero or one child
    else {
        TmpCell = T;
        // also handles zero child
        if (T->Left != NULL) {
            T = T->Left;
        }
        else if (T->Right != NULL) {
            T = T->Right;
        }
        free(TmpCell);
    }
    return T;
}

下面给出所有函数的具体实现

SearchTree
MakeEmpty( SearchTree T ) {
    if (T != NULL) {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position
Find( ElementType X, SearchTree T ) {
    if (T == NULL) {
        return NULL;
    }
    if ( X > T->Element ) {
        Find( X, T->Right );
    } else
    if ( X < T->Element ) {
        Find( X, T->Left );
    }
    // 如果找到
    else {
        return T;
    }
}

Position
FindMin( SearchTree T ) {
    if (T == NULL) {
        return NULL;
    } else if (T->Left != NULL) {
        FindMin(T->Left);
    // 如果是叶子节点 则就是最小的节点
    } else {
        return T;
    }
}

Position
FindMax( SearchTree T ) {
    if (T != NULL) {
        while ( T->Right != NULL) {
            T = T->Right;
        }
    }
    return T;
}

// 返回新插入的节点的指针
SearchTree
Insert(ElementType X, SearchTree T) {
    if (T == NULL) {
        // malloc 语句仅仅是给T指针一个新的内存地址，它的作用域是整个函数体
        T = (Position)malloc(sizeof(struct TreeNode));
        if (T == NULL) {
            fprintf(stderr, "Out of space.");
        } else {
            T->Element = X;
            T->Left = T->Right = NULL;
        }
    } else if (X < T->Element) {
        T->Left = Insert(X, T->Left);
    } else if (X > T->Element) {
        T->Right = Insert(X, T->Right);
    }

    return T;
}

最后修改于 2021-07-12