数据结构——二叉查找树(C语言)

二叉查找树,也称作二叉搜索树,有序二叉树,排序二叉树,而当一棵空树或者具有下列性质的二叉树,就可以被定义为二叉查找树:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值。
  • 若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值。
  • 任意节点的左、右子树也分别为二叉查找树。
  • 没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在查找、插入的时间复杂度较低,为O(log n)。二叉查找树是基础性数据结构,用于构建更为抽象的数据结构,如集合、multiset、关联数组等。对于大量的输入数据,链表的线性访问时间太慢,不宜使用。

下面来看我们为二叉查找树定义的抽象行为:

#ifndef _Tree_H

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
typedef int ElementType;

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 Retrieve( Position P );

#endif

而对于上述抽象行为的实现,我们先来给出实现代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Tree.h"

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0

typedef int Status;

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

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 )
        return Find(X, T->Left);
    else
    if (X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

Position FindMin(SearchTree T)
{
    if ( T == NULL )
        return NULL;
    else
    if ( T-> Left == NULL )
        return T;
    else
        return FindMin( T->Left );
}

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)
    {

        /* Create and return a one-node tree */
        T = malloc(sizeof( struct TreeNode ));
        if ( T == NULL )
            printf("Out of space!!!\n");
        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);
    /* Else X is in the tree already; we'll do nothing */

    return T;
}

SearchTree Delete(ElementType X, SearchTree T)
{
    Position TmpCell;
    if (T == NULL)
        printf("Element not found\n");
    else if (X < T->Element) /* Go left */
        T->Right = Delete(X, T->Left);
    else if (X > T->Element) /* Go Right */
        T->Right = Delete(X, T->Left);
    else if (T->Left && T->Right) /* Two Children */
    {
        /* Replace with smallest in right subtree */
        TmpCell = FindMin(T->Right);
        T->Element = TmpCell->Element;
        T->Right = Delete(T->Element, T->Right);
    }
    else /* One or zero children */
    {
        TmpCell = T;
        if (T->Left == NULL) /* Also handles 0 children */
            T = T->Right;
        else if (T->Right == NULL)
            T = T->Left;
        free( TmpCell );
    }

    return T;
}

ElementType Retrieve(Position P)
{
    return P->Element;
}

/**
 * 前序遍历"二叉树"
 * @param T Tree
 */
void PreorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        printf("%d\n", T->Element);
        PreorderTravel(T->Left);
        PreorderTravel(T->Right);
    }
}

/**
 * 中序遍历"二叉树"
 * @param T Tree
 */
void InorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        InorderTravel(T->Left);
        printf("%d\n", T->Element);
        InorderTravel(T->Right);
    }
}

/**
 * 后序遍历二叉树
 * @param T Tree
 */
void PostorderTravel(SearchTree T)
{
    if (T != NULL)
    {
        PostorderTravel(T->Left);
        PostorderTravel(T->Right);
        printf("%d\n", T->Element);
    }
}

void PrintTree(SearchTree T, ElementType Element, int direction)
{
    if (T != NULL)
    {
        if (direction == 0)
            printf("%2d is root\n", T->Element);
        else
            printf("%2d is %2d's %6s child\n", T->Element, Element, direction == 1 ? "right" : "left");

        PrintTree(T->Left, T->Element, -1);
        PrintTree(T->Right, T->Element, 1);
    }
}

最后我们对我们的实现代码,在main函数中进行测试:

int main(int argc, char const *argv[])
{
    printf("Hello Leon\n");
    SearchTree T;
    MakeEmpty(T);

    T = Insert(21, T);
    T = Insert(2150, T);
    T = Insert(127, T);
    T = Insert(121, T);

    printf("树的详细信息: \n");
    PrintTree(T, T->Element, 0);

    printf("前序遍历二叉树: \n");
    PreorderTravel(T);

    printf("中序遍历二叉树: \n");
    InorderTravel(T);

    printf("后序遍历二叉树: \n");
    PostorderTravel(T);

    printf("最大值: %d\n", FindMax(T)->Element);
    printf("最小值: %d\n", FindMin(T)->Element);

    return 0;
}

编译运行这个C文件,控制台打印的信息如下:

Hello wsx
树的详细信息:
21 is root
2150 is 21's  right child
127 is 2150's   left child
121 is 127's   left child
前序遍历二叉树:
21
2150
127
121
中序遍历二叉树:
21
121
127
2150
后序遍历二叉树:
121
127
2150
21
最大值: 2150
最小值: 21

测试成功。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法修养

LeetCode 102. Binary Tree Level Order Traversal

15640
来自专栏数据结构笔记

数据结构(三):线性表

该序列中所含的元素个数叫做线性表的长度,用 n表示(n>=0)。当 n=0时,表示线性表是一个空表,即表中不包含任何数据元素。

19560
来自专栏算法channel

图解用栈数据结构对树的遍历

本公众号主要推送关于如何构思算法使之应用到我们的工作中。计算机常用算法思想大致来说有,分而治之,动态规划,贪心算法,搜索算法,回溯 ,训练这些思维的一个很好的平...

378110
来自专栏desperate633

LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For ex...

10020
来自专栏LeetCode

BST & AVL 二分搜索树 & 平衡二叉树的实现原理

本文完整的实现了基本的BST,由于注重的是逻辑和原理的实现,所以没有采用泛型。注意方法的访问修饰符。

27810
来自专栏郭耀华‘s Blog

LeetCode第六天

第六天 30.(219) Contains Duplicate II ? JAVA class Solution { public boolean co...

29370
来自专栏猿人谷

删除链表中的重复元素

昨晚在参加兰亭集势的笔试时,看到了这样一个题目。大致意思就是给出一个单链表,链表中有重复的元素,需要删除重复的元素。如:1→2→3→5→4→3→7,删除重复元素...

26380
来自专栏用户2442861的专栏

List、Set、Map、数组之间各种转换

刚学Java不久的时候,接到一个电面,然后问了一些java的知识,比如说Java的编码,Unicode等,但是最让我蛋疼的是怎么吗map转为set,那个时候对...

38020
来自专栏Android知识点总结

Java总结之容器家族--Collection

Set的操作比较少,基本上也就是Collection传下来的方法 Set一般基于Map来实现:HashSet、LinkedHashSet、TreeSet的特性...

17020
来自专栏曾大稳的博客

线性表(ArrayList 和 LinkedList源码分析)

线性表(linear list) 是数据结构的一种,一个线性表是n个具有相同特性的数据元素的有限序列。

15920

扫码关注云+社区

领取腾讯云代金券