二叉搜索树的常用操作

本文主要是介绍二叉搜索树的常用操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参考 ：http://blog.csdn.net/wanmeiwushang/article/details/51921821

#include <stdio.h>
#include <stdlib.h>typedef enum {false,true}bool;
typedef int ElementType;
typedef struct TNode* BinTree;
struct TNode{ElementType data;BinTree Left;BinTree Right;
};BinTree BuildTree();
bool IsBST(BinTree T);
int maxValue(BinTree T);
int minValue(BinTree T);
void PreOrderTraverse(BinTree T);
void InOrderTraverse(BinTree T);
void PostOrderTraverse(BinTree T);BinTree Insert(BinTree T, ElementType X);
BinTree Delete(BinTree T, ElementType X );
BinTree FindMin( BinTree T );
BinTree FindMax( BinTree T );BinTree Find( BinTree BST, ElementType X );int main(){BinTree T;T=BuildTree();if(IsBST(T))printf("YES!\n");elseprintf("NO!\n");printf("PreOrder: ");PreOrderTraverse(T);printf("\n");printf("InOrder: ");InOrderTraverse(T);printf("\n");printf("PostOrder: ");PostOrderTraverse(T);printf("\n");Delete(T, 3);Delete(T, 7);printf("PreOrder: ");PreOrderTraverse(T);printf("\n");T = Find(T, 5);printf("T->data = %d\n", T->data);return 0;
}
/* 4 3 1 -1 2 -1 -1 -1 5 -1 7 6 -1 -1 8 -1 -1 4 */  
//PreOrder:  4 3 1 2 5 7 6 8
//InOrder:   1 2 3 4 5 6 7 8
//PostOrder: 2 1 3 6 8 7 5 4BinTree BuildTree(){BinTree T=NULL;ElementType val;scanf("%d", &val);if(val==-1)return T;T = (BinTree)malloc(sizeof(struct TNode));T->data = val;T->Left = BuildTree();T->Right = BuildTree();return T;
}bool IsBST(BinTree T){if(T==NULL)return true;if(T->Left!=NULL&&maxValue(T->Left)>T->data)return false;if(T->Right!=NULL&&maxValue(T->Right)<=T->data)return false;return IsBST(T->Left)&&IsBST(T->Right);
}int maxValue(BinTree T){BinTree p;int max;max=T->data;p=T->Left;while(p){if(max<p->data)max=p->data;p=p->Left;}return max;
}int minValue(BinTree T){BinTree p;int min;min=T->data;p=T->Right;while(p){if(min>p->data)min=p->data;p=p->Right;}return min;
}void PreOrderTraverse(BinTree T){if(T==NULL)return;printf("%d ", T->data);PreOrderTraverse(T->Left);PreOrderTraverse(T->Right);
}
void InOrderTraverse(BinTree T){if(T==NULL)return;InOrderTraverse(T->Left);printf("%d ", T->data);InOrderTraverse(T->Right);
}
void PostOrderTraverse(BinTree T){if(T==NULL)return;PostOrderTraverse(T->Left);PostOrderTraverse(T->Right);printf("%d ", T->data);
}BinTree Insert(BinTree T, ElementType X){if(T==NULL){T = (BinTree)malloc(sizeof(struct TNode));T->data = X;T->Left = NULL;T->Right = NULL;}else{if(X<T->data)T->Left=Insert(T->Left, X);else if(X>T->data)T->Right=Insert(T->Right, X);}return T;
}
BinTree Delete(BinTree T, ElementType X ){BinTree tmp;if(NULL==T){printf("Not Found!\n");return T;}if(X<T->data)T->Left=Delete(T->Left, X);else if(X>T->data)T->Right=Delete(T->Right, X);else{if(T->Left&&T->Right){tmp = FindMin(T->Right);T->data=tmp->data;T->Right = Delete(T->Right, T->data);		}else{tmp = T;  if(T->Left==NULL)  T=T->Right;  else if(T->Right==NULL)  T=T->Left;free(tmp);  }}return T;
}
BinTree FindMin( BinTree T ){if(T){while(T->Left)T=T->Left;}return T;
}
BinTree FindMax( BinTree T ){if(T){while(T->Right)T=T->Right;}return T;
}BinTree Find( BinTree T, ElementType X ){if(NULL==T)return NULL;if(X<T->data)return Find(T->Left, X);else if(X>T->data)return Find(T->Right, X);elsereturn T;
}

这篇关于二叉搜索树的常用操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---