建立AVL树并用前序的方式输出

#include <stdio.h> #include <string.h> #include <stdlib.h> #include <malloc.h> #include <math.h> typedef struct AVLtree { char element; int height; struct AVLtree* left; struct AVLtree* right; }AVLTREE; typedef struct AVLtree* Tree; Tree Insert(Tree T, char t); int Height(Tree T); void Preorder(Tree T); Tree DoubleRotateWithLeft(Tree T); Tree DoubleRotateWithRight(Tree T); Tree SingleRotateWithRight(Tree T); Tree SingleRotateWithLeft(Tree t1); int Max(int a, int b); int main() { Tree T=NULL; char initial[100]; char ch; int length; scanf("%s",initial); length=strlen(initial); for(int i=0;i<length;i++) { if(initial[i]!=',') { T=Insert(T, initial[i]); } } Preorder(T); return 0; } Tree Insert(Tree T, char t) { if(T==NULL) { T=(Tree)malloc(sizeof(struct AVLtree)); T->element=t; T->left=NULL; T->right=NULL; T->height=0; } else { if(t<T->element) { T->left=Insert(T->left,t); if(Height(T->left)-Height(T->right)==2) { if(t<T->left->element) { T=SingleRotateWithLeft(T); } else { T=DoubleRotateWithLeft(T); } } } if(t>T->element) { T->right=Insert(T->right,t); if(Height(T->right)-Height(T->left)==2) { if(t>T->right->element) { T=SingleRotateWithRight(T); } else { T=DoubleRotateWithRight(T); } } } } //T->height=Max(Height(T->left),Height(T->right))+1;// return T; } int Height(Tree T) { if(T==NULL) { return 1; } else { return 1+Max(Height(T->left),Height(T->right)); } } int Max(int a, int b) { if(a>b) { return a; } else { return b; } } Tree SingleRotateWithLeft(Tree T) { Tree t1; Tree t2; t1=T; t2=t1->left; t1->left=t2->right; t2->right=t1;// //t2->left=t1; //t1->height=Max(Height(t1->left),Height(t1->right)); //t2->height=Max(Height(t2->left),Height(t2->right)); return t2; } Tree SingleRotateWithRight(Tree T) { Tree t1=T; Tree t2=t1->right; t1->right=t2->left; t2->left=t1; //t2->right=t1; //t1->height=Max(Height(t1->left),Height(t1->right)); //t2->height=Max(Height(t2->left),Height(t2->right)); return t2; } Tree DoubleRotateWithRight(Tree T) { Tree t1=T; Tree t3=t1->right; Tree t2=t3->left; t1->right = t2->left; t3->left = t2->right; t2->left = t1; t2->right = t3; t1->height = Max(Height(t1->left), Height(t1->right)) + 1; t3->height = Max(Height(t3->left), Height(t3->right)) + 1; t2->height = Max(Height(t2->left), Height(t2->right)) + 1; return t2; } Tree DoubleRotateWithLeft(Tree T) { Tree t3=T; Tree t1=t3->left; Tree t2=t1->right; t1->right=t2->left; t3->left=t2->right; t2->left = t1; t2->right = t3; return t2; } void Preorder(Tree T) { if(T!=NULL) { printf("%c,",T->element); Preorder(T->left); Preorder(T->right); } }