这里要说的是一种特殊的二叉树，叫对分查找树。特点在于：左子树的所有值都比根节点小，右子树的所有值都比根节点大。
对分查找树的三种遍历：
中序遍历(inOrder) 遍历左子树；处理节点中的值；遍历右子树。
前序遍历(preOrder) 处理节点中的值；遍历左子树；遍历右子树。
后序遍历(postOrder) 遍历左子树；遍历右子树；处理节点中的值。
注意的是，对分查找树中序遍历的结果是对数列进行升序排列。因此中序遍历又叫二叉树排序。
下面的程序说明对分查找树的生成和三种遍历的实现。
/*author：zhanglin*/
#include
#include
#include .h>.h>.h>
struct treeNode{
struct treeNode *leftPtr;
int data;
struct treeNode *rightPtr;
};
typedef struct treeNode TreeNode;
typedef TreeNode *TreeNodePtr;
void insertNode(TreeNodePtr *, int);
void inOrder(TreeNodePtr);
void preOrder(TreeNodePtr);
void postOrder(TreeNodePtr);
int main(){
int i, item;
TreeNodePtr rootPtr= NULL;
srand(time(NULL));
/*insert random values between 1 and 15 in the tree*/
printf("the number being placed in the tree are:\n");
for(i=0; i<10;i++){
item = rand()%15;
printf("%3d", item);
insertNode(&rootPtr, item);
}
/*traverse the tree in inOrder*/
printf("\ntraverse the tree in inOrder\n");
inOrder(rootPtr);
/*traverse the tree in preOrder*/
printf("\ntraverse the tree in preOrder\n");
preOrder(rootPtr);
/*traverse the tree in postOrder*/
printf("\ntraverse the tree in postOrder\n");
postOrder(rootPtr);
return 0;
}
void insertNode(TreeNodePtr *ptr, int value){
if(*ptr==NULL){
*ptr = (TreeNodePtr)malloc(sizeof(TreeNode));
if(*ptr!=NULL){
(*ptr)->data = value;
(*ptr)->leftPtr = NULL;
(*ptr)->rightPtr = NULL;
}else{
printf("\nerror. No memory available\n");
}
}else{
if(value<(*ptr)->data){
insertNode(&((*ptr)->leftPtr), value);
}else if(value>(*ptr)->data){
insertNode(&((*ptr)->rightPtr), value);
}else{
printf("\nduplicate data\n");
}
}
}
void inOrder(TreeNodePtr ptr){
if(ptr!=NULL){
inOrder(ptr->leftPtr);
printf("%3d", ptr->data);
inOrder(ptr->rightPtr);
}
}
void preOrder(TreeNodePtr ptr){
if(ptr!=NULL){
printf("%3d", ptr->data);
preOrder(ptr->leftPtr);
preOrder(ptr->rightPtr);
}
}
void postOrder(TreeNodePtr ptr){
if(ptr!=NULL){
postOrder(ptr->leftPtr);
postOrder(ptr->rightPtr);
printf("%3d", ptr->data);
}
}
