背景

接上面五篇文章

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

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

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

二叉搜索树排序思想

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

二叉搜索树排序实现

二叉搜索树的插入

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

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
    
     Count; i++) {        printf("%d ", T->Element);    }    if(NULL != T->Right) Tree_LMR_Travel(T->Right);}
    

One More Thing