参考:http://blog.csdn.net/zz198808/article/details/7621275
平衡二叉树,又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1。
问题:判断一个二叉排序树是否是平衡二叉树这里是二叉排序树的定义解决方案:根据平衡二叉树的定义,如果任意节点的左右子树的深度相差不超过1,那这棵树就是平衡二叉树。首先编写一个计算二叉树深度的函数,利用递归实现。
package cn.edu.tju.searchTree;
public class TreeDepth {
/*
* 若为空,则其深度为0,若只有一个结点则为1
* 否则,其深度等于左子树和右子树的深度的最大值加1
*/
public int getDepth(TreeNode node){
if(node == null){
return 0;
}else{
return getDepth(node.leftChild) > getDepth(node.rightChild) ? (getDepth(node.leftChild) + 1) :(getDepth(node.rightChild) + 1);
}
}
/*
* getNodeCount:计算二叉树的结点个数
*/
public int getNodeCount(TreeNode node){
if(node == null){
return 0;
}else{
return (getNodeCount(node.leftChild) + getNodeCount(node.rightChild) + 1);
}
}
/*
* isBalance:判断二叉树是否平衡
* 平衡二叉树,又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:
* 它的左子树和右子树都是平衡二叉树,且左子树和右子树的高度之差之差的绝对值不超过1。
* 根据平衡二叉树的定义,如果【任意】节点的左右子树的深度相差不超过1,那这棵树就是平衡二叉树。
*/
public boolean isBalance(TreeNode node){
if(node == null){
return true;
}
int distance = getDepth(node.leftChild) - getDepth(node.rightChild);
if(distance > 1 || distance < -1){
return false;
}else{
return isBalance(node.leftChild) && isBalance(node.rightChild);
}
}
}
分享到:
相关推荐
输入节点建立二叉树, 遍历递归的先中後序, 非递归的先中後序, 计算出深度 结点数 /* 运行结果: ------------------------ ...二叉树的结点个数是3 Press any key to continue ------------------------------ */
0. 建立二叉树(方法0) 1. 建立二叉树(方法1) 2. 统计叶子结点个数 3. 求二叉树的树深
通过递归查询二叉树的深度,首先分别递归根结点的左右子树,找出各自的深度,返回其中较大的深度
二叉树的三种遍历与求数的深度以及数的结点数 二叉树的三种遍历与求数的深度以及数的结点数
完整的计算C++二叉树叶子结点数及深度的程序,希望能帮到大家。
可实现: 输入相应元素,用先序创建二叉树(无元素处用“#”) ... 二叉数的深度: 交换二叉树的左右子树: 二叉树已左右交换。 递归先序遍历二叉树: 递归中序遍历二叉树: 递归后序遍历二叉树:
数据结构对二叉树结构的C++代码实现,包含基本的建立二叉树,各种方式遍历二叉树,深度计算、结点个数计算等等
利用二叉树的二叉链表存储结构求解二叉树的深度和双分支结点的个数;利用二叉树的二叉链表存储结构实现二叉排序树建树和删除操作。 实验内容: 题一:二叉树采用二叉链表结构表示。设计并实现如下算法:求一棵二叉树...
采用先序法建立一棵二叉树,设计求该二叉树的深度,二叉树的数据域类型为字符型, 扩展二叉树的叶子结点用‘#’表示,要求可以求多棵二叉树的深度,当二叉树的深度为0时程序结束。
深度为k的二叉树至多有2^k-1个结点;对任何一棵二叉树T,如果其终端结点数为n_0,度为2的结点数为n_2,则n_0=n_2+1。 一棵深度为k,且有2^k-1个节点的二叉树,称为满二叉树。这种树的特点是每一层上的节点数都是最大...
3 程序所能达到的功能:生成一个新的二叉树,实现对二叉树的先序,中序,后序和层次遍历,计算二叉树的深度,结点数,叶结点数,。 4 测式数据: A生成一个新的二叉树后,直接在键盘上按要求输入字符,可以依次输入...
本次实验是利用二叉排序树和平衡二叉树达到以下目的:(1)以回车('\n')为输入结束标志,输入数列L,生成一棵二叉排序树T;(2)对二叉排序树T作中序遍历,输出结果;(3)计算二叉排序树T查找成功的平均查找长度,输出结果...
数据结构二叉树的遍历 二叉树的深度 二叉树的某结点层次 二叉树结点数
/*建立二叉树后写出各种遍历算法,统计各类结点个数并求树的深度 (1)仅输出中序遍历第K个元素算法(奖励1分) (2)编写求某个结点在树中层数算法(奖励2分) (3)已知中序和后序建立树结构(奖励3分)*/
三) 在(二)的基础上,求二叉树的深度+结点数 (1)求出二叉树的深度并显示; (2)求出二叉树的结点总数并显示; (3)求叶子结点总数并显示。 四)应用题 (1)编制一个递归算法,求一个二叉树中位于先序序列中第k个...
设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树 2按(A:先序 B:中序 C:后序 )遍历输出二叉树的所有结点 ...
5. 深度为 k 的二叉树最多有 个结点,最少有 k 个结点。 三、综合题(共58分)。 1. 假定字符集{a,b,c,d,e,f }中的字符在电码中出现的次数如下: 字符 a b c d e f 频度 9 12 20 23 15 5 构造一棵哈夫曼树(6分...
( 统计二叉树结点.cpp )
总结的一些关于二叉树的算法,与大家共享(如统计叶子节点,复制二叉树,节点数目,深度算法等等等)
=10,深度从1开始,结点个数N<1024,结点编号1~N)的层次遍历序列和中序遍历序列,输出T从左向右叶子结点以及二叉树先序和后序遍历序列。输入格式输入共三行:第一行是整数n,表示二叉树中的结点数目;第二行有n...