当前位置 博文首页 > CrazyCatJack:《数据结构与算法分析》学习笔记-第四章-树
typedef struct TreeNode *PtrToNode;
struct TreeNode
{
ElementType Element;
PtrToNode FirstChild;
PtrToNode NextSibling;
}
static void
ListDir(DirectoryOrFile D, int Depth)
{
if (D is a legitimate entry)
{
PrintName(D, Depth);
if (D is a directory)
{
for each child, C, of D
ListDir(C, Depth+1);
}
}
}
void
ListDirectory(DirectoryOrFile D)
{
ListDir(D, 0);
}
static void
SizeDirectory (DirectoryOrFile D)
{
int TotalSize;
TotalSize = 0;
if (D is a legitimate entry)
{
TotalSize = FileSize(D);
if (D is a directory)
for each child, C, of D
TotalSize += SizeDirectory(C)
}
return TotalSize;
}
具有N个节点的每一棵二叉树,都将需要N+1个NULL指针
typedef struct TreeNode *PtrToNode;
typedef PtrToNode Tree;
struct TreeNode
{
ElementType Element;
Tree Left;
Tree Right;
}
表达式树的树叶是操作数,比如常量或变量,而其它节点为操作符。
构造一棵表达式树
void suffixExpression(char *inputStr)
{
int cnt, cnt2;
Stack s = CreateStack();
for (cnt = 0; inputStr[cnt] != '\0'; cnt++) {
if ((inputStr[cnt] >= '0') && (inputStr[cnt] <= '9')) {
PtrToTreeHead numTree = CreateTreeNode();
numTree->Element = inputStr[cnt];
printf("Push %c\n", numTree->Element);
Push(numTree, s);
}
for (cnt2 = 0; cnt2 < OPERATOR_TYPE; cnt2++) {
if (inputStr[cnt] == Operator[cnt2]) {
PtrToTreeHead operatorTree = CreateTreeNode();
operatorTree->Element = inputStr[cnt];
PtrToTreeHead num2Tree = Top(s);
Pop(s);
PtrToTreeHead num1Tree = Top(s);;
Pop(s);
operatorTree->LeftChild = num1Tree;
operatorTree->RightChild = num2Tree;
Push(operatorTree, s);
printf("operator=%c, num1=%c, num2=%c\n", operatorTree->Element, num1Tree->Element, num2Tree->Element);
}
}
}
PtrToTreeHead printTree = Top(s);
PrintTree(printTree);
DrstroyTree(printTree);
DistroyStack(s);
}
struct TreeNode;
typedef struct TreeNode *Position;
typedef Position SearchTree;
struct TreeNode {
ElementType Element;
Search Left;
Srarch Right
}
SearchTree
MakeEmpty(SearchTree treeHead)
{
if (treeHead == NULL) {
return NULL;
}
if (treeHead->Left != NULL) {
MakeEmpty(treeHead->Left);
}
if (treeHead->Right != NULL) {
MakeEmpty(treeHead->Right);
}
if (treeHead != NULL) {
free(treeHead);
}
}
SearchTree
Find(SearchTree treeHead, ElementType Element)
{
if (treeHead == NULL) {
return NULL;
}
if (Element < treeHead->Element) {
return Find(treeHead->Left, Element);
} else if (Element > treeHead->Element) {
return Find(treeHead->Right, Element);
} else {
return treeHead;
}
}
SearchTree
FindMin(SearchTree treeHead)
{
if (treeHead == NULL) {
return NULL;
}
if (treeHead->Left != NULL) {
return FindMin(treeHead->Left);
} else {
return treeHead;
}
}
SearchTree
FindMin(SearchTree treeHead)
{
if (treeHead == NULL) {
return NULL;
}
SearchTree tmp = treeHead;
while (tmp->Left != NULL) {
tmp = tmp->Left;
}
return tmp;
}
SearchTree
FindMax(SearchTree treeHead)
{
if (treeHead == NULL) {
return NULL;
}
if (treeHead->Right != NULL) {
return FindMin(treeHead->Right);
} else {
return treeHead;
}
}
SearchTree
FindMax(SearchTree treeHead)
{
if (treeHead == NULL) {
return NULL;
}
SearchTree tmp = treeHead;
while (tmp->Right != NULL) {
tmp = tmp->Right;
}
return tmp;
}
SearchTree
Insert(SearchTree treeHead, ElementType element)
{
if (treeHead == NULL) {
treeHead = (SearchTree)malloc(sizeof(struct TreeNode));
if (treeHead == NULL) {
return NULL;
}
memset(treeHead, 0, sizeof(struct TreeNode));
treeHead->Element = element;
treeHead->Left = treeHead->Right = NULL;
} else if (element < treeHead->Element) {
treeHead->Left = Insert(treeHead->Left, element);
} else if (element > treeHead->Element) {
treeHead->Right = Insert(treeHead->Right, element);
}
return treeHead;
}
SearchTree
Delete(SearchTree T, ElementType element)
{
SearchTree tmp;
if (T == NULL) {
printf("Couldn't find element\n");
return NULL;
} else if (element < T->element) {
T->Left = Delete(T->Left, element);
} else if (element > T->element) {
T->Right = Delete(T->Right, element);
} else if (T->Left && T->Right) {
tmp = T;
T->Element = tmp->Element;
T->Right = Delete(T->Right, element);
} else {
tmp = T;
if (T->Left) {
T = T->Left;
} else if (T->Right) {
T = T->Right;
}
free(tmp);
}
}
相当于两次单旋转。
struct AvlNode {
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
}
typedef struct AvlNode *Position;
typedef struct AvlNode *AvlTree;
static int
Height(Position P)
{
if (P == NULL) {
return -1;
} else {
return P->Height;
}
}
AvlTree
Insert(AvlTree T, ElementType X)
{
if (T == NULL) {
T = (struct AvlNode)malloc(sizeof(struct AvlNode));
if (T == NULL) {
return NULL;
}
memset(T, 0, sizeof(struct AvlNode));
T->Element = X;
T->Height = 0;
T->Left = T->Right = NULL;
} else if (X < T->Element) {
T->Left = Insert(T->Left, X);
if (Height(T->Left) - Height(T->Right) == 2) {
if (X < T->Left->Element) {
T = SingleRotateWithLeft(T);
} else {
T = DoubleRotateWithLeft(T);
}
}
} else if (X > T->Element) {
T->Right = Insert(T->Right, X);
if (Height(T->Right) - Height(T->Left) == 2) {
if (X > T->Right->Element) {
T = SingleRotateRight(T);
} else {
T = DoubleRotateRight(T);
}
}
}
T->Height = MAX(Height(T->Left), Height(T->Right)) + 1;
return T;
}
AvlTree
SingleRotateWithLeft(Position P)
{
Position P1 = NULL;
P1 = P->Left;
P->Left = P1->Right;
P1->Right = P;
P->Height = Max(Height(P->Left), Height(P->Right)) + 1;
P1->Height = Max(Height(P1->Left), Height(P1->Right)) + 1;
return P1;
}
AvlTree
SingleRotateWithRight(Position P)
{
Position P1 = NULL;
P1 = P->Right;
P->Right = P1->Left;
P1->Left = P;
P->Height = Max(Height(P->Left) + Height(P->Right)) + 1;
P1->Height = Max(Height(P1->Left) + Height(P1->Right)) + 1;
return P1;
}
AvlTree
DoubleRotateWithLeft(Position P)
{
P->Left = SingleRotateWithRight(P->Left);
return SingleRotateWithLeft(P);
}
AvlTree
DoubleRotateWithRight(Position P)
{
P->Right = SingleRotateWithLeft(P->Right);
return SingleRotateWithRight(P);
}
本文作者: CrazyCatJack
本文链接: https://www.cnblogs.com/CrazyCatJack/p/13339994.html
版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
关注博主:如果您觉得该文章对您有帮助,可以点击文章右下角推荐一下,您的支持将成为我最大的动力!