前置知识:
什么是二叉树:一个递归的树形数据结构,每个节点最多有两个子节点;
二叉树一般都是二分查找树,每个节点的值大于它左子节点的值,小于它右子节点的值
二叉树遍历:
递归遍历:
前序遍历:先访问根节点,再访问左子节点,最后访问右子节点
上图中前序遍历结果:30、20、5、28、50、38、58
中序遍历:先访问左子节点,再访问根节点,最后访问右子节点
上图中中序遍历结果:5、20、28、30、38、50、58
后序遍历:先访问左子节点,再访问右子节点,最后访问根节点
上图中后序遍历结果:5、28、20、38、58、50、30
非递归遍历:
常用的是利用栈的先进后出特性,不断地将节点入栈,然后再出栈
非递归前序遍历和非递归中序遍历两种方式很好理解,控制遍历时机即可,而非递归后序遍历较为复杂,需要额外维护一个最后访问节点
二叉树demo
详细实现原理都在注释中,花了几天写的,球球你好好看看,来都来了
public class MyBinaryTree {
//根节点
private MyNode root;
//注意,这是私有方法,对用户开放的新增方法在下面,其它几个方法也是
private MyNode addNode(MyNode current, int value) {
//如果根节点为空,直接new个新节点
if (current == null) return new MyNode(value);
if (value < current.value) {
//如果当前插入节点的值小于根节点,则在树的左边递归插入
current.left = addNode(current.left, value);
} else if (value > current.value) {
//如果当前插入节点的值大于根节点,则在树的右边递归插入
current.right = addNode(current.right, value);
} else {
//如果等于,直接返回
return current;
}
return current;
}
public void addNode(int value) {
//指定当前根节点
root = addNode(root, value);
}
private boolean isContainNode(MyNode current, int value) {
//如果当前根节点不存在,直接返回false
if (current == null) return false;
//如果根节点存在并且值等于当前查找值,返回true
if (current.value == value) return true;
//如果目标值大于当前节点值,则在右子树递归查找,反之在左子树递归查找
return value > current.value ? isContainNode(current.right, value) : isContainNode(current.left, value);
}
public boolean isContainNode(int value) {
//从根节点开始找
return isContainNode(root, value);
}
//删除节点比较复杂,或许会让你看了以后疯狂怀疑自己,请酌情查看
private MyNode deleteNode(MyNode current, int value) {
//如果节点不存在,就不删咯
if (!isContainNode(value) || current == null) return null;
//如果目标节点等于根节点
if (current.value == value) {
//目标节点无子节点,直接删除目标节点
if (current.left == null && current.right == null) return null;
//目标节点只有左子节点,直接删除目标节点,并将目标节点的父节点指向左子节点
if (current.right == null) return current.left;
//目标节点只有右子节点,直接删除目标节点,并将目标节点的父节点指向右子节点
if (current.left == null) return current.right;
//目标节点既有左子节点又有右子节点,这种比较复杂
//需要将目标节点右子节点的最左节点,或者目标节点左子节点的最右节点替换成目标节点,然后将目标节点删除
//我们这里是替换目标节点右子节点的最左节点,所以需要找到目标节点右子节点下面最小的那个节点,即左最节点
int i = findSmallerNode(current.right);
//将目标节点替换成找到的最左节点
current.value = i;
//递归删除,满足上面能删除的三种情况
current.right = deleteNode(current.right, i);
return current;
} else if (current.value > value) {
current.left = deleteNode(current.left, value);
return current;
} else {
current.right = deleteNode(current.right, value);
return current;
}
}
public boolean deleteNode(int value) {
MyNode node = deleteNode(root, value);
if (node == null) return false;
return true;
}
//中序递归遍历
private void centerShow(MyNode root) {
if (root != null) {
//先递归遍历左子树
centerShow(root.left);
//遍历根节点
System.out.print(root.value + " ");
//再递归遍历右子树
centerShow(root.right);
}
}
public void centerShow() {
System.out.print("\n中序递归遍历:");
centerShow(root);
}
public void centerShowPro() {
System.out.print("\n中序非递归遍历:");
//利用栈的先进后出
Stack<MyNode> nodeStack = new Stack<>();
while (root != null || !nodeStack.isEmpty()) {
//将根节点遍历入栈
while (root != null) {
nodeStack.push(root);
root = root.left;
}
//取出栈顶元素作为根节点并删除栈顶元素,此时栈顶元素为最左节点的值
root = nodeStack.pop();
//遍历左节点,因为是从根往左入栈,所以出栈是从左到根
System.out.print(root.value + " ");
//找到下一个节点,依次往右遍历
root = root.right;
}
}
private void preShow(MyNode root) {
if (root != null) {
//先遍历根节点
System.out.print(root.value + " ");
//然后遍历左节点
preShow(root.left);
//再遍历右节点
preShow(root.right);
}
}
public void preShow() {
System.out.print("\n先序递归遍历:");
preShow(root);
}
public void preShowPro() {
System.out.print("\n先序非递归遍历:");
Stack<MyNode> nodeStack = new Stack<>();
while (root != null || !nodeStack.isEmpty()) {
while (root != null) {
//同中序非递归遍历,只是这里先遍历根节点
System.out.print(root.value + " ");
nodeStack.push(root);
root = root.left;
}
root = nodeStack.pop();
root = root.right;
}
}
private void afterShow(MyNode root) {
if (root != null) {
afterShow(root.left);
afterShow(root.right);
System.out.print(root.value + " ");
}
}
public void afterShow() {
System.out.print("\n后序递归遍历:");
afterShow(root);
}
public void afterShowPro() {
System.out.print("\n后序非递归遍历:");
Stack<MyNode> nodeStack = new Stack<>();
MyNode lastNode = null;
while (root != null || !nodeStack.isEmpty()) {
while (root != null) {
nodeStack.push(root);
root = root.left;
}
//取出栈顶元素但不删除
root = nodeStack.peek();
//如果栈顶元素的右节点为空或者它是最后一次访问的节点
if (root.right == null || root.right == lastNode) {
//遍历当前节点
System.out.print(root.value + " ");
lastNode = nodeStack.pop();
root = null;
} else {
root = root.right;
}
}
}
private int findSmallerNode(MyNode root) {
//删除节点用的,用来找到节点的最左子节点
return root.left == null ? root.value : findSmallerNode(root.right);
}
//节点,为了演示方便,只支持存放int数字
private class MyNode {
private int value;
private MyNode left;
private MyNode right;
public MyNode(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
}
测试:
public class MyBinaryTest {
public static void main(String[] args) {
deleteTest();
testPre();
testPrePro();
testCenter();
testCenterPro();
testAfter();
testAfterPro();
}
public static void deleteTest() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
System.out.println("是否存在28:"+tree.isContainNode(28));
tree.deleteNode(28);
System.out.println("删除28后是否还存在28:"+tree.isContainNode(28));
}
public static void testCenter() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
tree.centerShow();
}
public static void testCenterPro() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
tree.centerShowPro();
}
public static void testPre() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
tree.preShow();
}
public static void testPrePro() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
tree.preShowPro();
}
public static void testAfter() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
tree.afterShow();
}
public static void testAfterPro() {
MyBinaryTree tree = new MyBinaryTree();
tree.addNode(30);
tree.addNode(20);
tree.addNode(5);
tree.addNode(28);
tree.addNode(50);
tree.addNode(38);
tree.addNode(58);
tree.afterShowPro();
}
}
运行结果:
是否存在28:true
删除28后是否还存在28:false
先序递归遍历:30 20 5 28 50 38 58
先序非递归遍历:30 20 5 28 50 38 58
中序递归遍历:5 20 28 30 38 50 58
中序非递归遍历:5 20 28 30 38 50 58
后序递归遍历:5 28 20 38 58 50 30
后序非递归遍历:5 28 20 38 58 50 30
还是那句话,家里有条件的一定一定一定复制到idea跑一跑
ok我话说完,skr~