链表的访问速度太慢,不适合大量的输入数据。而树的大部分运行时间平均为O(logN)。
定义树的一种自然的额方式是递归的方法。
1.实现二叉树
TianryTree.h
typedef int ElementType;
#ifndef BINARYTREE_H_INCLUDED
#define BINARYTREE_H_INCLUDED
//二叉树声明
struct TreeNode;
typedef struct TreeNode *PtrToNode;
typedef PtrToNode pNode;
typedef PtrToNode Tree;
Tree MakeEmpty( Tree &T);
pNode Find(ElementType X, Tree T);
pNode FindMin(Tree T);
pNode FindMax(Tree T);
void TraverTree(Tree T);
Tree Insert(ElementType X, Tree T);
Tree Delete(ElementType X, Tree T);
ElementType Retrieve(pNode P);
#endif // BINARYTREE_H_INCLUDED
BinaryTree.cpp
#include <iostream>
#include <stdlib.h>
#include "BinaryTree.h"
#include "fatal.h"
using namespace std;
//二叉树节点声明
struct TreeNode
{
ElementType Element;
Tree Left;
Tree Right;
};
//空树
Tree MakeEmpty(Tree &T)
{
if(T != NULL)
{
MakeEmpty(T->Left);
MakeEmpty(T->Right);
free(T);
T=NULL;
}
cout << "the empty operation is end !!! " << endl << endl;
return NULL;
}
//二叉查找数的find操作
pNode Find(ElementType X, Tree T)
{
if(T==NULL)
{
cout << "NOT FIND The ELEMENT "<< X << endl << endl;
return NULL;
}
if(X < T->Element)
{
cout << "serching " << T->Element << " Left SubTree..." << endl;
return Find(X, T->Left);
}
else if(X > T->Element)
{
cout << "searching " << T->Element << " Right SubTree..."<< endl;
return Find(X, T->Right);
}
else
{
cout << "the Element " << X << " is find !!! " << endl << endl;
return T;
}
}
//FinMin实现
pNode FindMin(Tree T)
{
if(T==NULL)
{
return NULL;
}
else if(T->Left == NULL)
{
cout << "the min is : " << T->Element << endl << endl;
return T;
}
else
return FindMin(T->Left);
}
pNode FindMax(Tree T)
{
if(T != NULL)
{
while(T->Right != NULL)
{
T=T->Right;
}
}
cout << "the max is : " << T->Element << endl << endl;
return T;
}
Tree Insert(ElementType X, Tree T)
{
if(T == NULL)
{
T = (struct TreeNode *)malloc(sizeof(struct TreeNode));
if(T == NULL)
{
FatalError("out of space!!!");
}
else
{
T->Element = X;
T->Left = T->Right = NULL;
cout << T->Element <<" Element! "<< endl;
}
}
else if(X < T->Element)
{
T->Left = Insert(X, T->Left);
}
else if(X > T->Element)
{
T->Right = Insert(X, T->Right);
}
cout << "insert is OK !!!" << endl << endl;
return T;
}
void TraverTree(Tree T)
{
if(T == NULL)
{
cout << "Travel --- the Tree is empty!!!" << endl << endl;
}
else
{
cout << "node " << T->Element << endl << endl;
TraverTree(T->Left);
TraverTree(T->Right);
}
}
int main()
{
cout << "The Program is Starting ...." << endl << endl;
Tree T = NULL;
T = Insert(5,T);
T = Insert(2,T);
T = Insert(1,T);
T = Insert(3,T);
T = Insert(7,T);
T = Insert(6,T);
T = Insert(9,T);
Find(1,T);
FindMin(T);
FindMax(T);
TraverTree(T);
MakeEmpty(T);
TraverTree(T);
return 0;
}
2.AVLTree,带有平衡条件的二叉查找树。树的深度是O(logN)。每个节点都必须有相同高度的左子树和右子树。
AVLTree.h
typedef int ElementType;
#ifndef AVLTREE_H_INCLUDED
#define AVLTREE_H_INCLUDED
struct AvlNode;
typedef struct AvlNode *PtrToNode;
typedef PtrToNode pNode;
typedef PtrToNode AvlTree;
AvlTree MakeEmpty(AvlTree &T);
pNode Find(ElementType X, AvlTree T);
pNode FindMin(AvlTree T);
pNode FindMax(AvlTree T);
AvlTree Insert(ElementType X, AvlTree T);
AvlTree Delete(ElementType X, AvlTree T);
ElementType Retrieve(pNode P);
static pNode SingleRotateWithLeft(pNode K);
static pNode DoubleRotateWithLeft(pNode K);
static pNode SingleRotateWithRight(pNode K);
static pNode DoubleRotateWithRight(pNode K);
void TraverTree(AvlTree T);
#endif // AVLTREE_H_INCLUDED
AVLTree.cpp
#include <iostream>
#include <stdlib.h>
#include "AVLTree.h"
#include "fatal.h"
using namespace std;
//AVL节点声明
struct AvlNode
{
ElementType Element;
AvlTree Left;
AvlTree Right;
int Height;
};
//取两个数中较大的数
int Max(int a, int b)
{
if(a<b)
{
return b;
}
else
{
return a;
}
}
//计算节点高度函数,空树高度为0
static int Height(pNode P)
{
if(P == NULL)
{
return 0;
}
else
return P->Height;
}
AvlTree Insert(ElementType X, AvlTree T)
{
if(T == NULL)
{
T = (struct AvlNode *)malloc(sizeof(struct AvlNode));
if(T == NULL)
{
FatalError("out of space !!!");
}
else
{
T->Element = X;
T->Height = 0;
T->Left = NULL;
T->Right = NULL;
cout << "insert the element " << T->Element << " in AvlTree ! " << T->Height << endl;
}
}
else
{
if(X<T->Element)
{
T->Left = Insert(X, T->Left);
if(Height(T->Left) - Height(T->Right) ==2)
{
if(X<T->Left->Element)
{
T = SingleRotateWithLeft(T);
}
else
{
T = DoubleRotateWithLeft(T);
}
}
}
if(X>T->Element)
{
T->Right = Insert(X, T->Right);
if(Height(T->Right) - Height(T->Left) ==2)
{
if(X>T->Right->Element)
{
T = SingleRotateWithRight(T);
}
else
{
T = DoubleRotateWithRight(T);
}
}
}
}
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
static pNode SingleRotateWithLeft(pNode K2)
{
pNode K1;
K1 = K2->Left;
K2->Left = K1->Right;
K1->Right = K2;
K2->Height = Max(Height(K2->Left), Height(K2->Right)) +1 ;
K1->Height = Max(Height(K1->Left), K2->Height) +1;
return K1;
}
static pNode SingleRotateWithRight(pNode K1)
{
pNode K2;
K2 = K1->Right;
K1->Right = K2->Left;
K2->Left = K1;
K2->Height = Max(Height(K1), Height(K2->Right)) + 1;
K1->Height = Max(Height(K1->Left), Height(K1->Right))+ 1;
return K2;
}
static pNode DoubleRotateWithLeft(pNode K3)
{
K3->Left = SingleRotateWithRight(K3->Left);
return SingleRotateWithLeft(K3);
}
static pNode DoubleRotateWithRight(pNode K3)
{
K3->Right = SingleRotateWithLeft(K3->Right);
return SingleRotateWithRight(K3);
}
void TraverTree(AvlTree T)
{
if(T == NULL)
{
cout << "Travel --- the Tree is empty!!!" << endl << endl;
}
else
{
cout << "Node: " << T->Element << " Height: " << T->Height << endl << endl;
TraverTree(T->Left);
TraverTree(T->Right);
}
}
int main()
{
cout << "AVLTree program is starting ..." << endl << endl << endl;
AvlTree T = NULL;
cout << "insert element ..." << endl << endl;
T = Insert(3,T);
T = Insert(2,T);
T = Insert(1,T);
T = Insert(10,T);
T = Insert(13,T);
cout << "print the node ..." << endl << endl;
TraverTree(T);
return 0;
}
#include
ifstream fin;
fin.open("1.txt");
int a[10];
fin >> a[i];
fin.close();
ofstream fout;