由于上个文件字数到达2w以上，本软件加载比较麻烦，故而新建一个文件用来记录。

数据结构与算法

9 哈希表

一种数据结构

一般有hashMap,hashtable

哈希表，是一种数据结构，主要是key 与value的关系，了解hash表之前，我们需要了解的是哈希表，需要知道哈希函数，在jdk1.8之后，采用的红黑树进行一定的存储，其是根据关键码值而进行访问的数据结构，也就是说，其通过把关键码映射到表中的一个位置来访问记录，以加快查找的速度，这个映射函数我们称之为散列函数，存放记录的数组叫做散列表。

hashtable来存储雇员信息。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
public class HashtableDemo {

	public static void main(String[] args) {
		hashTable hashtab = new hashTable(8);
        Emp Emp1 = new Emp(10,"社会虎");
        Emp Emp2 = new Emp(18,"废物刀");
        Emp Emp3 = new Emp(26,"黑牛");
        Emp Emp4 = new Emp(3,"白牛");
        Emp Emp5 = new Emp(193,"小亮");
        Emp Emp6 = new Emp(231,"唐老鸭");
        Emp Emp7 = new Emp(12,"百特曼");
        Emp Emp8 = new Emp(1,"独爱小尹");
        Emp Emp9 = new Emp(123,"丽丽");
        Emp Emp10 = new Emp(126,"带篮子");
        Emp Emp11 = new Emp(29,"刘墉");
        Emp Emp12 = new Emp(86,"丁真");
        Emp Emp13 = new Emp(800,"王冰冰");//定义数据

        hashtab.add(Emp1);
        hashtab.add(Emp2);
        hashtab.add(Emp3);
        hashtab.add(Emp4);
        hashtab.add(Emp5);
        hashtab.add(Emp6);
        hashtab.add(Emp7);
        hashtab.add(Emp8);
        hashtab.add(Emp9);
        hashtab.add(Emp10);
        hashtab.add(Emp11);
        hashtab.add(Emp12);
        hashtab.add(Emp13);//插入数据
        
        hashtab.list();
	}
}

//创建hashtable
class hashTable{
	private int size;
	private EmpLinkedList[] empLinkedLists;
	//创建一个构造器
	public hashTable(int size) {
		this.size = size;
		//初始化empLinkedListArray
		empLinkedLists = new EmpLinkedList[size];
		//细节，引用类型的变量在声明后如果不初始化那么默认值就是null
		for(int i = 0 ; i < size; i++) {
			//这个循环体就是在初始化
			empLinkedLists[i] = new EmpLinkedList();//在这里必须要逐一为每个元素实例化
		}
	}
	public int hash(int id) {
		return id % size;
	}
	//添加雇员
	public void add(Emp emp){
		//根据员工的id得到该员工应该加入
		int num = hash(emp.id);
		empLinkedLists[num].add(emp);
	}
	public void list() {
		for(int i = 0 ; i < size ; i ++ ) {
			System.out.println("第"+i+"个链表状况");
			empLinkedLists[i].list();
		}
	}
}

//表是
class Emp{
	public int id;
	public String name;
	public Emp next;  //next 默认为空
	public Emp() {
		super();
	}
	public Emp(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}
	public int getId() {
		return id;
	}
	public void setId(int id) {
		this.id = id;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public Emp getNext() {
		return next;
	}
	public void setNext(Emp next) {
		this.next = next;
	}
}
//创建一个EmpLinkList,表示链表
class EmpLinkedList{
	//投指针，执行第一个Emp,因此我们这个链表的head是直接指向第一个Emp
	private Emp head; //默认为空
	//添加雇员到链表
	//说明
	//假定，当添加雇员时候，id是自增长，即id的分配总数从小到大的
	//因此我们将该雇员直接加入到本链表的最后即可
	public void add(Emp emp) {
		//如果是第一个雇员
		if(head == null ) {
			head = emp;
			return ;
		}
		//如果不是第一个雇员，则使用一个辅助的指针，帮助定位到最后
		Emp curEmp = head;
		while(true) {
			if(curEmp.next == null) {
				break;
			}
			curEmp = curEmp.next; //后移
		}
		//退出时直接将emp加入链表
		curEmp.next = emp;
	}
	//遍历链表的雇员信息
	public void list() {
		if(head == null) {
			//如果链表为空
			System.out.println("当前链表为空");
			return ;
		}
		System.out.println("当前链表的信息为：");
		Emp cuEmp = head ; //辅助指针
		int count = 0;
		while(true) {
			System.out.printf("id = %d name = %s\n",cuEmp.id,cuEmp.name);
			count ++;
			if(cuEmp.next == null ) {
				//说明cuEmp已经是最后的节点
			System.out.println("共计有"+ count+ "个");
				break;
			}
			cuEmp = cuEmp.next;//后移，遍历
		}
	}
}

10.数据结构的存储方式

10.1二叉树

  1. 数组的存储方式的分析
    优点：通过下标方式访问元素，速度快。对于有序数组，还可以使用二分查找提高检索速度。

    缺点：如果要检索具体某个值，或者插入值（按照一定顺序）会整体移动，效率较低。

  1. 链式存储方式的分析

    优点：在一定程度上对数组的存储方式有优化（比如：插入一个数值节点，只需要将插入节点，链接到链表中即可，删除效率也很好）

    缺点：在进行检索时，效率仍然比较低，比如（检索某个值，需要从头结点开始遍历）

  2. 树存储方式的分析

    优点：可以提高数据存储，读取的效率，比如利用二叉排序树，既可以保证数据的检索速度，同时也可以保证数据的插入，删除，修改的速度。

    缺点：顺序存储可能会浪费空间（在非完全二叉树的时候，但是读取某个特定的节点的时候效率比较高O(0)）;链式存储相对于二叉树，浪费空间较少，但是读取某个结点时效率偏低O(nlogn)。

10.2 二叉树的概率和常用术语

满二叉树：在一个二叉树中，如果所有分支节点都有左孩子节点和右孩子节点，并且叶节点都集中在二叉树中的最下一层，这样的二叉树被称为满二叉树。

完全二叉树：若二叉树中最多只有最下面两层的结点的度数可以小于2，并且最下面一层的叶子节点，都依次排列在该层最左边的位置上，这样的二叉树称为完全二叉树。

遍历和节点删除

二叉树是一种非常重要的数据结构，非常多的数据结构都是基于二叉树的基础演变而来的。对于二叉树有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义，因此采用递归的方法实现树的三种遍历。

  • 前序遍历：根结点 —>左子树—>右子树；
  • 中序遍历：左子树 —>根结点—>右子树；
  • 后续遍历：左子树 —>右子树—>根结点；
  • 层次遍历：仅仅需按成次遍历即可；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
public class BinaryTreeDemo {
	//定义一个自定义二叉树
	public static void main(String[] args) {
		//创建一个二叉树
		//创建一个二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建结点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "卢俊义");
        HeroNode node3 = new HeroNode(3, "吴用");
        HeroNode node4 = new HeroNode(4, "公孙胜");
        HeroNode node5 = new HeroNode(5, "关胜");
        root.setLeft(node2);
        root.setRight(node3);
        node3.setLeft(node4);
        node3.setRight(node5);
        binaryTree.setRoot(root);
        System.out.println("前序遍历");
        binaryTree.preOrder();
        System.out.println("中序遍历");
        binaryTree.midOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();
        binaryTree.delNode(3);
        System.out.println("删除结点3，前序遍历");
        binaryTree.preOrder();
	}
}
//定义BinaryTree 二叉树
class BinaryTree {
	private HeroNode root;

	public HeroNode getRoot() {
		return root;
	}

	public void setRoot(HeroNode root) {
		this.root = root;
	}
	//前序遍历
	public void preOrder() {
		if(this.root != null) {
			this.root.preOrder();
		}else {
			System.out.println("二叉树为空，不能遍历");
		}
	}
	//中序遍历
	public void midOrder() {
		if(this.root != null) {
			this.root.midOrder();
		}else {
			System.out.println("二叉树为空，无法遍历");
		}
	}
	//后序遍历
	public void postOrder() {
		if(this.root != null) {
			this.root.postOrder();
		}else {
			System.out.println("二叉树为空，无法遍历");
		}
	}

	//删除结点
	public void delNode(int no) {
		if(root != null) {
			//如果只有一个root结点, 这里立即判断root是不是就是要删除结点
			if(root.getNo() == no) {
				root = null;
			} else {
				//递归删除
				root.delNode(no);
			}
		}else{
			System.out.println("空树，不能删除~");
		}
	}
}

//先创建HeroNode 结点
class HeroNode {
	private int no;
	private String name;
	private HeroNode left; //默认null
	private HeroNode right; //默认null
	public HeroNode(int no, String name) {
		this.no = no;
		this.name = name;
	}
	public int getNo() {
		return no;
	}
	public void setNo(int no) {
		this.no = no;
	}
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public HeroNode getLeft() {
		return left;
	}
	public void setLeft(HeroNode left) {
		this.left = left;
	}
	public HeroNode getRight() {
		return right;
	}
	public void setRight(HeroNode right) {
		this.right = right;
	}
	@Override
	public String toString() {
		return "HeroNode [no=" + no + ", 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 midOrder() {
		//递归向左子树中序遍历
		if(this.left != null) {
			this.left.midOrder();
		}
		System.out.println(this);//输出父节点
		//递归向右子树前序遍历
		if(this.right != null) {
			this.right.midOrder();
		}
	}

	//后序遍历
	public void postOrder() {
		//递归向左子树后序遍历
		if(this.left != null) {
			this.left.postOrder();
		}
		//递归向右子树前序遍历
		if(this.right != null) {
			this.right.postOrder();
		}
		System.out.println(this);//输出父节点
	}

	//递归删除结点
	//1.如果删除的节点是叶子节点，则删除该节点
	//2.如果删除的节点是非叶子节点，则删除该子树
	public void delNode(int no) {
		//思路
		/*
		 * 	1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断当前这个结点是不是需要删除结点.
			2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
			3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
			4. 如果第2和第3步没有删除结点，那么我们就需要向左子树进行递归删除
			5.  如果第4步也没有删除结点，则应当向右子树进行递归删除.
		 */
		//2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将this.left = null; 并且就返回(结束递归删除)
		if(this.left != null && this.left.no == no) {
			this.left = null;
			return;
		}

		//3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将this.right= null ;并且就返回(结束递归删除)
		if(this.right != null && this.right.no == no) {
			this.right = null;
			return;
		}

		//4.我们就需要向左子树进行递归删除
		if(this.left != null) {
			this.left.delNode(no);
		}

		//5.则应当向右子树进行递归删除
		if(this.right != null) {
			this.right.delNode(no);
		}
	}
}

10.3链式存储

查找节点：先对树进行一次遍历，然后找出要找的那个数；因为有三种排序方法，所以查找节点也分为先序查找，中序查找，后序查找；

删除节点：由于链式存储，不能找到要删的数直接删除，需要找到他的父节点，然后将指向该数设置为null；所以需要一个变量来指向父节点，找到数后，再断开连接。

树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
public class BinaryTree {

    TreeNode root;

    //设置根节点
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //获取根节点
    public TreeNode getRoot() {
        return root;
    }

    //先序遍历
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍历
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //后序遍历
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查找
    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //删除一个子树
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }
}

  • 节点类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
public class TreeNode {
    //节点的权
    int value;
    //左儿子
    TreeNode leftNode;
    //右儿子
    TreeNode rightNode;

    public TreeNode(int value) {
        this.value = value;
    }

    //设置左儿子
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    //设置右儿子
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍历
    public void frontShow() {
        //先遍历当前节点的值
        System.out.print(value + " ");
        //左节点
        if (leftNode != null) {
            leftNode.frontShow(); //递归思想
        }
        //右节点
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍历
    public void middleShow() {
        //左节点
        if (leftNode != null) {
            leftNode.middleShow(); //递归思想
        }
        //先遍历当前节点的值
        System.out.print(value + " ");
        //右节点
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //后续遍历
    public void afterShow() {
        //左节点
        if (leftNode != null) {
            leftNode.afterShow(); //递归思想
        }
        //右节点
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍历当前节点的值
        System.out.print(value + " ");
    }

    //先序查找
    public TreeNode frontSearch(int i) {
        TreeNode target = null;
        //对比当前节点的值
        if (this.value == i) {
            return this;
            //当前节点不是要查找的节点
        } else {
            //查找左儿子
            if (leftNode != null) {
                //查找的话t赋值给target，查不到target还是null
                target = leftNode.frontSearch(i);
            }
            //如果target不为空，说明在左儿子中已经找到
            if (target != null) {
                return target;
            }
            //如果左儿子没有查到，再查找右儿子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //删除一个子树
    public void delete(int i) {
        TreeNode parent = this;
        //判断左儿子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判断右儿子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，递归检查并删除左儿子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //递归检查并删除右儿子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }

    }
}

测试

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public class Demo {
    public static void main(String[] args) {
        //创建一棵树
        BinaryTree binaryTree = new BinaryTree();
        //创建一个根节点
        TreeNode root = new TreeNode(1);
        //把根节点赋给树
        binaryTree.setRoot(root);
        //创建左,右节点
        TreeNode rootLeft = new TreeNode(2);
        TreeNode rootRight = new TreeNode(3);
        //把新建的节点设置为根节点的子节点
        root.setLeftNode(rootLeft);
        root.setRightNode(rootRight);
        //为第二层的左节点创建两个子节点
        rootLeft.setLeftNode(new TreeNode(4));
        rootLeft.setRightNode(new TreeNode(5));
        //为第二层的右节点创建两个子节点
        rootRight.setLeftNode(new TreeNode(6));
        rootRight.setRightNode(new TreeNode(7));

        //先序遍历
        binaryTree.frontShow(); //1 2 4 5 3 6 7
        System.out.println();
        //中序遍历
        binaryTree.middleShow(); //4 2 5 1 6 3 7
        System.out.println();
        //后序遍历
        binaryTree.afterShow(); //4 5 2 6 7 3 1
        System.out.println();

        //先序查找
        TreeNode result = binaryTree.frontSearch(5);
        System.out.println(result); //binarytree.TreeNode@1b6d3586

        //删除一个子树
        binaryTree.delete(2);
        binaryTree.frontShow(); //1 3 6 7 ，2和他的子节点被删除了
    }
}

10.4顺序存储的二叉树

概述：顺序存储使用数组的形式实现；由于非完全二叉树会导致数组中出现空缺，有的位置不能填上数字，所以顺序存储二叉树通常情况下只考虑完全二叉树

原理： 顺序存储在数组中是按照第一层第二层一次往下存储的，遍历方式也有先序遍历、中序遍历、后续遍历

性质：

  • 第n个元素的左子节点是：2*n+1；
  • 第n个元素的右子节点是：2*n+2；
  • 第n个元素的父节点是：（n-1)/2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
public class ArrayBinaryTree {

	public static void main(String[] args) {
			int[] data = {1,2,3,4,5,6,7};
			ArrayBinaryTree tree = new ArrayBinaryTree(data);
			//先序遍历
			tree.frontShow(); //1 2 4 5 3 6 7
	}

	int[] data;

	public ArrayBinaryTree(int[] data) {
		this.data = data;
	}

	//重载先序遍历方法，不用每次传参数了,保证每次从头开始
	public void frontShow() {
		frontShow(0);
	}

	//先序遍历
	public void frontShow(int index) {
		if (data == null || data.length == 0) {
			return;
		}
		//先遍历当前节点的内容
		System.out.print(data[index] + " ");
		//处理左子树：2*index+1
		if (2 * index + 1 < data.length) {
			frontShow(2 * index + 1);
		}
		//处理右子树：2*index+2
		if (2 * index + 2 < data.length) {
			frontShow(2 * index + 2);
		}
	}
}

10.5线索二叉树

为什么使用线索二叉树？

当用二叉链表作为二叉树的存储结构时，可以很方便的找到某个结点的左右孩子；但一般情况下，无法直接找到该结点在某种遍历序列中的前驱和后继结点

原理：n个结点的二叉链表中含有n+1(2n-(n-1)=n+1个空指针域。利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前驱和后继结点的指针。

例如：某个结点的左孩子为空，则将空的左孩子指针域改为指向其前驱；如果某个结点的右孩子为空，则将空的右孩子指针域改为指向其后继（这种附加的指针称为”线索”）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public class ThreadedBinaryTree {

    ThreadedNode root;
    //用于临时存储前驱节点
    ThreadedNode pre = null;
    
    //设置根节点
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }

    //中序线索化二叉树
    public void threadNodes() {
        threadNodes(root);
    }

    public void threadNodes(ThreadedNode node) {
        //当前节点如果为null，直接返回
        if (node == null) {
            return;
        }
        //处理左子树
        threadNodes(node.leftNode);

        //处理前驱节点
        if (node.leftNode == null) {
            //让当前节点的左指针指向前驱节点
            node.leftNode = pre;
            //改变当前节点左指针类型
            node.leftType = 1;
        }
        //处理前驱的右指针，如果前驱节点的右指针是null（没有右子树）
        if (pre != null && pre.rightNode == null) {
            //让前驱节点的右指针指向当前节点
            pre.rightNode = node;
            //改变前驱节点的右指针类型
            pre.rightType = 1;
        }

        //每处理一个节点，当前节点是下一个节点的前驱节点
        pre = node;

        //处理右子树
        threadNodes(node.rightNode);
    }

    //遍历线索二叉树
    public void threadIterate() {
        //用于临时存储当前遍历节点
        ThreadedNode node = root;
        while (node != null) {
            //循环找到最开始的节点
            while (node.leftType == 0) {
                node = node.leftNode;
            }
            //打印当前节点的值
            System.out.print(node.value + " ");
            //如果当前节点的右指针指向的是后继节点，可能后继节点还有后继节点
            while (node.rightType == 1) {
                node = node.rightNode;
                System.out.print(node.value + " ");
            }
            //替换遍历的节点
            node = node.rightNode;

        }
    }

    //获取根节点
    public ThreadedNode getRoot() {
        return root;
    }

    //先序遍历
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍历
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //后序遍历
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查找
    public ThreadedNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //删除一个子树
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
public class ThreadedNode {
    //节点的权
    int value;
    //左儿子
    ThreadedNode leftNode;
    //右儿子
    ThreadedNode rightNode;
    //标识指针类型,1表示指向上一个节点，0
    int leftType;
    int rightType;

    public ThreadedNode(int value) {
        this.value = value;
    }

    //设置左儿子
    public void setLeftNode(ThreadedNode leftNode) {
        this.leftNode = leftNode;
    }

    //设置右儿子
    public void setRightNode(ThreadedNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍历
    public void frontShow() {
        //先遍历当前节点的值
        System.out.print(value + " ");
        //左节点
        if (leftNode != null) {
            leftNode.frontShow(); //递归思想
        }
        //右节点
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍历
    public void middleShow() {
        //左节点
        if (leftNode != null) {
            leftNode.middleShow(); //递归思想
        }
        //先遍历当前节点的值
        System.out.print(value + " ");
        //右节点
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //后续遍历
    public void afterShow() {
        //左节点
        if (leftNode != null) {
            leftNode.afterShow(); //递归思想
        }
        //右节点
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍历当前节点的值
        System.out.print(value + " ");
    }

    //先序查找
    public ThreadedNode frontSearch(int i) {
        ThreadedNode target = null;
        //对比当前节点的值
        if (this.value == i) {
            return this;
            //当前节点不是要查找的节点
        } else {
            //查找左儿子
            if (leftNode != null) {
                //查找的话t赋值给target，查不到target还是null
                target = leftNode.frontSearch(i);
            }
            //如果target不为空，说明在左儿子中已经找到
            if (target != null) {
                return target;
            }
            //如果左儿子没有查到，再查找右儿子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //删除一个子树
    public void delete(int i) {
        ThreadedNode parent = this;
        //判断左儿子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判断右儿子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，递归检查并删除左儿子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //递归检查并删除右儿子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class Demo {
    public static void main(String[] args) {
        //创建一棵树
        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
        //创建一个根节点
        ThreadedNode root = new ThreadedNode(1);
        //把根节点赋给树
        binaryTree.setRoot(root);
        //创建左,右节点
        ThreadedNode rootLeft = new ThreadedNode(2);
        ThreadedNode rootRight = new ThreadedNode(3);
        //把新建的节点设置为根节点的子节点
        root.setLeftNode(rootLeft);
        root.setRightNode(rootRight);
        //为第二层的左节点创建两个子节点
        rootLeft.setLeftNode(new ThreadedNode(4));
        ThreadedNode fiveNode = new ThreadedNode(5);
        rootLeft.setRightNode(fiveNode);
        //为第二层的右节点创建两个子节点
        rootRight.setLeftNode(new ThreadedNode(6));
        rootRight.setRightNode(new ThreadedNode(7));

        //中序遍历
        binaryTree.middleShow(); //4 2 5 1 6 3 7
        System.out.println();
        //中序线索化二叉树
        binaryTree.threadNodes();
//        //获取5的后继节点
//        ThreadedNode afterFive = fiveNode.rightNode;
//        System.out.println(afterFive.value); //1
        binaryTree.threadIterate(); //4 2 5 1 6 3 7
    }
}

10.6二叉排序树

概述：二叉排序树（Binary Sort Tree）也叫二叉查找树或者是一颗空树，对于二叉树中的任何一个非叶子节点，要求左子节点比当前节点值小，右子节点比当前节点值大

特点：

  • 查找性能与插入删除性能都适中还不错
  • 中序遍历的结果刚好是从大到小

创建二叉排序树原理：其实就是不断地插入节点，然后进行比较。

删除节点

  • 删除叶子节点，只需要找到父节点，将父节点与他的连接断开即可
  • 删除有一个子节点的就需要将他的子节点换到他现在的位置
  • 删除有两个子节点的节点，需要使用他的前驱节点或者后继节点进行替换，就是左子树最右下方的数（最大的那个）或右子树最左边的树（最小的数）；即离节点值最接近的值；（还要注解要去判断这个值有没有右节点，有就要将右节点移上来）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
public class BinarySortTree {
    Node root;

    //添加节点
    public void add(Node node) {
        //如果是一颗空树
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //中序遍历
    public void middleShow() {
        if (root != null) {
            root.middleShow(root);
        }
    }

    //查找节点
    public Node search(int value) {
        if (root == null) {
            return null;
        }
        return root.search(value);
    }

    //查找父节点
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }
        return root.searchParent(value);
    }

    //删除节点
    public void delete(int value) {
        if (root == null) {
            return;
        } else {
            //找到这个节点
            Node target = search(value);
            //如果没有这个节点
            if (target == null) {
                return;
            }
            //找到他的父节点
            Node parent = searchParent(value);
            //要删除的节点是叶子节点
            if (target.left == null && target.left == null) {
                //要删除的节点是父节点的左子节点
                if (parent.left.value == value) {
                    parent.left = null;
                }
                //要删除的节点是父节点的右子节点
                else {
                    parent.right = null;
                }
            }
            //要删除的节点有两个子节点的情况
            else if (target.left != null && target.right != null) {
                //删除右子树中值最小的节点，并且获取到值
                int min = deletMin(target.right);
                //替换目标节点中的值
                target.value = min;
            }
            //要删除的节点有一个左子节点或右子节点
            else {
                //有左子节点
                if (target.left != null) {
                    //要删除的节点是父节点的左子节点
                    if (parent.left.value == value) {
                        parent.left = target.left;
                    }
                    //要删除的节点是父节点的右子节点
                    else {
                        parent.right = target.left;
                    }

                }
                //有右子节点
                else {
                    //要删除的节点是父节点的左子节点
                    if (parent.left.value == value) {
                        parent.left = target.right;
                    }
                    //要删除的节点是父节点的右子节点
                    else {
                        parent.right = target.right;
                    }
                }
            }
        }
    }

    //删除一棵树中最小的节点
    private int deletMin(Node node) {
        Node target = node;
        //递归向左找最小值
        while (target.left != null) {
            target = target.left;
        }
        //删除最小的节点
        delete(target.value);
        return target.value;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //向子树中添加节点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        /*判断传入的节点的值比当前紫薯的根节点的值大还是小*/
        //添加的节点比当前节点更小(传给左节点）
        if (node.value < this.value) {
            //如果左节点为空
            if (this.left == null) {
                this.left = node;

            }
            //如果不为空
            else {
                this.left.add(node);
            }

        }
        //添加的节点比当前节点更大(传给右节点）
        else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    //中序遍历二叉排序树，结果刚好是从小到大
    public void middleShow(Node node) {
        if (node == null) {
            return;
        }
        middleShow(node.left);
        System.out.print(node.value + " ");
        middleShow(node.right);
    }

    //查找节点
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.value > value && this.left != null) {
                return this.left.searchParent(value);
            } else if (this.value < value && this.right != null) {
                return this.right.searchParent(value);
            }
            return null;
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public class Demo {
    public static void main(String[] args) {
        int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        //创建一颗二叉排序树
        BinarySortTree bst = new BinarySortTree();
        //循环添加
/*        for(int i=0;i< arr.length;i++) {
            bst.add(new Node(arr[i]));
        }*/
        for (int i : arr) {
            bst.add(new Node(i));
        }

        //中序遍历
        bst.middleShow(); //1 3 4 6 7 8 10 13 14
        System.out.println();

        //查找节点
        Node node = bst.search(10);
        System.out.println(node.value);//10

        Node node2 = bst.search(20);
        System.out.println(node2); //null

        //查找父节点
        Node node3 = bst.searchParent(1);
        Node node4 = bst.searchParent(14);
        System.out.println(node3.value); //3
        System.out.println(node4.value); //10

        //删除叶子节点
//        bst.delete(13);
//        bst.middleShow(); //1 3 4 6 7 8 10 14
//        System.out.println();
//        //删除只有一个子节点的节点
//        bst.delete(10);
//        bst.middleShow(); //1 3 4 6 7 8 ；10和14都没了

        //删除有两个子节点的节点
        bst.delete(3);
        bst.middleShow(); //1 4 6 7 8 10 13 14
    }
}

10.7平衡二叉树

平衡二叉树（Balanced Binary Tree）又被称为AVL树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这个方案很好的解决了二叉查找树退化成链表的问题，把插入，查找，删除的时间复杂度最好情况和最坏情况都维持在O(logN)。但是频繁旋转会使插入和删除牺牲掉O(logN)左右的时间，不过相对二叉查找树来说，时间上稳定了很多。

平衡因子 BF

  • 定义：左子树和右子树高度差
  • 计算：左子树高度 - 右子树高度的值
  • 别名：简称 BF（Balance Factor）
  • 一般来说 BF 的绝对值大于 1，,平衡树二叉树就失衡，需要旋转纠正

最小不平衡子树

  • 距离插入节点最近的，并且 BF 的绝对值大于 1 的节点为根节点的子树。
  • 旋转纠正只需要纠正最小不平衡子树即可

旋转方式

2 种旋转方式:

左旋 :

  • 旧根节点为新根节点的左子树
  • 新根节点的左子树（如果存在）为旧根节点的右子树

右旋：

  • 旧根节点为新根节点的右子树
  • 新根节点的右子树（如果存在）为旧根节点的左子树

4 种旋转纠正类型：

  • 左左型：插入左孩子的左子树，右旋
  • 右右型：插入右孩子的右子树，左旋
  • 左右型：插入左孩子的右子树，先左旋，再右旋
  • 右左型：插入右孩子的左子树，先右旋，再左旋
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //获取当前节点高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    //获取左子树高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    //获取右子树高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }


    //向子树中添加节点
    public void add(Node node) {
        if (node == null) {
            return;
        }
        /*判断传入的节点的值比当前紫薯的根节点的值大还是小*/
        //添加的节点比当前节点更小(传给左节点）
        if (node.value < this.value) {
            //如果左节点为空
            if (this.left == null) {
                this.left = node;

            }
            //如果不为空
            else {
                this.left.add(node);
            }

        }
        //添加的节点比当前节点更大(传给右节点）
        else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        //查询是否平衡
        //右旋转
        if (leftHeight() - rightHeight() >= 2) {
            //双旋转，当左子树左边高度小于左子树右边高度时
            if (left != null && left.leftHeight() < left.rightHeight()) {
                //左子树先进行左旋转
                left.leftRotate();
                //整体进行右旋转
                rightRotate();
            }
            //单旋转
            else {
                rightRotate();
            }
        }
        //左旋转
        if (leftHeight() - rightHeight() <= -2) {
            //双旋转
            if (right != null && right.rightHeight() < right.leftHeight()) {
                right.rightRotate();
                leftRotate();
            }
            //单旋转
            else {
                leftRotate();
            }
        }
    }

    //右旋转
    private void rightRotate() {
        //创建一个新的节点，值等于当前节点的值
        Node newRight = new Node(value);
        //把新节点的右子树设置为当前节点的右子树
        newRight.right = right;
        //把新节点的左子树设置为当前节点的左子树的右子树
        newRight.left = left.right;
        //把当前节点的值换位左子节点的值
        value = left.value;
        //把当前节点的左子树设置为左子树的左子树
        left = left.left;
        //把当前节点设置为新节点
        right = newRight;
    }

    //左旋转
    private void leftRotate() {
        //创建一个新的节点，值等于当前节点的值
        Node newLeft = new Node(value);
        //把新节点的左子树设置为当前节点的左子树
        newLeft.left = left;
        //把新节点的右子树设置为当前节点的右子树的左子树
        newLeft.right = right.left;
        //把当前节点的值换位右子节点的值
        value = right.value;
        //把当前节点的右子树设置为右子树的右子树
        right = right.right;
        //把当前节点设置为新节点
        left = newLeft;
    }

    //中序遍历二叉排序树，结果刚好是从小到大
    public void middleShow(Node node) {
        if (node == null) {
            return;
        }
        middleShow(node.left);
        System.out.print(node.value + " ");
        middleShow(node.right);
    }

    //查找节点
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    //查找父节点
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.value > value && this.left != null) {
                return this.left.searchParent(value);
            } else if (this.value < value && this.right != null) {
                return this.right.searchParent(value);
            }
            return null;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        //创建一颗二叉排序树
        BinarySortTree bst = new BinarySortTree();
        //循环添加
        for (int i : arr) {
            bst.add(new Node(i));
        }
        //查看高度
        System.out.println(bst.root.height()); //3
        //查看节点值
        System.out.println(bst.root.value); //根节点为4
        System.out.println(bst.root.left.value); //左子节点为2
        System.out.println(bst.root.right.value); //右子节点为5
    }
}