数据结构之树的学习

在树中，对于任意节点n，n的深度为从根节点到n的唯一路径的 长。因此，根 的深度为零。n 的高度是从n到一片树叶的最长路径的长。因此所有的树叶的高都是0一棵树的高等于他的根的高.
一颗树的深度等于他的最深的树叶的深度,该深度总是等于这棵树的高.


树节点的声明
typedef struct TreeNode *PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode FirstChild;
PtrToNode NextSibling;
};


二叉树节点声明
typedef struct TreeNode *PtrToNode;
tyedef struct PtrToNode Tree;
struct TreeNode
{
ElementType Element;
Tree Left;
Tree Right;
};
是二叉树成为二叉查找树的性质是:对于树中的每一个节点X,他的左子树的所有关键字值
小于X的关键字值.而他的右子树中所有关键字的值大于X的关键字值.
二叉查找树的声明
#ifndef _Tree-h
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *searchTree;


SearchTree MakeEmpty(searchTree T);
Position Find(ElementType X,SearchTree T);
Position FindMin(SearchTree T);
Positon FindMax(SearchTree T);
SearchTree Insert(ElementType X,SearchTree T);


SearchTree Delete(ElementType X,SerachTre T);


ElementType Retrieve(Position P);


#endif


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


建立一颗空的二叉树
SearchTree MakeEmpty(SeachTree 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);


else
return T;
}


对二叉查找树的FindMin的递归实现


Position FindMin(SearchTree T)
{
if(T==NULL)
return NULL;
else if(T->Left==NULL)
return T;
else
return FindMin(T->Left);
}
对而查找树的FindMax的非递归实现


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=malloc(sizeof(struct TreeNode))
if(T==NULL)
FatalError("Out of space");
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);
return T;
}


二叉查找树的删除
SearchTree Delete(ElementType X,Searchtree T)
{
Position TmpCell;
if(T==NULL)
Error("Element not find");
else if(X<T->Element)
T->Left=Delete(X,T->Left);
else if(X>T->Element)
T->Right=Delete(X,T->Left);
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;
}