树和二叉树 -数据结构（C语言实现）

读数据结构与算法分析

树的概念

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

树的实现

思路

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

树的节点声明

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


树的遍历

先序遍历

以打印文件目录为例

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


后序遍历

以计算文件目录大小为例

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


二叉树

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

实现

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

节点声明和初始化

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操作

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操作

递归和非递归实现

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操作

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操作

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

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

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