二叉树 & 平衡二叉树 算法(Java实现)
2024-09-17 16:40:38
二叉树
比如我要依次插入10、3、1、8、23、15、28。先插入10作为根节点:
然后插入3,比10小,放在左边:
再插入1,比10和3小,放在3左边:
再插入8,比10小,比3大,放在3右边:
再插入23,比10大,放在10右边:
再插入15,比10大,比23小,放在23左边:
最后插入28,比10和23大,放在23右边:
代码实现:
package com.demo.tree; import java.util.LinkedList;
import java.util.Queue; public class BinaryTree { public static void main(String[] args){
BinaryTree tree = new BinaryTree();
tree.batchInsert(new int[]{10,3,1,8,23,15,28});
tree.prePrint();
tree.midPrint();
tree.postPrint();
tree.tierPrint();
tree.printDepth();
} private Node root; /**
* 节点
*/
private class Node{
int data; // 数据
Node left; // 左指针
Node right; // 右指针 private Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
} /**
* 插入
* @param data
*/
public void insert(int data){
Node newData = new Node(data);
if (root == null){
root = newData;
}else{
Node parent = root;
while (true){
if (data < parent.data){
// 如果左边为空,那新数据就直接放在这
if (parent.left == null){
parent.left = newData;
break;
}
// 进入左节点
parent = parent.left;
}else{
// 如果右边为空,那新数据就直接放在这
if (parent.right == null){
parent.right = newData;
break;
}
// 进入右节点
parent = parent.right;
}
}
}
} /**
* 批量插入
* @param arr
*/
public void batchInsert(int[] arr){
for (int data : arr){
insert(data);
}
} /**
* 前序遍历
*/
public void prePrint(){
System.out.print("前序遍历\t");
if (root != null){
pre(root);
}
System.out.println();
} private void pre(Node node){
if (node != null) {
System.out.print(node.data + "\t");
pre(node.left);
pre(node.right);
}
} /**
* 中序遍历
*/
public void midPrint(){
System.out.print("中序遍历\t");
if (root != null){
mid(root);
}
System.out.println();
} private void mid(Node node){
if (node != null) {
mid(node.left);
System.out.print(node.data + "\t");
mid(node.right);
}
} /**
* 后序遍历
*/
public void postPrint(){
System.out.print("后序遍历\t");
if (root != null){
post(root);
}
System.out.println();
} private void post(Node node){
if (node != null) {
post(node.left);
post(node.right);
System.out.print(node.data + "\t");
}
} /**
* 层序遍历,利用队列先进先出
*/
public void tierPrint(){
if (root != null){
Queue<Node> queue = new LinkedList<>();
queue.add(root);
System.out.print("层序遍历\t");
while (!queue.isEmpty()){
Node temp = queue.remove();
System.out.print(temp.data + "\t");
if (temp.left != null){
// 左节点不为空,放进队列
queue.add(temp.left);
}
if (temp.right != null){
// 右节点不为空,放进队列
queue.add(temp.right);
}
}
}
System.out.println();
} /**
* 求树高
*/
public void printDepth(){
if (root == null){
System.out.println(0);
}else{
System.out.println("树高\t" + getDepth(root));
}
} private int getDepth(Node node){
if (node == null){
return 0;
}
return Math.max(getDepth(node.left), getDepth(node.right))+1;
} }
测试:
平衡二叉树
前面的二叉树有个问题,如果我们按照顺序插入,那么这个树就会退化成一个线性链表,这个时候引入平衡二叉树来解决。
平衡二叉树要维持平衡需要旋转操作
LL型(在A的左孩子(L)的左子树(L)上插入新结点)
过程:
1. 将A的左孩子B提升为根节点
2. 将A降级为B的右孩子
3. 将B的右孩子调整为A的左孩子
RR型(在A的右孩子(R)的右子树(R)上插入新结点)
过程:
1. 将A的右孩子B提升为根节点
2. 将A降级为B的左孩子
3. 将B的左孩子调整为A的右孩子
LR型(在A的左孩子(L)的右子树(R)上插入新结点)【插入在C任意一颗子树都可以】
过程:
1. B、C节点左旋。
2. A、C节点右旋。
RL型(在A的右孩子(R)的左子树(L)上插入新结点)【插入在C任意一颗子树都可以】
过程:
1. B、C节点右旋。
2. A、C节点左旋。
插入步骤图解
平衡二叉树的插入,例如依次插入:8,6,3,4,5,20,15,23,28,1,2
插入8先作为根节点,插入6依然平衡,插入3不平衡,进行一次右旋(LL)
插入4依然平衡,插入5不平衡,进行左旋(RR)
插入20依然平衡,插入15不平衡,先右旋再左旋(RL)
插入23依然平衡,插入28不平衡,进行一次左旋(RR)
插入1依然平衡,插入2不平衡,先左旋再右旋(LR)
代码
package com.demo.tree; import java.util.LinkedList;
import java.util.Queue; public class BalancedBinaryTree { public static void main(String[] args){
BalancedBinaryTree tree = new BalancedBinaryTree();
tree.batchInsert(new int[]{8,6,3,4,5,20,15,23,28,1,2});
tree.tierPrint();
} private Node root; /**
* 节点
*/
private class Node{
int data; // 数据
Node left; // 左指针
Node right; // 右指针 private Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
} /**
* 右旋操作(左孩子的左子树插入节点)
* @param p
*/
private Node rightRotate(Node p){
Node temp = p.left; // temp指向p的左子树
p.left = temp.right; // p的左子树指向temp的右子树
temp.right = p;
return temp;
} /**
* 左旋操作(右孩子的右子树插入节点)
* @param p
*/
private Node leftRotate(Node p){
Node temp = p.right; // temp指向p的右子树
p.right = temp.left; // p的右子树指向temp的左子树
temp.left = p;
return temp;
} /**
* 先左旋再右旋(左孩子的右子树插入节点)
* @param p
*/
private Node leftRightRotate(Node p){
p.left = leftRotate(p.left);
return rightRotate(p);
} /**
* 先右旋再左旋(右孩子的左子树插入节点)
* @param p
*/
private Node rightLeftRotate(Node p){
p.right = rightRotate(p.right);
return leftRotate(p);
} /**
* 树高
* @param node
* @return
*/
private int getDepth(Node node){
if (node == null){
return 0;
}
return Math.max(getDepth(node.left), getDepth(node.right))+1;
} /**
* 平衡因子(左高:>1 等高:0 右高:<-1)
* @return
*/
public int balanceFactor(Node node){
if (node == null){
return 0;
}
return getDepth(node.left) - getDepth(node.right);
} /**
* 插入
* @param node
* @param data
*/
public Node insert(Node node, int data){
Node newData = new Node(data);
if (node == null){
return newData;
}
if (data < node.data){
node.left = insert(node.left, data);
}else if (data > node.data){
node.right = insert(node.right, data);
}else{
return node;
}
int bf = balanceFactor(node); if (bf > 1 && data < node.left.data){
// LL
System.out.println("LL" + data);
return rightRotate(node);
}else if (bf < -1 && data > node.right.data){
// RR
System.out.println("RR" + data);
return leftRotate(node);
}else if (bf > 1 && data > node.left.data){
// LR
System.out.println("LR" + data);
return leftRightRotate(node);
}else if (bf < -1 && data < node.right.data){
// RL
System.out.println("RL" + data);
return rightLeftRotate(node);
}
return node;
} /**
* 批量插入
* @param arr
*/
public void batchInsert(int[] arr){
for (int data : arr){
root = insert(root, data);
}
} /**
* 前序遍历
*/
public void prePrint(){
System.out.print("前序遍历\t");
if (root != null){
pre(root);
}
System.out.println();
} private void pre(Node node){
if (node != null) {
System.out.print(node.data + "\t");
pre(node.left);
pre(node.right);
}
} /**
* 中序遍历
*/
public void midPrint(){
System.out.print("中序遍历\t");
if (root != null){
mid(root);
}
System.out.println();
} private void mid(Node node){
if (node != null) {
mid(node.left);
System.out.print(node.data + "\t");
mid(node.right);
}
} /**
* 后序遍历
*/
public void postPrint(){
System.out.print("后序遍历\t");
if (root != null){
post(root);
}
System.out.println();
} private void post(Node node){
if (node != null) {
post(node.left);
post(node.right);
System.out.print(node.data + "\t");
}
} /**
* 层序遍历,利用队列先进先出
*/
public void tierPrint(){
if (root != null){
Queue<Node> queue = new LinkedList<>();
queue.add(root);
System.out.print("层序遍历\t");
while (!queue.isEmpty()){
Node temp = queue.remove();
System.out.print(temp.data + "\t");
if (temp.left != null){
// 左节点不为空,放进队列
queue.add(temp.left);
}
if (temp.right != null){
// 右节点不为空,放进队列
queue.add(temp.right);
}
}
}
} }
最新文章
- 《Invert》开发日志00:缘起
- [ASP.NET]书店后台开发-模板页
- Angular从0到1:function(下)
- (easy)LeetCode 205.Reverse Linked List
- [NOI2001]反正切函数的应用
- 显示/去掉CONSOLE窗口
- [Gauss]POJ1222 EXTENDED LIGHTS OUT
- HTML DOM select() 方法
- kickstartInstalls
- vs错误【C1083 C1854 C4727】的若干解决办法(对预编译文件头的解释)
- 一百多道.NET面试题!
- 用DIV+css写Table
- margin:0 auto在ie7浏览器里面无效
- linux中的软连接和硬连接
- FineUIMvc随笔(4)自定义回发参数与自定义回发
- redis 基础学习总结
- cocos-lua3.17 Lua tablrView工具类
- MYSQL: 1292 - Truncated incorrect DOUBLE value: &#39;184B3C0A-C411-47F7-BE45-CE7C0818F420&#39;
- Android-滑动解锁高亮文字自定义TextView
- boost.property_tree解析xml的帮助类以及中文解析问题的解决(转)