本文共 2339 字，大约阅读时间需要 7 分钟。

    在学习数据结构的时候，也曾经学习过二叉树，以及前序排列、中序排列、后序排列等等，但是一直无缘使用它！

二叉树可以干什么？

    排序有快速排序，归并排序，查找有二分法，甚至直接遍历查找，二叉树的使用很少。

    实际场景使用上，用的最多的是二叉平衡树，有种特殊的二叉平衡树就是红黑树，Java集合中的TreeSet和TreeMap,C++STL中的set,map以及LInux虚拟内存的管理，都是通过红黑树去实现的，还有哈弗曼树编码方面的应用，以及B-Tree,B+-Tree在文件系统中的应用。当然二叉查找树可以用来查找和排序。

二叉树的分类

    满二叉树：从高到低，除了叶节点外，所以节点左右节点都存在。

    完全二叉树：比满二叉树少几个叶节点，从左向右放子节点。

    平衡二叉树：空树或者它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树也都是平衡树。

    二叉搜索树：空树或者二叉树的所有节点比他的左子节点大，比他的右子节点小。

    红黑树：不仅是具有二叉搜索树的属性，还具有平衡树的属性，有序且子树差不超过1，颜色规则：根节点和特殊节点（即叶节点下面两个虚无的节点和未填写的节点）是黑的，红节点的左右子节点是黑的，最重要的是对于每个节点，从该节点到子孙叶节点的所有路径包含相同数目的黑节点。

    二叉树在搜索上的优势

    数组的搜索比较方便，可以直接使用下标，但删除或者插入就比较麻烦了，而链表与之相反，删除和插入都比较简单，但是查找很慢，这自然也与这两种数据结构的存储方式有关，数组是取一段相连的空间，而链表是每创建一个节点便取一个节点所需的空间，只是使用指针进行连接，空间上并不是连续的。而二叉树就既有链表的好处，又有数组的优点。

今天就学习一下最简单的二叉排序树

1.定义：

二叉排序树又叫二叉查找树或者二叉搜索树，它首先是一个二叉树，而且必须满足下面的条件：

1）若左子树不空，则左子树上所有结点的值均小于它的根节点的值；

2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值

3）左、右子树也分别为二叉排序树

2.二叉树的遍历：

在网上找到的一个遍历示意图：

图1 遍历示意图

前序遍历（根-左-右）：ABDGHECKFIJ

中序遍历（左-根-右）：GDHBEAKCIJF

后序便利（左-右-根）:GHDEBKJIFCA

结合定义可以知道，二叉搜索树的数据大小关系为：G<D<H<B<E<A<K<C<I<J<F，即中序遍历顺序。

小结：从创建好的二叉搜索树，我们可以直接使用中序遍历得到排序。

3.二叉树的代码实现：

    有了思路，代码实现的方式很多，以下就是很经典的一种实现，多多思考把握吧。

#include 
   
    using namespace std;/*BST的结点*/typedef struct node{    int key;    struct node *lChild, *rChild;}Node, *BST;/*在给定的BST中插入结点，其数据域为element, 使之称为新的BST*/bool BSTInsert(BST &p, int element){    if(NULL == p) // 空树    {        p = new Node;        p->key = element;        p->lChild = p->rChild = NULL;        return true;    }//    if(element == p->key) // BST中不能有相等的值,不注释掉会屏蔽掉相同的树//        return false;    if(element < p->key)  // 递归        return BSTInsert(p->lChild, element);    else        return BSTInsert(p->rChild, element);}/*先序遍历*/void preOrderTraverse(BST T){    if(T)    {        cout << T->key << " ";        preOrderTraverse(T->lChild);        preOrderTraverse(T->rChild);    }}/*中序遍历*/void inOrderTraverse(BST T){    if(T)    {        inOrderTraverse(T->lChild);        cout << T->key << " ";        inOrderTraverse(T->rChild);    }}/*后序遍历*/void postOrderTraverse(BST T){    if(T)    {        inOrderTraverse(T->lChild);        inOrderTraverse(T->rChild);        cout << T->key << " ";    }}int main(){    int a[13] = {4, 5, 2, 1, 0, 9, 3, 7, 6, 8,5,4,7};    int n = 13;    BST T;    T = NULL;    int i;    for(i = 0; i < n; i++)    {        BSTInsert(T, a[i]);    }    inOrderTraverse(T);    cout << endl;    return 0;}
   

转载地址：https://islet.blog.csdn.net/article/details/75647670 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！