如图：一棵二叉树
我们把这样的二叉树称为二叉查找树或二叉排序树（也叫BST树Binary Search Trees）
其特性如下:
- 每一个结点的值都不同，也就是整棵树中的每一个结点都拥有不同的值
- 每一个结点的数据大于左子树结点（如果有的话）的数据，但是小于右子树的结点（如果有的话）的数据。
- 左右两部分的子树，也是一课二叉查找树。
如果二叉树的结点数据已经按照上述规则进行排序，二叉树的查找就十分简单。例如：在上述二叉树内查找结点数据8，第一步与树根5比较，因为比5大，所以结点一定在二叉树的右子树。接着和右子树结点6比较，结果还是比6大，所以继续向右子树走，此时结点数是8，找到了。
如果我们采用遍历的方式，必须经过遍历左子树后才能找到，这样的运行效率差异就十分的明显，下面通过代码来看
/*********************************************************
- Copyright (C): 2016
- File name : serachtree.c
- Author : - Zhaoxinan -
- Date : 2016年08月02日 星期二 01时25分22秒
- Description : 该二叉是上图中的BST树。该程序有两种创建二叉树的方
- 式，两种查找二叉树的方式。
* *******************************************************/
#include <stdio.h>
#include <stdlib.h>
struct tree //树结构的声明
{
int data; //结点数据
struct tree *left; //指向左子树的指针
struct tree *right; //指向右子树的指针
};
typedef struct tree treenode; //树的结构新类型
typedef treenode *btree; //声明树结点指针类型
/*
递归创建二叉树
*/
btree createtree(int *data, int pos)
{
btree newnode;
//递归终止条件
if (data[pos] == || pos > )
{
return NULL;
}
else
{
//给新节点分配内存
newnode = (btree)malloc(sizeof(treenode));
//创建新节点内容
newnode->data = data[pos];
//创建左子树的递归调用
newnode->left = createtree(data, *pos);
//创建右子树的递归调用
newnode->right = createtree(data, *pos+);
return newnode;
}
}
/*
二叉查找树的查找
*/
btree btreefind(btree ptr, int value)
{
//主循环
while (ptr != NULL)
{
//找到了
if (ptr->data == value)
{
return ptr;
}
else
{
//比较数据
if (ptr->data > value)
{
ptr = ptr->left;
}
else
{
ptr = ptr->right;
}
}
}
return NULL;//没有找打
}
/*
二叉树的遍历查找
*/
btree btreesearch(btree ptr, int value)
{
btree ptrleft;
btree ptrright;
if (ptr != NULL)
{
//找到了
if (ptr->data == value)
{
return ptr;
}
else
{
//往左子树找
ptrleft = btreesearch(ptr->left, value);
ptrright = btreesearch(ptr->right, value);
if (ptrleft != NULL)
{
//在左子树
return ptrleft;
}
else
{
if (ptrright != NULL)
{
//在右子树
return ptrright;
}
else
{
//没有找到
return NULL;
}
}
}
}
else
{
return NULL;
}
}
/*
二叉树的插入
*/
btree insertnode(btree root, int value)
{
btree newnode; //树的新结点
btree temp = root; //代替树根的临时结点
btree back; //指向父节点的指针
//给新结点分配内存与赋值
newnode = (btree)malloc(sizeof(treenode));
newnode->data = value;
newnode->left = NULL;
newnode->right = NULL;
//如果当前没有根结点则直接返回新节点作为根结点
if (root == NULL)
{
return newnode;
}
else
{
while (temp != NULL)
{
//保留父结点指针
back = temp;
//比较结点值
if (temp->data > value)
{
//应该往左子树走
temp = temp->left;
}
else
{
//应该往右子树走
temp = temp->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 = ; i < len; i++)
{
root = insertnode(root, data[i]);
}
return root;
}
/*
二叉树的输出--先序遍历
*/
void preolder(btree ptr)
{
if (ptr)
{
printf("%2d", ptr->data);
preolder(ptr->left);
preolder(ptr->right);
}
}
/*
二叉树的输出--中序遍历
*/
void inolder(btree ptr)
{
if (ptr)
{
inolder(ptr->left);
printf("%2d", ptr->data);
inolder(ptr->right);
}
}
/*
二叉树的输出--后序遍历
*/
void postolder(btree ptr)
{
if (ptr)
{
postolder(ptr->left);
postolder(ptr->right);
printf("%2d", ptr->data);
}
}
int main()
{
int value = ;
btree root = NULL;
btree ptr = NULL;
//递归方式创建二叉树
//int data[16] = {0,5,4,6,2,0,0,8,1,3,0,0,0,0,7,9};
//root = createtree(data, 1);
//插入方式创建二叉树
int data[] = {, , , , , , , , };
root = createbtree(data, );
printf("\n---------先序遍历--------\n");
preolder(root);
printf("\n---------中序遍历--------\n");
inolder(root);
printf("\n---------后序遍历--------\n");
postolder(root);
printf("\n请输入要查找的数据(1-9):");
scanf("%d", &value);
//二叉查找树的查找
ptr = btreefind(root, value);
if (ptr != NULL)
{
printf("\n二叉查找树：节点数据是 %d\n", ptr->data);
}
else
{
printf("二叉查找树没有找到\n");
}
//二叉树的遍历查找
ptr = btreesearch(root, value);
if (ptr != NULL)
{
printf("\n遍历查找：节点数据是 %d\n", ptr->data);
}
else
{
printf("遍历查找没有找到\n");
}
return ;
}
