package com.xiejianjun.day08.threadBinaryTreeDemo;
/**
* @author bilibilidick
* @version 2022 04
* @date 2022/4/22 17:45
*/
public class ThreadBinaryTreeDemo {
public static void main(String[] args) {
BinaryNode one = new BinaryNode(1, "one");
BinaryNode two = new BinaryNode(2, "two");
BinaryNode three = new BinaryNode(3, "three");
BinaryNode four = new BinaryNode(4, "four");
BinaryNode five = new BinaryNode(5, "five");
one.left = two;
one.right = three;
two.left = four;
three.right = five;
BinaryTree binaryTree = new BinaryTree();
binaryTree.setRoot(one);
binaryTree.preRootOrder();
/* binaryTree.inRootOrder();
binaryTree.postRootOrder();*/
binaryTree.deleteNodeById(4);
binaryTree.preRootOrder();
}
}
class BinaryTree {
public BinaryNode root;
public void setRoot(BinaryNode root) {
this.root = root;
}
public void preRootOrder() {
System.out.println("前序遍历根节点");
if (this.root != null)
this.root.preOrder();
}
public void inRootOrder() {
System.out.println("中序遍历根节点");
if (this.root != null)
this.root.inOrder();
}
public void postRootOrder() {
System.out.println("后序遍历根节点");
if (this.root != null)
this.root.postOrder();
}
public void deleteNodeById(int id) {
System.out.printf("开始删除值为%d的结点", id);
if (this.root == null) {
System.out.println("空树");
return;
}
if (this.root.id == id) {
this.root = null;
} else {
this.root.deleteNode(id);
}
}
}
class BinaryNode {
public int id;
public String name;
public BinaryNode left;
public BinaryNode right;
public int leftType = 0;
public int rightType = 0;
public BinaryNode pre = null;
public BinaryNode(int id, String name) {
this.id = id;
this.name = name;
}
@Override
public String toString() {
return "BinaryNode{" +
"id=" + id +
", name='" + name + '\'' +
'}';
}
public void preOrder() {
System.out.println(this);
if (this.left != null) {
this.left.preOrder();
}
if (this.right != null) {
this.right.preOrder();
}
}
public void inOrder() {
if (this.left != null) {
this.left.inOrder();
}
System.out.println(this);
if (this.right != null) {
this.right.inOrder();
}
}
public void postOrder() {
if (this.left != null) {
this.left.postOrder();
}
if (this.right != null) {
this.right.postOrder();
}
System.out.println(this);
}
public void deleteNode(int id) {
if (this.left != null) {
if (this.left.id == id) {
this.left = null;
return;
} else {
this.left.deleteNode(id);
}
}
if (this.right != null) {
if (this.right.id == id) {
this.right = null;
} else {
this.right.deleteNode(id);
}
}
}
public boolean isLeaf(BinaryNode node) {
return node.left == null && node.right == null;
}
public void deleteNode2(int id) {
// 叶子结点那直接删除
if (this.left != null) {
if (this.left.id == id) {
if (isLeaf(left)) this.left = null;
return;
} else {
this.left.deleteNode2(id);
}
}
if (this.right != null) {
if (this.right.id == id) {
if (isLeaf(right)) this.right = null;
} else {
this.right.deleteNode2(id);
}
}
}
public void threadTreeNode(BinaryNode node) {
if (node == null) {
return;
}
// 先中序线索化左子树
threadTreeNode(node.left);
// 线索化当前结点
// 先处理当前结点的前驱结点,如果当前节点的左子树为空,则让其指向前驱结点,并将leftType置为1
if (node.left == null) {
node.left = pre;
node.leftType = 1;
}
// 因为树是单向的,所以要在下一个结点处判断前一个结点的右子树是否为空,若为空,则将上一个结点的右子树指向自己,即后继结点的线索化
if (pre != null && pre.right == null) {
pre.right = node;
pre.rightType = 1;
}
pre = node;
// 再中序线索化右子树
threadTreeNode(node.right);
}
}
关键代码:
public void threadTreeNode(BinaryNode node) {
if (node == null) {
return;
}
// 先中序线索化左子树
threadTreeNode(node.left);
// 线索化当前结点
// 先处理当前结点的前驱结点,如果当前节点的左子树为空,则让其指向前驱结点,并将leftType置为1
if (node.left == null) {
node.left = pre;
node.leftType = 1;
}
// 因为树是单向的,所以要在下一个结点处判断前一个结点的右子树是否为空,若为空,则将上一个结点的右子树指向自己,即后继结点的线索化
if (pre != null && pre.right == null) {
pre.right = node;
pre.rightType = 1;
}
pre = node;
// 再中序线索化右子树
threadTreeNode(node.right);
}
精髓在于由于二叉树单向的特点,需要设置前驱结点,并且利用了第一个结点无须设置前驱结点的特性,绕开了第一层的设置,非常精妙
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)