问题描述

平衡二叉树的构造及验证

要求实现以下功能

1.输入节点数据，构造二叉树的节点，按二叉排序树的规则插入该节点到三叉链表中；
2.根据不平衡节点左右孩子及插入新结点的值，判定二叉树的不平衡状态｛LL、LR、RR、RL｝；
3.输入二叉树的前序或后序，中序序列，手动恢复二叉树，验证中序序列的有序性；
4.四种旋转方式用四个独立的函数实现；
5.分析平衡二叉树的平衡效率ASL

解决方案

平衡二叉树的左右子树都是平衡二叉树，并且左右子树的深度的差值的绝对值不超过1.平衡二叉树上的任何节点的左子树和右子树的深度的差值只能是－1、0或1。
对于该题目：
首先一个完全二叉树必然是平衡二叉树。对于深度为N的完全二叉树一共有2^N-1个节点。

当N=3时，共有2^3-1=7个节点；
当N=4时，共有2^4-1=15个节点；
当N=5时，共有2^5-1=31个节点；
当N=6时，共有2^6-1=63个节点。