二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：
若左子树不空，则左子树上所有节点的值均小于它的根节点的值
若右子树不空，则右字数上所有节点的值均大于它的根节点的值
它的左、右子树也分别为二叉排序数（递归定义）
从图中可以看出，二叉排序树组织数据时，用于查找是比较方便的，因为每次经过一次节点时，最多可以减少一半的可能，不过极端情况会出现所有节点都位于同一侧，直观上看就是一条直线，那么这种查询的效率就比较低了，因此需要对二叉树左右子树的高度进行平衡化处理，于是就有了平衡二叉树（Balenced Binary Tree）
所谓“平衡”，说的是这棵树的各个分支的高度是均匀的，它的左子树和右子树的高度之差绝对值小于1，这样就不会出现一条支路特别长的情况。于是，在这样的平衡树中进行查找时，总共比较节点的次数不超过树的高度，这就确保了查询的效率（时间复杂度为O(logn)）
static boolean IsSearchTree(Bitree *t){if(!t) //空二叉树情况
return true
else if(!(t.lchild)&&!(t.rchild)) //左右子树都无情况
return true
else if((t.lchild)&&!(t.rchild)){ //只有左子树情况
if(t.lchild.data>t.data)
return false
else
return IsSearchTree(t.lchild)
}
else if((t.rchild)&&!(t.lchild)){ //只有右子树的情况
if(t.rchild.data<t.data)
return false
else
return IsSearchTree(t.rchild)
}
else{ //左右子树都有的情况
if((t.lchild.data>t.data) || (t.rchild.data<t.data))
return false
else
return (IsSearchTree(t.lchild) && IsSearchTree(t.rchild))
}
}
二叉排序树具有如下性质:(1) 若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
(2) 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
(3) 左、右子树也分别为二叉排序树.
元素（19.14.22.01.66.21.83.27.56.13.10）构造二叉排序树的过程如下:
加入19, 这是根结点. 往后但凡数值比19小的都属于左子树, 比19大的都属于右子树.
加入14, 数值比19小, 作为19的左子树.
19
/
14
加入22, 数值比19大, 作为19的右子树.
19
/ \
14 22
加入01, 数值比19, 14都小, 作为14的左子树.
19
/ \
14 22
/
1
加入66, 数值比19, 22都大, 作为22的右子树.
19
/ \
14 22
/ \
1 66
加入21, 数值比19大, 比22小, 作为22的左子树.
19
/ \
14 22
/ / \
1 21 66
加入83, 数值比19, 22, 66都大, 作为66的右子树.
19
/ \
14 22
/ / \
1 21 66
\
83
加入27, 数值比19, 22都大, 但是比66小, 作为66的左子树.
19
/ \
14 22
/ / \
1 21 66
/ \
27 83
加入56, 数值比19, 22都大, 比66小, 但是比27大, 作为27的右子树.
19
/ \
14 22
/ / \
1 21 66
/ \
27 83
\
56
加入13, 数值比19, 14都小, 但是比1大, 作为1的右子树.
19
/ \
14 22
/ / \
1 21 66
\ / \
13 27 83
\
56
加入10, 数值比19, 14都小, 比1大, 但是比13小, 作为13的左子树.
19
/ \
14 22
/ / \
1 21 66
\ / \
13 27 83
/ \
10 56
因为二叉树排序的根结点是19, 27比19大, 所以27肯定排在根结点19的右子树,
而13比19小, 所以13肯定排在根结点19的左子树, 故此,13不会是27的左子树.
根据二叉排序树的性质, 13是1的右子树.
//C语言测试程序
#include "stdio.h"
#include "stdlib.h"
struct tree
{
int data
struct tree *left
struct tree *right
}
typedef struct tree treenode
typedef treenode *btree
btree insertnode(btree root,int value) //插入新结点
{
btree newnode
btree current
btree back
newnode=(btree)malloc(sizeof(treenode))
newnode->data=value
newnode->left=NULL
newnode->right=NULL
if(root==NULL)
{
return newnode
}
else
{
current=root
while(current!=NULL)
{
back=current
if(current->data > value)
current=current->left
else
current=current->right
}
if(back->data > value)
back->left=newnode
else
back->right=newnode
}
return root
}
btree createBtree(int *data,int len) //创建二叉排序树
{
btree root=NULL
int i
for(i=0i<leni++)
{
root=insertnode(root,data[i])
}
return root
}
void preOrder(btree ptr) //前序遍历
{
if(ptr!=NULL)
{
printf("%d ",ptr->data)
preOrder(ptr->left)
preOrder(ptr->right)
}
}
void inOrder(btree ptr) //中序遍历
{
if(ptr!=NULL)
{
inOrder(ptr->left)
printf("%d ",ptr->data)
inOrder(ptr->right)
}
}
void postOrder(btree ptr) //后序遍历
{
if(ptr!=NULL)
{
postOrder(ptr->left)
postOrder(ptr->right)
printf("%d ",ptr->data)
}
}
int main()
{
btree root=NULL
int data[]={19,14,22,01,66,21,83,27,56,13,10}
int n
int i
n=sizeof(data)/sizeof(data[0])
printf("原数组数据: ")
for(i=0i<ni++)
{
printf("%d ",data[i])
}
root=createBtree(data,n)
printf("\n前序遍历序列: ")
preOrder(root)
printf("\n中序遍历序列: ")
inOrder(root)
printf("\n后序遍历序列: ")
postOrder(root)
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）