锐客网

  1. 首页 > 生活百科 > it技术 > >

java判断满二叉树代码 判断一个二叉树是否为满二叉树

IT技术结点

java，完全二叉树？完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上 ， 则此二叉树称为完全二叉树 。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树 。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树 。
（3） 在完全二叉树中，若某个结点没有左孩子 ， 则它一定没有右孩子，即该结点必是叶结点 。
建立一个二叉树，附带查询代码，JAVA代码import java.util.ArrayList;
// 树的一个节点
class TreeNode {
Object _value = https://www.04ip.com/post/null; // 他的值
TreeNode _parent = null; // 他的父节点，根节点没有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子节点
public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = https://www.04ip.com/post/value;
}
public TreeNode getParent(){
return _parent;
}
public String toString() {
return _value.toString();
}
}
public class Tree {
// 给出宽度优先遍历的值数组，构建出一棵多叉树
// null 值表示一个层次的结束
// "|" 表示一个层次中一个父亲节点的孩子输入结束
// 如：给定下面的值数组：
// { "root", null, "left", "right", null }
// 则构建出一个根节点，带有两个孩子("left","right")的树
public Tree( Object[] values ){
// 创建根
_root = new TreeNode( values[0], null );
// 创建下面的子节点
TreeNode currentParent = _root; // 用于待创建节点的父亲
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父亲的第几个儿子
//TreeNode lastNode = null; // 最后一个创建出来的TreeNode，用于找到他的父亲
for ( int i = 2; ivalues.length; i){
// 如果null ,表示下一个节点的父亲是当前节点的父亲的第一个孩子节点
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}
// 表示一个父节点的所有孩子输入完毕
if ( values[i].equals("|") ){
if ( currentChildIndex 1currentParent._childList.size() ){
currentChildIndex;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}
TreeNode child = createChildNode( currentParent, values[i] );
}
}
TreeNode _root = null;
public TreeNode getRoot(){
return _root;
}
/**
// 按宽度优先遍历，打印出parent子树所有的节点
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; iparent._childList.size(); i){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth ":" child);
}
if ( parent._childList.size() != 0 )System.out.println("" null);// 为了避免叶子节点也会打印null
//打印 parent 同层的节点的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( iparent._parent._childList.size() ){// parent 的父亲还有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i;
}
}
// 递归调用，打印所有节点
for ( int i = 0; iparent._childList.size(); i){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth 1 );
}
}
// 按宽度优先遍历，打印出parent子树所有的节点
public void printSteps(){
System.out.println("" _root);
System.out.println("" null);
printSteps(_root, 1 );
}**/
// 将给定的值做为 parent 的孩子，构建节点
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}
public static void main(String[] args) {
Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();
System.out.println(""( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );
System.out.println(""( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );
}
}
java：二叉树添加和查询方法
package arrays.myArray;
public class BinaryTree {
private Node root;
// 添加数据
public void add(int data) {
// 递归调用
if (null == root)
root = new Node(data, null, null);
else
addTree(root, data);
}
private void addTree(Node rootNode, int data) {
// 添加到左边
if (rootNode.datadata) {
if (rootNode.left == null)
rootNode.left = new Node(data, null, null);
else
addTree(rootNode.left, data);
} else {
// 添加到右边
if (rootNode.right == null)
rootNode.right = new Node(data, null, null);
else
addTree(rootNode.right, data);
}
}
// 查询数据
public void show() {
showTree(root);
}
private void showTree(Node node) {
if (node.left != null) {
showTree(node.left);
}
System.out.println(node.data);
if (node.right != null) {
showTree(node.right);
}
}
}
class Node {
int data;
Node left;
Node right;
public Node(int data, Node left, Node right) {
this.data = https://www.04ip.com/post/data;
this.left = left;
this.right = right;
}
}
如何判断二叉树是满二叉树满二叉树的判断方法：
除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点） 。也可以这样理解 ， 除叶子结点外的所有结点均有两个子结点 。节点数达到最大值 。所有叶子结点必须在同一层上 。
结点（如果一颗树深度为h，最大层数为k）：
1、它的叶子数是： 2^(h-1)；
2、第k层的结点数是： 2^(k-1)；
3、总结点数是： 2^k-1 (2的k次方减一)；
4、总节点数一定是奇数 。
已知一颗二叉链表表示二叉树T，编写函数，判断T是否为完全二叉树 。先问题：判断二叉树是否为完全二叉树 。完全二叉树的定义是java判断满二叉树代码，前n-1层都是满的java判断满二叉树代码，第n层如有空缺，则是缺在右边，即第n层的最右边的节点，它的左边是满的，右边是空的 。以3层二叉树为例，以下情况为完全二叉树：[方法一]这个问题的描述已经提示java判断满二叉树代码了解法 ， 采用广度优先遍历，从根节点开始 ， 入队列，如果队列不为空，循环 。遇到第一个没有左儿子或者右儿子的节点，设置标志位 ， 如果之后再遇到有左/右儿子的节点，那么这不是一颗完全二叉树 。这个方法需要遍历整棵树，复杂度为O(N) ， N为节点的总数 。//二叉树结点定义typedefstructNode{intdata;structNode*left;structNode*right;}Node;//实现广度遍历需要队列Queuequeue;//第n层最右节点标志boolleftMost=false;boolProcessChild(Node*child){if(child){if(!leftMost){queue.push(child);}else{returnfalse;}}else{leftMost=true;}returntrue;}boolIsCompleteBinaryTree(Node*root){//空树也是完全二叉树if(!root)returntrue;//首先根节点入队列queue.push(root);while(!queue.empty()){Node*node=queue.pop();//处理左节点if(!ProcessChild(node-left))returnfalse;//处理右节点if(!ProcessChild(node-right))returnfalse;}//广度优先遍历完毕，此乃完全二叉树returntrue;}[方法二]根据完全二叉树的定义，左边的深度=右边的深度 。从根节点开始，分别沿着最左最右分支下去，找到最左和最右的深度 。如果左边比右边深1，再分别检查以左儿子和右儿子为根的两根树 。有点递归的感觉了 。[Tobecontinued]
java二叉树遍历问题二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1) 。
证明：用数学归纳法证明：
归纳基?。篿=1时，有2i-1=20=1 。因为第1层上只有一个根结点，所以命题成立 。
归纳假设：假设对所有的j(1≤ji)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立 。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点 。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍 。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立 。
性质2 深度为k的二叉树至多有2k-1个结点(k≥1) 。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多 。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20 21 … 2k-1=2k-1
故命题正确 。
性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2 1 。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no n1 n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl 2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1 2n2 1 (式子2)
由式子1和式子2得到：
no=n2 1
满二叉树和完全二叉树是二叉树的两种特殊情形 。
1、满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二又树称为满二叉树 。
满二叉树的特点：
（1） 每一层上的结点数都达到最大值 。即对给定的高度，它是具有最多结点数的二叉树 。
（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上 。
图(a)是一个深度为4的满二叉树 。
2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2 ， 并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树 。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树 。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树 。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点 。
如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树 。
图(b)是一棵完全二叉树 。
性质4 具有n个结点的完全二叉树的深度为
证明：设所求完全二叉树的深度为k 。由完全二叉树定义可得：
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树 ， 一共有2k-1-1个结点 。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
n2k-1-1 。
另一方面，由性质2可得：
n≤2k-1 ，
即：2k-1-ln≤2k-1
由此可推出：2k-1≤n2k，取对数后有：
k-1≤lgnk
又因k-1和k是相邻的两个整数 ， 故有
,
由此即得：
注意：
的证明
急急～判断一棵二叉树是满二叉树的算法！我的思路是利用满二叉树的性质来判断 。满二叉树一定符合
节点数
=
2的n次方
【java判断满二叉树代码 判断一个二叉树是否为满二叉树】-1
（n为深度）
所以可以先遍历二叉树，并记录深度和节点数，最后做出判断
#includestdio.h
void
inorder(bintree
*t,int
currentDeep)
{
if(*t!=NULL)
{
if(currentDeepdeep)
deep=currentDeep;
/*
如果当前深度大于记录的深度，则更新深度
*/
countNodes;
/*
节点数加一
*/
inorder(t-lchild,currentDeep 1);
/*
访问当前节点的左孩子 ， 并把当前节点的深度 1传给调用函数
*/
inorder(t-rchild,currentDeep 1);
/*
访问当前节点的右孩子，并把当前节点的深度 1传给调用函数
*/
}
}
main()
{
/*
p
为二叉树的根节点，其定义略
*/
int
currentDeep=1;
/*
currentDeep用于记录当前深度
static
int
deep=0;
/*
静态变量deep用于记录已检索的最大深度
*/
static
int
countNodes=0;
/*
静态变量countNodes用于记录已检索的节点数目
*/
inorder(p,currentDeep);
/*
中序遍历二叉树从而得到二叉树的深度以及节点数目
*/
if(countNodes(pow(2,deep)-1))
printf("这不是一棵满二叉树 。");
else
printf("这是一棵满二叉树 。");
/*
利用满二叉树的节点数一定等于2的深度次方减1做出判断
*/
/*
pow函数的作用是求2的deep次方
*/
camb_yang
同学满二叉树为什么就不用判断呢？
java判断满二叉树代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于判断一个二叉树是否为满二叉树、java判断满二叉树代码的信息别忘了在本站进行查找喔 。

    推荐阅读


    上一篇：为什么拍摄闪电，为什么拍摄闪电不能拍

    下一篇：电脑钉钉群怎么建，电脑钉钉群怎么建相册