看了《数据结构与算法分析》的第4章，讲树的内容，感觉写的不错。记录一下^_^
1 查找树ADT-二叉查找树
假设树中的每个节点被指定一个关键字值，在我们的例子中，虽然任意复杂的关键字都是允许的，为了简单起见，假设他们都是整型。对于树中的每个节点，它的做左子树所
有关键字小于X的关键字，而它的右子树中所有关键字值大于X的关键字值。
//关于二叉查找树的定义
~~~
#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
typedef struct TREENODE 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);
int Travel(SearchTree T);
int Height(SearchTree T);
struct TREENODE
{
ElementType data;
SearchTree left;
SearchTree right;
};
#endif // TREE_H_INCLUDED
~~~
//关于二叉查找树的功能函数定义
~~~
#include "tree.h"
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;
else if(x < T->data)
return Find(x, T->left);
else if(x > T->data)
return Find(x, T->right);
else
return T;
}
Position FindMin(SearchTree T)
{
if(T != NULL)
while(T->left != NULL)
T = T->left;
return T;
}
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 = (Position)malloc(sizeof(TreeNode));
if(T == NULL)
exit(-1);
T->data = x;
T->left = T->right = NULL;
}
else if(x < T->data)
T->left = Insert(x, T->left);
else if(x > T->data)
T->right = Insert(x, T->right);
return T;
}
SearchTree Delete(ElementType x, SearchTree T)
{
Position tmpnode;
if(T == NULL)
{
printf("the tree have not any treenode\n");
exit(-1);
}
else if(x < T->data)
T->left = Delete(x, T->left);
else if(x > T->data)
T->right = Delete(x, T->right);
else if(T->left && T->right)
{
tmpnode = FindMin(T->right);
T->data = tmpnode->data;
T->right = Delete(T->data, T->right);
}
else
{
tmpnode = T;
if(T->left == NULL)
T = T->right;
else if(T->right == NULL)
T = T->left;
free(tmpnode);
}
return T;
}
ElementType Retrieve(Position P)
{
return P->data;
}
int Travel(SearchTree T)
{
if(T != NULL)
{
Travel(T->left);
printf("%d ", T->data);
Travel(T->right);
}
return 1;
}
int Max(int a, int b)
{
return (a >= b ? a : b);
}
int Height(SearchTree T)
{
if(T == NULL)
return 0;
else
return 1 + Max(Height(T->left), Height(T->right));
}
~~~
//二叉查找树测试的主函数
~~~
#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
int main()
{
SearchTree root = NULL;
root = Insert(2, root);
Insert(1, root);
Insert(3, root);
Insert(4, root);
Travel(root);
printf("min = %d, max = %d\n", FindMin(root)->data, FindMax(root)->data);
printf("the tree height %d\n", Height(root));
Delete(4, root);
Travel(root);
printf("min = %d, max = %d\n", FindMin(root)->data, FindMax(root)->data);
printf("the tree height %d\n", Height(root));
if(MakeEmpty(root) == NULL)
printf("Free the tree is ok\n");
return 0;
}
~~~
2 AVL树
一颗AVl树是其每个节点的左子树和右子树的高度最多差1的二叉查找树。（空树的高度定义为0）
单旋转>>
双旋转>>
//关于AVL树的定义
~~~
#ifndef AVLTREE_H_INCLUDED
#define AVLTREE_H_INCLUDED
#include <stdio.h>
#include <stdlib.h>
typedef struct AVLNODE AvlNode;
typedef struct AVLNODE *Position;
typedef struct AVLNODE *AvlTree;
typedef int ElementType;
int Height(Position P);
AvlTree MakeEmpty(AvlTree T);
Position Find(ElementType x, AvlTree T);
Position FindMin(AvlTree T);
Position FindMax(AvlTree T);
AvlTree Insert(ElementType x, AvlTree T);
AvlTree Delete(ElementType x, AvlTree T);
ElementType Retrieve(Position P);
struct AVLNODE
{
ElementType data;
AvlTree left;
AvlTree right;
int Height;
};
#endif // AVLTREE_H_INCLUDED
~~~
//关于AVL树的功能函数定义
~~~
#include "avltree.h"
int Height(Position P)
{
if(P == NULL)
return 0;
else
return P->Height;
}
AvlTree MakeEmpty(AvlTree T)
{
if(T != NULL)
{
MakeEmpty(T->left);
MakeEmpty(T->right);
free(T);
}
return NULL;
}
Position Find(ElementType x, AvlTree T)
{
if(T == NULL)
return NULL;
else if(x < T->data)
return Find(x, T->left);
else if(x > T->data)
return Find(x, T->right);
else
return T;
}
Position FindMin(AvlTree T)
{
if(T != NULL)
while(T->left != NULL)
T = T->left;
return T;
}
Position FindMax(AvlTree T)
{
if(T != NULL)
while(T->right != NULL)
T = T->right;
return T;
}
//----------------- Insert() ------------------
static int _max(int a, int b)
{
//return (a >= b ? a : b);
if(a > b)
return a;
else
return b;
}
static Position SingleRotateWithLeft(Position k2)
{
Position k1;
k1 = k2->left;
k2->left = k1->right;
k1->right = k2;
k2->Height = 1 + _max(Height(k2->left), Height(k2->right));
k1->Height = 1 + _max(Height(k1->left), k2->Height);
return k1;
}
static Position SingleRotateWithRight(Position k1)
{
Position k2;
k2 = k1->right;
k1->right = k2->left;
k2->left = k1;
k1->Height = _max(Height(k1->left), Height(k1->right)) + 1;
k2->Height = _max(k1->Height, Height(k2->right)) + 1;
return k2;
}
static Position DoubleRotateWithLeft(Position k3)
{
k3->left = SingleRotateWithRight(k3->left);
return SingleRotateWithLeft(k3);
}
static Position DoubleRotateWithRight(Position k1)
{
k1->right = SingleRotateWithLeft(k1->right);
return SingleRotateWithRight(k1);
}
AvlTree Insert(ElementType x, AvlTree T)
{
if(T == NULL)
{
T = (Position)malloc(sizeof(AvlNode));
if(T == NULL)
exit(-1);
T->data = x;
T->Height = 0;
T->left = T->right = NULL;
}
else if(x < T->data)
{
T->left = Insert(x, T->left);
if(Height(T->left) - Height(T->right) == 2)
{
if(x < T->left->data)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
}
else if(x > T->data)
{
T->right = Insert(x, T->right);
if(Height(T->right) - Height(T->left) == 2)
{
if(x > T->right->data)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
}
T->Height = _max(Height(T->left), Height(T->right)) + 1;
return T;
}
~~~
//AVL树测试的主函数
~~~
#include <stdio.h>
#include <stdlib.h>
#include "avltree.h"
int Trave(AvlTree T)
{
if(T != NULL)
{
Trave(T->left);
printf("%d ", T->data);
Trave(T->right);
}
return 1;
}
int Trave0(AvlTree T)
{
if(T != NULL)
{
printf("%d ", T->data);
Trave0(T->left);
Trave0(T->right);
}
return 1;
}
void root(AvlTree avltree)
{
printf("\n <root = %d> \n", avltree->data);
printf(" <root->left = %d root->right = %d>\n", avltree->left->data, avltree->right->data);
}
int main()
{
AvlTree avltree = NULL;
avltree = Insert(10, avltree);
avltree = Insert(12, avltree);
avltree = Insert(14, avltree);
root(avltree);
printf("The avltree height is %d\n", avltree->Height);
Trave0(avltree);
printf("\n");
Trave(avltree);
printf("\n");
avltree = Insert(16, avltree);
root(avltree);
printf("The avltree height is %d\n", avltree->Height);
Trave0(avltree);
printf("\n");
Trave(avltree);
printf("\n");
avltree = Insert(8, avltree);
root(avltree);
printf("The avltree height is %d\n", avltree->Height);
Trave0(avltree);
printf("\n");
Trave(avltree);
printf("\n");
avltree = Insert(4, avltree);
root(avltree);
printf("The avltree height is %d\n", avltree->Height);
Trave0(avltree);
printf("\n");
Trave(avltree);
printf("\n");
avltree = Insert(6, avltree);
root(avltree);
printf("The avltree height is %d\n", avltree->Height);
Trave0(avltree);
printf("\n");
Trave(avltree);
printf("\n");
avltree = Insert(7, avltree);
root(avltree);
printf("The avltree height is %d\n", avltree->Height);
Trave0(avltree);
printf("\n");
Trave(avltree);
printf("\n");
if(MakeEmpty(avltree) == NULL)
printf("Free the avltree is ok\n");
return 0;
}
~~~
