树和二叉树

树的概念

  • 一棵树是一些节点的集合,可以为空
  • 由称做根(root)的节点以及0个或多个非空子树组成,子树都被一条来自根的有向边相连

树的实现

思路

孩子兄弟表示法:树中的每个节点中除了数据为还有两个指针,一个指向其儿子,一个指向其兄弟。

树的节点声明

1
2
3
4
5
6
7
8
typedef struct TreeNode *PrtToNode ;

struct TreeNode
{
ElementType Element ;
PrtToNode FirstChild ;
PrtToNode NextSibling ;
}

树的遍历

先序遍历

以打印文件目录为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void ListDir(DirectoryOrFile D,int Depth) //传进第一个目录和深度(第几级)
{
if( D 是一个合法的文件目录)
{
PrintName(D,Depth) ;//先序遍历,即先访问它的名字打印出来
for(遍历 D 所有的孩子 C)
ListDir(C,Depth + 1) ; //递归调用,遍历子树
}
}

void ListDirectory(DirectoryOrFile D) //启动程序
{
ListDir(D,0) ;
}

后序遍历

以计算文件目录大小为例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SizeDirectory(DirectoryOrFile D)
{
int TotalSize ;

TotalSize = 0 ;
if(D 是一个合法的文件目录)
{
TotalSize = FileSize(D) ;
for(D 的每个孩子 C)
TotalSize += SizeDirectory(C) ;
}

return TotalSize ;
}

二叉树

是一颗每个节点都不能由多于两个儿子的树

实现

二叉查找树:左子树关键字小于父节点,右子树关键字大于父节点

节点声明和初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
struct TreeNode ;
typedef struct TreeNode *Poisition ;
typedef struct TreeNode *SearchTree ;

SearchTree MakeEmpty(SearchTree T) ;
Position Find(ElementType X, SearchTree T) ;
Position FindMin(SearchTree T) ;
Position FinMax(SearchTree T) ;
SearchTree Insert(ElementType X, SearchTree T) ;
SearchTree Delete(ElementType X, SearchTree T) ;
ElementType Retrieve(Poisition P) ;

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

Find操作

1
2
3
4
5
6
7
8
9
10
11
Position Find(ElementType X, SearchTree T)
{
if(T == NULL)
return NULL ;
else if(X < T->Elements)
return Find(X,T->Left) ;
else if(X > T->Elements)
return Find(X,T->Right) ;

return T ;
}

FindMin和FindMax操作

递归和非递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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;
}

Insert操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
SearchTree Inesert(ElementType X, SearchTree T)
{
if(T == NULL)
{
T = malloc(sizeof(struct
TreeNode)) ;
if(T == NULL)
FatalError("内存不足") ;
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) ;

return T ;
}

Delete操作

只有一个节点的情况,直接用子树顶替

由两个节点的情况,找到右子树最小的元素顶替它,并删除这颗树(这颗树肯定只有一个节点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
SearchTree Delete(Element X, SearchTree T)
{
Position TmpCell ;
if(T == NULL)
Error("未找到") ;
else if(X < T->Element)
T->left = Delete(X,T-Left) ;
else if(X > T->Element)
T->Right = Delete(X,T->Right) ;
else if(T->Left && T->Right)
{
TmpCell = FindMin(T->Right) ;
T->Element = TmpCell->Element ;
T->Right = Delete(TmpCell->Element,T->Right) ;
}
else
{
TmpCell = T ;
if(T->Left == NULL)
T = T->Right ;
if(T->Right == NULL)
T = T ->Left ;
free(TmpCell) ;
}

return T ;
}