二叉查找树
树是一种由n个有限节点组成一个具有层次关系的集合
树叶:没有儿子的节点称为树叶
深度:对任意的节点ni，ni的深度为从根到ni唯一路径的长
高:ni的高是从ni到一片树叶的最长路径的长，因此，所有叶子的高为0，一颗树的高等于它的根的高
遍历方法
前序遍历：节点，左子树，右子树的遍历
后序遍历: 左子树，右子树，节点的遍历
中序遍历: 左，节点,右的遍历方式称为中序遍历
二叉树 : 二叉树是一棵树，其中每个节点都不能多于两个儿子
二叉查找树（Binary Search Tree） : 假设树中每一个节点指定一个关键字值 对于树中的每个节点X，它的左子树中所有的关键字的值小于X的关键值
而它的右子树中所有关键字的值大于X的关键字值
实现：
#ifndef _TREE_H
struct TreeNode;
typedef struct TreeNode * Position;
typedef struct TreeNode * SearchTree;
SearchTree MakeEmpty(SearchTree T);
Position Find(int X, SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(int X, SearchTree T);
SearchTree Delete(int X, SearchTree T);
#endif#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
struct TreeNode{
int E;
SearchTree Left, Right;
};
//前序遍历
void PrintTree(SearchTree T){
if(T == NULL){
return;
}
printf("%d ", T->E);
if(T->Left != NULL){
PrintTree(T->Left);
}
if(T->Right != NULL){
PrintTree(T->Right);
}
}
int main(int argc, char *argv[]){
int i, arr[5] = {2, 1, 4, 3, 8};
SearchTree Root, T;
Root = Insert(6, NULL);
T = Root;
for(i = 0; i < 5; i++){
T = Insert(arr[i], T);
}
PrintTree(Root);
Delete(2, Root);
printf("\n");
PrintTree(Root);
return 0;
}
//清空树
SearchTree MakeEmpty(SearchTree T){
if(T != NULL){
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}
return NULL;
}
//查找节点
SearchTree Find(int X, SearchTree T){
if(T == NULL){
return NULL;
}
if(X < T->E){
return Find(X, T->Left);
}else if(X > T->E){
return Find(X, T->Right);
}
return T;
}
//查找最小节点
Position FindMin(SearchTree T){
if(T == NULL){
return NULL;
}else if(T->Left == NULL){
return T;
}else{
return FindMin(T->Left);
}
}
//查找最大节点
Position FindMax(SearchTree T){
if(T == NULL){
return NULL;
}
while(T->Right != NULL){
T = T->Right;
}
return T;
}
//插入节点
SearchTree Insert(int X, SearchTree T){
if(T == NULL){
T = malloc(sizeof(struct TreeNode));
if(T == NULL){
printf("out of space");
exit(0);
}
T->E = X;
T->Left = NULL;
T->Right = NULL;
}else if(X < T->E){
T->Left = Insert(X, T->Left);
}else if(X > T->E){
T->Right = Insert(X, T->Right);
}
return T;
}
//删除节点
SearchTree Delete(int X, SearchTree T){
Position TmpCell;
if(T == NULL){
//printf("Element not found");
//return NULL;
}else if(X < T->E){
T->Left = Delete(X, T->Left);
}else if(X > T->E){
T->Right = Delete(X, T->Right);
}else if(T->Left && T->Right){//有2个儿子节点
TmpCell = FindMin(T->Right);
T->E = TmpCell->E;
T->Right = Delete(T->E, T->Right);
}else{//有一个儿子节点,没有儿子节点
TmpCell = T;
if(T->Left == NULL){
T = T->Right;
}else if(T->Right == NULL){
T = T->Left;
}
free(TmpCell);
}
return T;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-03-10 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读