二叉查找樹面哥，也稱作二叉搜索樹很魂，有序二叉樹，排序二叉樹咏瑟，而當(dāng)一棵空樹或者具有下列性質(zhì)的二叉樹贱纠，就可以被定義為二叉查找樹：
若任意節(jié)點的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值响蕴。
若任意節(jié)點的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值惠桃。
任意節(jié)點的左浦夷、右子樹也分別為二叉查找樹。
沒有鍵值相等的節(jié)點辜王。
二叉查找樹相比于其他數(shù)據(jù)結(jié)構(gòu)的優(yōu)勢在查找劈狐、插入的時間復(fù)雜度較低，為O(log n)呐馆。二叉查找樹是基礎(chǔ)性數(shù)據(jù)結(jié)構(gòu)肥缔，用于構(gòu)建更為抽象的數(shù)據(jù)結(jié)構(gòu),如集合、multiset汹来、關(guān)聯(lián)數(shù)組等续膳。對于大量的輸入數(shù)據(jù)，鏈表的線性訪問時間太慢收班，不宜使用坟岔。
下面來看我們?yōu)槎娌檎覙涠x的抽象行為：
#ifndef _Tree_H
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
typedef int ElementType;
SearchTree MakeEmpty( SearchTree T );
Position Find( ElementType X, SearchTree T );
Position FindMin( SearchTree T );
Position FindMax( SearchTree T );
SearchTree Insert( ElementType X, SearchTree T );
SearchTree Delete( ElementType X, SearchTree T );
ElementType Retrieve( Position P );
#endif
而對于上述抽象行為的實現(xiàn)，我們先來給出實現(xiàn)代碼:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "Tree.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
typedef int Status;
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;
}
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);
else
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 )
while(T->Right != NULL)
T = T->Right;
return T;
}
SearchTree Insert(ElementType X, SearchTree T)
{
if (T == NULL)
{
/* Create and return a one-node tree */
T = malloc(sizeof( struct TreeNode ));
if ( T == NULL )
printf("Out of space!!!\n");
else
{
T->Element = X;
T->Left = T->Right = NULL;
}
}
else if (X < T->Element)
T->Left = Insert(X, T->Left);
else if (X > T->Element)
T->Right = Insert(X, T->Right);
/* Else X is in the tree already; we'll do nothing */
return T;
}
SearchTree Delete(ElementType X, SearchTree T)
{
Position TmpCell;
if (T == NULL)
printf("Element not found\n");
else if (X < T->Element) /* Go left */
T->Right = Delete(X, T->Left);
else if (X > T->Element) /* Go Right */
T->Right = Delete(X, T->Left);
else if (T->Left && T->Right) /* Two Children */
{
/* Replace with smallest in right subtree */
TmpCell = FindMin(T->Right);
T->Element = TmpCell->Element;
T->Right = Delete(T->Element, T->Right);
}
else /* One or zero children */
{
TmpCell = T;
if (T->Left == NULL) /* Also handles 0 children */
T = T->Right;
else if (T->Right == NULL)
T = T->Left;
free( TmpCell );
}
return T;
}
ElementType Retrieve(Position P)
{
return P->Element;
}
/**
* 前序遍歷"二叉樹"
* @param T Tree
*/
void PreorderTravel(SearchTree T)
{
if (T != NULL)
{
printf("%d\n", T->Element);
PreorderTravel(T->Left);
PreorderTravel(T->Right);
}
}
/**
* 中序遍歷"二叉樹"
* @param T Tree
*/
void InorderTravel(SearchTree T)
{
if (T != NULL)
{
InorderTravel(T->Left);
printf("%d\n", T->Element);
InorderTravel(T->Right);
}
}
/**
* 后序遍歷二叉樹
* @param T Tree
*/
void PostorderTravel(SearchTree T)
{
if (T != NULL)
{
PostorderTravel(T->Left);
PostorderTravel(T->Right);
printf("%d\n", T->Element);
}
}
void PrintTree(SearchTree T, ElementType Element, int direction)
{
if (T != NULL)
{
if (direction == 0)
printf("%2d is root\n", T->Element);
else
printf("%2d is %2d's %6s child\n", T->Element, Element, direction == 1 ? "right" : "left");
PrintTree(T->Left, T->Element, -1);
PrintTree(T->Right, T->Element, 1);
}
}
最后我們對我們的實現(xiàn)代碼摔桦，在main函數(shù)中進行測試:
int main(int argc, char const *argv[])
{
printf("Hello Leon\n");
SearchTree T;
MakeEmpty(T);
T = Insert(21, T);
T = Insert(2150, T);
T = Insert(127, T);
T = Insert(121, T);
printf("樹的詳細信息: \n");
PrintTree(T, T->Element, 0);
printf("前序遍歷二叉樹: \n");
PreorderTravel(T);
printf("中序遍歷二叉樹: \n");
InorderTravel(T);
printf("后序遍歷二叉樹: \n");
PostorderTravel(T);
printf("最大值: %d\n", FindMax(T)->Element);
printf("最小值: %d\n", FindMin(T)->Element);
return 0;
}
編譯運行這個C文件社付，控制臺打印的信息如下:
Hello wsx
樹的詳細信息:
21 is root
2150 is 21's right child
127 is 2150's left child
121 is 127's left child
前序遍歷二叉樹:
21
2150
127
121
中序遍歷二叉樹:
21
121
127
2150
后序遍歷二叉樹:
121
127
2150
21
最大值: 2150
最小值: 21
測試成功。
