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

定义：高度为 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? ?后序

二叉树的遍历次序：

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