二叉查找樹

引言：

使二叉樹成為二叉查找樹的性質是：對於樹中的每個節點X，它的左子樹中所有關鍵字值小於X的關鍵字值，而它的右子樹中所有關鍵字值大於X的關鍵字值。

二叉查找樹聲明

struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;

struct TreeNode{
ElementType Element;
SearchTree Left;
SearchTree Right;
};

建立一棵空樹的例程

SearchTree MakeEmpty(SearchTree T)
{
if(T != NULL){
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
}

return NULL;
}

二叉查找樹的Find操作

Position Find(ElementType X, SearchTree T)
{
if(T == NULL)
return NULL;
if(X < T->Element)
return Find(X, T->Left);
else if(X > T->Element)
return Find(X, T->Right);
return T;
}

二叉查找樹的FindMin遞歸與非遞歸實現

Position FindMin(SearchTree T)
{
if(T == NULL)
return NULL;
else if(T->Left == NULL)
return T;
else
return FindMin(T->Left);
}

Position FindMin(SearchTree T)
{
if(T != NULL)
while(T->Left != NULL)
T = T->Left;
return T;
}

二叉查找樹的FindMax遞歸與非遞歸實現

Position FindMax(SearchTree T)
{
if(T == NULL)
return NULL;
else if(T->Right == NULL)
return T;
else
return FindMax(T->Right);
}

Position FindMax(SearchTree T)
{
if(T != NULL)
while(T->Right != NULL)
T = T->Right;
return T;
}

插入元素到二叉查找樹的例程

SearchTree Insert(ElementType X, SearchTree T)
{
if(T == NULL){
T = (SearchTree)malloc(sizeof(struct TreeNode));
if(T == NULL){
printf("Out of space.\n");
return NULL;
}
}else if(X < T->Element){
T->Left = Insert(X, T->Left);
}else (X > T->Element){
T->Right = Insert(X, T->Right);
}

return T;
}

二叉查找樹的刪除例程

SearchTree Delete(ElementType X, SearchTree T)
{
Position TmpCell;

if(T == NULL){
fprintf(stderr,"Element not found.\n");
return NULL;
}else if(X < T->Element)
T->Left = Delete(X, T->Left);
else if(X > T->Element)
T->Right = Dlelte(X, T->Right);
else if(T->Left && T->Right){
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}else{
TmpCell = T;
if(T->Left == NULL)
T = T->Right;
else if(T->Right == NULL)
T = T->Left;
free(TmpCell);
}

return T;
}

二叉樹的常見問題及其解決程序 http://www.linuxidc.com/Linux/2013-04/83661.htm

【遞歸】二叉樹的先序建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75608.htm

在JAVA中實現的二叉樹結構 http://www.linuxidc.com/Linux/2008-12/17690.htm

【非遞歸】二叉樹的建立及遍歷 http://www.linuxidc.com/Linux/2012-12/75607.htm

二叉樹遞歸實現與二重指針 http://www.linuxidc.com/Linux/2013-07/87373.htm

二叉樹先序中序非遞歸算法 http://www.linuxidc.com/Linux/2014-06/102935.htm

輕松搞定面試中的二叉樹題目 http://www.linuxidc.com/linux/2014-07/104857.htm