04-树5 Root of AVL Tree

/*===================================================================================== # COPYRIGHT NOTICE # Copyright (c) 2016 # # @Author :Zehao Wang # @Email :zehaowang@163.com # @from ：https://pta.patest.cn/pta/test/1342/exam/4/question/20492 # @Last modified :2016-12-3 # @Description :求平衡二叉树根节点（涉及到旋转） ========================================================================================*/ #include <stdio.h> #include<stdlib.h> typedef struct AvlNode* AvlTree; struct AvlNode { int data; AvlTree left; AvlTree right; int height; }; //求两数最大值 int Max(int a, int b) { int i = (a > b ? a : b); return i; } //求节点高度。节点为NULL则高度为-1，没有左右儿子的节点高度为0 int height(AvlTree Tree) { if (!Tree) return -1; else return Tree->height; } //左单旋 AvlTree singleRotateWithLeft(AvlTree K1) { AvlTree K2 = K1->left; K1->left=K2->right; K2->right = K1; K1->height = Max(height(K1->left), height(K1->right))+1; K2->height = Max(height(K2->left), height(K1))+1; return K2; } //右单旋 AvlTree singleRotateWithRight(AvlTree K1) { AvlTree K2 = K1->right; K1->right = K2->left; K2->left = K1; K1->height=Max(height(K1->left), height(K1->right))+1; K2->height= Max(height(K1), height(K2->right))+1; return K2; } //左双旋 AvlTree doubleRotateWithLeft(AvlTree K1) { K1->left = singleRotateWithRight(K1->left); return singleRotateWithLeft(K1); } //右双旋 AvlTree doubleRotateWithRight(AvlTree K1) { K1->right = singleRotateWithLeft(K1->right); return singleRotateWithRight(K1); } //插入函数，每插入一个节点，都要调整一次平衡 AvlTree Insert(int x, AvlTree Tree) { if (Tree == NULL) { Tree = (AvlTree)malloc(sizeof(struct AvlNode)); Tree->data = x; Tree->left = NULL; Tree->right = NULL; Tree->height = 0; } else { if (x < Tree->data) { Tree->left=Insert(x, Tree->left); if (height(Tree->left)- height(Tree->right) == 2) { if (x < Tree->left->data) Tree = singleRotateWithLeft(Tree); else if (x > Tree->left->data) Tree = doubleRotateWithLeft(Tree); } } else if (x > Tree->data) { Tree->right = Insert(x, Tree->right); if (height(Tree->right) - height(Tree->left) == 2) { if (x > Tree->right->data) Tree = singleRotateWithRight(Tree); else if(x<Tree->right->data) Tree= doubleRotateWithRight(Tree); } } } Tree->height = Max(height(Tree->left), height(Tree->right)) + 1; return Tree; } int main(void) { int N; int x; scanf("%d", &N); AvlTree Tree; Tree = NULL; for (int i = 0; i < N; i++) { if (scanf("%d", &x) == 1) Tree = Insert(x, Tree); } printf("%d",Tree->data); } /*======================================================================================= 注：最开始学旋转的时候很难理解二叉树的旋转究竟是一个怎样的流程。后来偶然看到一篇讲解二叉树 插入旋转的文章之后，茅塞顿开。文章链接： http://www.2cto.com/kf/201606/514183.html 文章很重视思考的过程。从一开始为什么要旋转二叉树讲起，不断深入，最后一步步引到二叉树的不同 旋转方式。其实，所有的知识产物都是为了解决问题而被人不断思考，改进出来的，绝非空穴来风。但 现在大多数的教科书都会把人的思考过程隐去，只告诉你结论，只告诉你要掌握住什么。而有意无意的 忽略了知识从无到有产生的过程。或许思考过程并不如知识本身来的直接，但其中所蕴含的思考方式却 值得后人的借鉴，也更有利于知识被更好的理解。 ========================================================================================*/