Is It An AVL Tree

7-1 Is It An AVL Tree (25 point(s))

In computer science, an AVL tree (Georgy Adelson-Velsky and Evgenii Landis’ tree, named after the inventors) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node differ by at most one. (Quoted from wikipedia)

For each given binary search tree, you are supposed to tell if it is an AVL tree.

Input Specification:

Each input file contains several test cases. The first line gives a positive integer K (≤10) which is the total number of cases. For each case, the first line gives a positive integer N (≤30), the total number of nodes in the binary search tree. The second line gives the preorder traversal sequence of the tree with all the keys being distinct. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in a line “Yes” if the given tree is an AVL tree, or “No” if not.

Sample Input:

3
7
50 40 36 48 46 62 77
8
50 40 36 48 46 62 77 88
6
50 40 36 48 46 62

Sample Output:

Yes
No
No

题目给出前序遍历的序列，可以利用这个序列一个一个插入来生成一棵树。之后再逐个计算节点因子判断是否为AVL树。

#include <iostream>
#include <algorithm>
using namespace std;

struct Node
{
    int value;
    Node *Left;
    Node *Right;
    Node(int _value): value(_value), Left(NULL), Right(NULL) {}
};

Node* insert(Node *p, int value);
int getHeight(Node *p);
bool AVLJudge(Node *p);

int main(int argc, const char *argv[])
{
    int K;
    cin >> K;
    while(K--)
    {
        int N;
        cin >> N;
        Node *Tree = NULL;
        for(int i = 0; i < N; i++)
        {
            int tmp;
            cin >> tmp;
            Tree = insert(Tree, tmp);
        }
        cout << (AVLJudge(Tree) ? "Yes" : "No") << endl;
    }

    return 0;
}


Node* insert(Node *p, int value)
{
    if(p == NULL)
        p = new Node(value);
    else
    {
        if(value < p->value)
            p->Left = insert(p->Left, value);
        else
            p->Right = insert(p->Right, value);
    }
    return p;
}


int getHeight(Node *p)
{
    if(p == NULL)
        return 0;
    else
        return max(getHeight(p->Left), getHeight(p->Right)) + 1;
}

bool AVLJudge(Node *p)
{
    if(p == NULL)
        return true;
    else
    {
        if(abs(getHeight(p->Left) - getHeight(p->Right)) > 1)
            return false;
        return AVLJudge(p->Left) && AVLJudge(p->Right);
    }
}

代码参考了https://www.cnblogs.com/littlepage/p/13194704.html

这代码写得挺妙的，每一步都有利用递归。

树结点的插入：

Node* insert(Node *p, int value)
{
    if(p == NULL)
        p = new Node(value);
    else
    {
        if(value < p->value)
            p->Left = insert(p->Left, value);
        else
            p->Right = insert(p->Right, value);
    }
    return p;
}

利用函数的返回值来修改原值，避免了修改传入参数导致原值没有被修改。调用时记得要赋值Tree = insert(Tree, tmp);

判断结点：

bool AVLJudge(Node *p)
{
    if(p == NULL)
        return true;
    else
    {
        if(abs(getHeight(p->Left) - getHeight(p->Right)) > 1)
            return false;
        return AVLJudge(p->Left) && AVLJudge(p->Right);
    }
}

利用了尾递归将判断结果传回。