# 数据结构——二叉查找树(C语言)

• 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值。
• 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值。
• 任意节点的左、右子树也分别为二叉查找树。
• 没有键值相等的节点。

```#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```

```#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)
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);
}
}```

```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;
}```

```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

121 篇文章32 人订阅

0 条评论

## 相关文章

15640

19560

378110

### LeetCode 144. Binary Tree Preorder Traversal题目分析代码

Given a binary tree, return the preorder traversal of its nodes' values. For ex...

10020

27810

29370

26380

38020