算法踩坑6-二叉搜索树排序

背景

接上面五篇文章
算法踩坑-快速排序
算法踩坑2-插入排序
算法踩坑3-堆排序
算法踩坑4-冒泡排序
算法踩坑5-归并排序

来继续聊聊最近我写的一些算法的小例程，这次要聊的是使用二叉搜索树实现的排序，是一个时间复杂度O(N)的算法。

主要从以下几方面来说的：

• 二叉搜索树排序思想
• 二叉搜索树排序实现

二叉搜索树排序思想

二叉搜索树的排序能够达到时间复杂度O(N)的前提是序列的数据结构需要是二叉搜索树，二叉搜索树的结构是每个非叶子节点最多有2个孩子节点，并且对于任一个节点，左孩子节点的关键字小于父父节点的关键字，右孩子节点的关键字大于父节点的关键字，因此使用中序遍历的方式（左子树->父节点->右子树）可以得到一个从小到大的有序序列。
因为只要遍历一遍二叉搜索树就能得到排序的序列，所有时间复杂度为O(N)。

二叉搜索树排序实现

二叉搜索树的插入

二叉搜索树核心的地方就在于节点的插入，使用递归的方式插入新的节点，需要注意的地方在于新的节点的插入需要返回改节点的指针，然后把某个节点的左孩子指针或者是右孩子的指针指向新创建的节点。
Tree_Insert

SearchTree Tree_Insert(ElementType Element, SearchTree T) {
    if (NULL == T) {
        T = malloc(sizeof(struct TreeNode));
        T->Element = Element;
        T->Count = 1;
        // 左右子树置为空
        T->Left = T->Right = NULL;
    } else if (Element < T->Element) {
        T->Left = Tree_Insert(Element, T->Left);
    } else if (Element > T->Element) {
        T->Right = Tree_Insert(Element, T->Right);
    } else {
        T->Count ++;
    }
    // 返回最终插入的位置
    return T;
}

二叉搜索树的中序遍历

二叉搜索树的节点中保存Count信息用于处理重复数据的个数信息，这种做法用于节点的关键字的数据是简单的数据类型，而不是某个复杂数据类型的其中某个关键字，如果用于排序的关键字是某个复杂数据类型的某个关键字，需要使用额外的空间来保存源数据的数据信息。

// Left->Middle->Right 中序遍历
void Tree_LMR_Travel(SearchTree T) {
    if (NULL == T) {
        return;
    }
    if(NULL != T->Left) Tree_LMR_Travel(T->Left);
    int i;
    for (i= 0; i<T->Count; i++) {
        printf("%d ", T->Element);
    }
    if(NULL != T->Right) Tree_LMR_Travel(T->Right);
}

One More Thing

噢！我是算法，点我