王维烨

摘要：本文主要介绍了数据结构中的各种树状结构，重点介绍了二叉搜索树，其他还包括平衡二叉树，红黑树，霍夫曼树以及堆。此外，本文详细解释了二叉搜索树的操作的时间复杂度。同时，我们将介绍各种树形结构在生活中的应用。

关键词：算法；树状结构；应用

中图分类号：TP312 文献标识码：A 文章编号：1007-9416（2017）05-0147-02

在计算机世界中，有各种各样的抽象数据结构，包括数组，队列，堆栈，链表等。这些数据结构都可以转换到现实生活中的各种问题中去，以此能够高效的解决一些问题。在这些数据结构中，被使用的较为广泛的无疑是树状结构。本文就将详细介绍一下树状结构。

所谓树状结构，就是将信息存贮在节点之中，节点与节点之间用边链接起来的结构。一颗二叉树由结点的有限集合组成。这个集合可以由一个根节点和两个不相交的二叉树组成，这两颗二叉树分别成为这个根节点的左子树和右子树。关于树状结构其他种类更多的结构介绍，我们将在下文中一一阐述。

树状结构在现实生活中的使用也相当广泛。从计算机网络到数据库实现，树状结构无时无刻的在提高我们的工作效率。本文也会介绍其在生活中的应用，以引发读者对计算机科学的兴趣。

1 二叉检索树

我们首先介绍一下树状结构中最为简单也是最为常见的一种树：二叉检索树（Binary Search Tree）。

1.1 定义

首先我们介绍一下二叉检索树，明确一下它的定义。

所谓二叉检索树，就是满足一下条件的一棵二叉树：任意一个结点，设其值为K，则该节点的左子树中任意一个結点的值都小于K；……