各类排序方法在时间、空间复杂度及稳定性方面各有优势：

  

  二叉树排序（ tree sort）根据要排序的元素构建二叉搜索树，然后遍历树（按顺序），以便元素按排序的顺序输出。

  二叉树排序法借助了数据结构二叉排序树，用中序遍历（先读取左子树，再读取根结点，最后再读取右子树。）二叉树得到的结果就是排序的结果。

  二叉树排序法首先需要根据数据构建二叉排序树，然后中序遍历，排序时间复杂度为O(nlogn)，构建二叉树需要额外的O(n)的存储空间遍历二叉树java算法 排序算法7｜二叉树排序（比较、插入类）（附动图），有相同的元素是可以设置排在后边的放在右子树，在中序变量的时候也会在后边，所以二叉树排序是稳定的。

  1 二叉排序树性质

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

  1.2 若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。

  1.3 换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值遍历二叉树java算法，并小于其右子树中的每一个节点的键值。

  1.4 左右子树也是二叉搜索树。

  如下便是一颗二叉排序树：

  定义一个二叉排序树节点：

  

  <pre>typedef int DataType;
typedef struct BST_Node {
……DataType data;
……struct BST_Node lchild, rchild;
}BST_T, *BST_P;
</pre>

  2 二叉排序树插入

  插入新元素时，可以从根节点开始，遇键值较大者就向左，遇键值较小者就向右遍历二叉树java算法，一直到末端，就是插入点。

  

  动力演示如何插入一个节点：

  

  节点插入代码：

  3 二叉排序树查找

  要在二叉树中找出查找最大最小元素是极简单的事情，从根节点一直往左走，直到无路可走就可得到最小值；从根节点一直往右走，直到无路可走，就可以得到最大值。

  递归版和非递归版查找：

  4 二叉树排序的基本原理

  先构建一颗空树，使用第一个元素作为根节点，如果之后的元素比第一个小，则放到左子树，否则放到右子树，之后按中序遍历。

  时间复杂度：nlog2(n)

  空间复杂度：中序遍历时，需要构建栈，为logn

  5 二叉树排序代码

  5 附代码

  5.1 二叉排序树插入

  <pre>void Insert_BST( BST_P *root, DataType data )
{
/ 初始化插入节点 /

BST_P p = (BST_P) malloc( sizeof(struct BST_Node) );
if ( !p )
    return;
p->data = data;
p->lchild = p->rchild = NULL;

/ 空树时，直接作为根节点 /

if ( *root == NULL )
{
    *root = p;
    return;
}

/ 是否存在，已存在则返回，不插入 /

if ( Search_BST( root, data ) != NULL )
    return;

/ 进行插入，首先找到要插入的位置的父节点 /

BST_P tnode = NULL, troot = *root;
while ( troot )
{
    tnode = troot;
    troot = (data < troot->data) ? troot->lchild : troot->rchild;
}
if ( data < tnode->data )
    tnode->lchild = p;
else
    tnode->rchild = p;

}
void CreateBST( BST_P *T, int a[], int n )
{

int i;
for ( i = 0; i < n; i++ )
{
    Insert_BST( T, a[i] );
}

}
</pre>

  5.2 二叉排序树查找

  <pre>BST_P Search_BST( BST_P root, DataType key )
{

if ( root == NULL )
    return(NULL);
if ( key > root->data ) /* 查找右子树 */
    return(Search_BST( root->rchild, key ) );
else if ( key < root->data ) /* 查找左子树 */
    return(Search_BST( root->lchild, key ) );
else
    return(root);

}
非 递 归版查 找：
BST_P Search_BST( BST_P root, DataType key )
{

BST_P p = root;
while ( p )
{
    if ( p->data == key )
        return(p);
    p = (key < p->data) ? p->lchild : p->rchild;
}
return(NULL);

}
</pre>

  5.3 完整代码：

<p><pre>#include

include

include

define STACK_INCREMENT 10

define STACK_INIT_SIZE 100

define MAXSIZE 50

define OVERFLOW -2

//二叉排序树的链式存储结构
typedef struct BiTNode
{

int data;
struct BiTNode *lchild,*rchild;

}BiTNode,*BiTree;

//栈的顺序存储结构
typedef struct
{

BiTree *base;
BiTree *top;
int stacksize;

}Sqstack;

//初始化一个栈，用于二叉树的中序遍历
void InitStack(Sqstack&S)
{

S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));
if(!S.base)
    exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;

}

//二叉排序树查找
void SearchBST(BiTree T,int key,BiTree f,BiTree&p)
{

if(!T) 
    p=f;
else if(T->data==key)
    p=T;
else if(T->datarchild,key,T,p);
else 
    SearchBST(T->lchild,key,T,p);

}

//创建一个二叉排序树
void CreatBST(BiTree &T,int e)
{

BiTree p,s,q;
SearchBST(T,e,NULL,p);//找到带插入的位置。
s=(BiTree)malloc(sizeof(BiTNode));
s->data=e;
s->lchild=NULL;
s->rchild=NULL;
if(!p)T=s;
else if(e==p->data)

//当待排序列中有相同的元素时，将其放在相同元素的右孩子位置。
//原来的右子树放在其右节点域。

{
    q=p->rchild;
    p->rchild=s;
    s->rchild=q;
}
else if(edata)
    p->lchild=s;
else
    p->rchild=s;

}

//中序遍历二叉排序树
void InOrderTravese(BiTree T)
{

BiTree p;
Sqstack Sqt;
InitStack(Sqt);
p=T;
while(p||Sqt.base!=Sqt.top)
{
    if(p)
    {
        if(Sqt.top-Sqt.base>=Sqt.stacksize)
        {
            Sqt.base=(BiTree*)realloc(Sqt.base, \
    (Sqt.stacksize+STACK_INCREMENT)*sizeof(BiTNode));
            if(!Sqt.base)
                exit(OVERFLOW);
            Sqt.top=Sqt.base+Sqt.stacksize;
            Sqt.stacksize+=STACK_INCREMENT;
        }
        *Sqt.top++=p;
        p=p->lchild;
    }
    else
    {
        p=*--Sqt.top;
        printf("%d ",p->data);
        p=p->rchild;
    }
}
printf("\n");

}
void main()
{

int length;
int bst[MAXSIZE];
BiTree BST;

BST=(BiTree)malloc(sizeof(BiTNode));
BST=NULL;

printf("***************************\n");
printf(" 二叉树排序算法 \n");
printf("***************************\n");
printf("请输入待排序序列的个数N (N