写点什么

java 实现简单二叉树,深入分布式缓存从原理到实践技术分享

用户头像
极客good
关注
发布于: 刚刚

定义:高度为 h,并且由 2h-1 个结点组成的二叉树,称为满二叉树



2、完全二叉树


定义:一棵二叉树中,只有最下面两层结点的度可以小于 2,并且最下层的叶结点集中在靠左的若干位置上,这样的二叉树称为完全二叉树。


特点:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。



面试题:如果一个完全二叉树的结点总数为 768 个,求叶子结点的个数。


由二叉树的性质知:n0=n2+1,将之带入 768=n0+n1+n2 中得:768=n1+2n2+1,因为完全二叉树度为 1 的结点个数要么为 0,要么为 1,那么就把 n1=0 或者 1 都代入公式中,很容易发现 n1=1 才符合条件。所以算出来 n2=383,所以叶子结点个数 n0=n2+1=384。


总结规律:如果一棵完全二叉树的结点总数为 n,那么叶子结点等于 n/2(当 n 为偶数时)或者(n+1)/2(当 n 为奇数时)


3、二叉查找树


定义:二叉查找树又被称为二叉搜索树。设 x 为二叉查找树中的一个结点,x 结点包含关键字 key,结点 x 的 key 值计为 key[x]。如果 y 是 x 的左子树中的一个结点,则 key[y]<=key[x];如果 y 是 x 的右子树的一个结点,则 key[y]>=key[x]



在二叉查找树种:


(1)若任意结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值。


(2)任意结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值。


(3)任意结点的左、右子树也分别为二叉查找树。


(4)没有键值相等的结点。


要求:将一个数组中的数以二叉树的存储结构存储,并遍历打印。


import java.util.ArrayList; import java.util.List; public class bintree { public bintree left; public bintree right; public bintree root; // 数据域 private Object data; // 存节点 public List<bintree> datas; public bintree(bintree left, bintree right, Object data){ this.left=left; this.right=right; this.data=data; } // 将初始的左右孩子值为空 public bintree(Object data){ this(null,null,data); } public bintree() { } public void creat(Object[] objs){ datas=new ArrayList<bintree>(); // 将一个数组的值依次转换为Node节点 for(Object o:objs){ datas.add(new bintree(o)); } // 第一个数为根节点 root=datas.get(0); // 建立二叉树 for (int i = 0; i <objs.length/2; i++) { // 左孩子 datas.get(i).left=datas.get(i*2+1); // 右孩子 if(i*2+2<datas.size()){//避免偶数的时候 下标越界 datas.get(i).right=datas.get(i*2+2); } } } //先序遍历 public void preorder(bintree root){ if(root!=null){ System.out.println(root.data); preorder(root.left); preorder(root.right); } } //中序遍历 public void inorder(bintree root){ if(root!=null){ inorder(root.left); System.out.println(root.data); inorder(root.right); } } // 后序遍历 public void afterorder(bintree root){ if(root!=null){ System.out.println(root.data); afterorder(root.left); afterorder(root.right); } } public static void main(String[] args) { bintree bintree=new bintree(); Object []a={2,4,5,7,1,6,12,32,51,22}; bintree.creat(a); bintree.preorder(bintree.root); } }


要求:从键盘输入数,存为二叉树结构并打印。


import java.util.Scanner;


public class btree {


private btree left,right;


private char data;


public btree creat(String des){


Scanner scanner=new Scanner(System.in);


System.out.println("des:"+des);


String str=scanner.next();


if(str.charAt(0)<'a')return null;


btree root=new btree();


root.data=str.charAt(0);


root.left=creat(str.charAt(0)+"左子树");


root.right=creat(str.charAt(0)+"右子树");


return root;


}


public void midprint(btree btree){


// 中序遍历


if(btree!=null){


midprint(btree.left);


System.out.print(btree.data+" ");


midprint(btree.right);


}


}


public void firprint(btree btree){


// 先序遍历


if(btree!=null){


System.out.print(btree.data+" ");


firprint(btree.left);


firprint(btree.right);


}


}


public void lastprint(btree btree){


// 后序遍历


if(btree!=null){


lastprint(btree.left);


lastprint(btree.right);


System.out.print(


【一线大厂Java面试题解析+核心总结学习笔记+最新架构讲解视频+实战项目源码讲义】
浏览器打开:qq.cn.hn/FTf 免费领取
复制代码


btree.data+" ");


}


}


public static void main(String[] args) {


btree tree = new btree();


btree newtree=tree.creat("根节点");


tree.firprint(newtree);


System.out.println();


tree.midprint(newtree);


System.out.println();


tree.lastprint(newtree);


}


}


输出结果:


des:根节点


a


des:a 左子树


e


des:e 左子树


c


des:c 左子树


1


des:c 右子树


1


des:e 右子树


b


des:b 左子树


1


des:b 右子树


1


des:a 右子树


d


des:d 左子树


f


des:f 左子树


1


des:f 右子树


1


des:d 右子树


1


a e c b d f? ? ? ? 先序


c ?e ?b ?a ?f ?d? ?中序


c ?b ?e ?f ?d ?a? ?后序


二叉树的遍历次序:


前序顺序是根节点排最先,然后同级先左后右;中序顺序是先左后根最后右;后序顺序是先左后右最后根。

用户头像

极客good

关注

还未添加个人签名 2021.03.18 加入

还未添加个人简介

评论

发布
暂无评论
java实现简单二叉树,深入分布式缓存从原理到实践技术分享