2 xm12345l xm12345l 于 2012.12.14 13:48 提问

平衡二叉树的构造及验证

要求实现以下功能

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

1个回答

ansjsun
ansjsun   2012.12.14 13:57

平衡二叉树的左右子树都是平衡二叉树,并且左右子树的深度的差值的绝对值不超过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个节点。

hooopo
hooopo 老师讲数据结构的时候我都睡觉去了......
大约 5 年之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!