import java.util.Arrays;
import java.util.Random;
import java.util.Stack;
public class BinaryTreeNode<T extends Comparable<T>> implements Comparable<T> {
public T data;
public BinaryTreeNode<T> parent;
public BinaryTreeNode<T> childL;
public BinaryTreeNode<T> childR;
public BinaryTreeNode() {
this(null);
}
public BinaryTreeNode(T data) {
this(data, null);
}
public BinaryTreeNode(T data, BinaryTreeNode<T> parent) {
this(data, parent, null, null);
}
public BinaryTreeNode(T data, BinaryTreeNode<T> parent, BinaryTreeNode<T> childL, BinaryTreeNode<T> childR) {
super();
this.data = data;
this.parent = parent;
this.childL = childL;
this.childR = childR;
}
@Override
public int compareTo(T e) {
if (data == e) {
return 0;
}
if (data == null) {
return -1;
}
if (e == null) {
return 1;
}
return data.compareTo(e);
}
@Override
public String toString() {
return String.valueOf(data);
}
//获得当前树的跟节点
public final BinaryTreeNode<T> getRoot() {
if (parent == null) {
return this;
}
BinaryTreeNode<T> root = parent;
while (root.parent != null) {
root = root.parent;
}
return root;
}
public final BinaryTreeNode<T> find(T target) {
int i;
BinaryTreeNode<T> node = this;
while (true) {
i = node.compareTo(target);
if (i > 0) {
if (node.childL != null) {
node = node.childL;
} else {
return null;
}
} else if (i < 0) {
if (node.childR != null) {
node = node.childR;
} else {
return null;
}
} else {
return node;
}
}
}
public final void add(T element) {
if (element == null) {
return;
}
if (this.data == null) {
this.data = element;
return;
}
int i;
BinaryTreeNode<T> node = this;
while (true) {
i = node.compareTo(element);
if (i > 0) {
if (node.childL != null) {
node = node.childL;
} else {
node.childL = new BinaryTreeNode<>(element, node);
}
} else if (i < 0) {
if (node.childR != null) {
node = node.childR;
} else {
node.childR = new BinaryTreeNode<>(element, node);
}
} else {
return;
}
}
}
//删除当前节点
public final void del() {
BinaryTreeNode<T> replace;
//如果具有左节点则取左边最大值进行替换
if ((replace = this.childL) != null) {
while (replace.childR != null) {
replace = replace.childR;//循环找到左侧最大元素
}
//替补节点是删除节点的左节点
if (this.childL == replace) {
this.childL = replace.childL;
} else {
replace.parent.childR = replace.childL;
}
//移交替补可能存在的子节点
if (replace.childL != null) {
replace.childL.parent = replace.parent;
}
} else if ((replace = this.childR) != null) {
//如果具有右节点则取右边最小值进行替换
while (replace.childL != null) {
replace = replace.childL;//循环找到右侧最大元素
}
if (this.childR == replace) {
this.childR = replace.childR;
} else {
replace.parent.childL = replace.childR;
}
if (replace.childR != null) {
replace.childR.parent = replace.parent;
}
}
//为空表示删除的是叶节点
if (replace == null) {
this.data = null;
if (this.parent != null) {
if (this.parent.childL == this) {
this.parent.childL = null;
} else {
this.parent.childR = null;
}
this.parent = null;
}
} else {
this.data = replace.data;
replace.parent = null;
}
}
/**
* 中序遍历
*/
public void midOrderTraverse(BinaryTreeNode<T> root) {
if (root == null || root.data == null) {
return;
}
//LDR
midOrderTraverse(root.childL);
System.out.print(root.data);
System.out.print(',');
System.out.print(' ');
midOrderTraverse(root.childR);
}
//非递归的中序遍历求和
public int inTraverseSum(BinaryTreeNode<T> root) {
Stack<BinaryTreeNode> st = new Stack<>();
BinaryTreeNode<T> p = root;
int count = 0;
while (p != null || !st.empty()) {
while (p != null) {
st.push(p);
count++;
p = p.childL;
}
if (!st.empty()) {
p = st.peek();
st.pop();
p = p.childR;
}
}
return count;
}
public void MorrisIn(BinaryTreeNode<T> head) {
if (head == null) return;
BinaryTreeNode<T> cur = head;
BinaryTreeNode<T> mostRight;
while (cur != null) {
mostRight = cur.childL;
//【1、2、】判断Cur的左孩子是否为空
if (cur.childL != null) {
//不断向右寻找Cur左子树最右的节点【mostRight右节点不为空 或者 不为当前cur节点，则非最右】
while (mostRight.childR != null && mostRight.childR != cur) {
mostRight = mostRight.childR;
}
// { 隐含意思：为空表示第一次来到该节点位置，为cur表示第二次来到该节点位置 }
//【2、(1)、】若最右节点为空
if (mostRight.childR == null) {
//{ 第一次来到该节点， 将该节右指针设为cur，表示该节点下一步将移动到cur }
mostRight.childR = cur;
cur = cur.childL;
continue;
} else {
//【2、(2)、】若最右节点为当前节点cur
/** { 第二次来到该节点， 将该节点右指针设为原来的null，
前一步其实已经将当前cur指针指向了该节点的右节点了，
即当前的cur已经是当前mostright的下一步节点了} */
mostRight.childR = null;
}
} else {//当前cur没有左孩子的时候
}
//【---【中序遍历】： 当前指针cur要准备往右孩子走了，马上打印】
System.out.print(cur.data);
//【1、】Cur的左孩子为空 或者【 2、(2)、】mostright的右孩子为Cur，即第二次访问到该节点的时候
cur = cur.childR;
}
}
public static void main(String[] args) {
BinaryTreeNode<Integer> tree = new BinaryTreeNode<>();
int[] arr = new int[16];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(99);
tree.add(arr[i]);
}
System.out.print("插入数据：");
System.out.println(Arrays.toString(arr));
System.out.print("数据排序：");
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.print("二叉树序：[");
tree.midOrderTraverse(tree);
System.out.println();
System.out.println(tree.inTraverseSum(tree));
System.out.println("----");
tree.MorrisIn(tree);
BinaryTreeNode<Integer> del;
for (int i = 0; i < arr.length; i++) {
System.out.print("删除数字");
System.out.println(arr[i]);
del = tree.find(arr[i]);
if (del != null) {
del.del();
}
tree.midOrderTraverse(tree);
System.out.println();
tree.add(arr[i]);
}
System.out.println("逐个删除：");
for (int i = 0; i < arr.length; i++) {
System.out.print("删除数字");
System.out.println(arr[i]);
del = tree.find(arr[i]);
if (del != null) {
del.del();
}
tree.midOrderTraverse(tree);
System.out.println();
}
}
}
网友评论