L
L
LearnJava
Search…
二叉树
本文讲解二叉树的基本操作:
  • 查找节点
  • 计算树的高度
  • 清空树
  • 递归遍历:先序遍历、中序遍历、后序遍历
  • 按层遍历
  • 前序、中序的非递归遍历
  • 树的路径
  • 树的左旋和右旋
来看一下树的结构:
1
class TreeNode {
2
String value;
3
TreeNode left;
4
TreeNode right;
5
public TreeNode() {
6
7
}
8
public TreeNode(String value) {
9
this.value = value;
10
}
11
}
Copied!
首先,为了方便后面看到效果,先手动初始化一个有4个节点的二叉树:
1
Tree tree = new Tree();
2
TreeNode root = new TreeNode("root");
3
TreeNode node1 = new TreeNode("ndoe1");
4
TreeNode node2 = new TreeNode("ndoe2");
5
TreeNode node3 = new TreeNode("ndoe3");
6
root.left = node1;
7
root.right = node2;
8
node1.left = node3;
Copied!

一、查找节点

1
//查找节点
2
public TreeNode findNode(TreeNode treeNode, String value) {
3
if(null == treeNode)
4
return null;
5
6
if(treeNode.value.equals(value))
7
return treeNode;
8
9
TreeNode leftNode = findNode(treeNode.left, value);//递归左子树
10
TreeNode rightNode = findNode(treeNode.right, value);//递归右子树
11
if(leftNode.value.equals(value))
12
return leftNode;
13
if(rightNode.value.equals(value))
14
return rightNode;
15
16
return null;
17
}
Copied!

二、计算树的深度

1
//计算树的深度
2
//递归方法
3
public int deepth(TreeNode treeNode) {
4
if(treeNode == null)
5
return 0;
6
int left = deepth(treeNode.left);
7
int right = deepth(treeNode.right);
8
return left > right? left + 1: right + 1;
9
}
Copied!

三、清空树

1
//清空二叉树
2
public void clearTreeNode(TreeNode treeNode) {
3
if(null != treeNode) {
4
clearTreeNode(treeNode.left);
5
clearTreeNode(treeNode.right);
6
treeNode = null;
7
}
8
}
Copied!

四、递归遍历

1
//遍历1 先序遍历
2
public void showDLR(TreeNode treeNode) {
3
if(null != treeNode) {
4
showData(treeNode);
5
showDLR(treeNode.left);
6
showDLR(treeNode.right);
7
}
8
}
9
//遍历2 中序遍历
10
public void showLDR(TreeNode treeNode) {
11
if(null != treeNode) {
12
showLDR(treeNode.left);
13
showData(treeNode);
14
showLDR(treeNode.right);
15
}
16
}
17
//遍历3 后序遍历
18
public void showLRD(TreeNode treeNode) {
19
if(null != treeNode) {
20
showLRD(treeNode.left);
21
showLRD(treeNode.right);
22
showData(treeNode);
23
}
24
}
Copied!

五、按层遍历

1
//遍历4 按层遍历 借助队列 先进先出
2
public void showByLevel(TreeNode treeNode) {
3
if(null == treeNode)
4
return;
5
6
LinkedList<TreeNode> list = new LinkedList<>();
7
TreeNode current;
8
list.offer(treeNode);//将根节点入队
9
10
while(!list.isEmpty()) {
11
current = list.poll();//队首出队
12
showData(current);//打印节点
13
if(null != current.left) {
14
list.offer(current.left);
15
}
16
if(null != current.right) {
17
list.offer(current.right);
18
}
19
}
20
}
Copied!
运行结果:
1
树的深度是:3
2
先序遍历:
3
root-->ndoe1-->ndoe3-->ndoe2-->
4
中序遍历:
5
ndoe3-->ndoe1-->root-->ndoe2-->
6
后序遍历:
7
ndoe3-->ndoe1-->ndoe2-->root-->
8
按层遍历
9
root-->ndoe1-->ndoe2-->ndoe3-->
Copied!

六、先序,中序遍历的非递归实现

1
//遍历5 前序遍历的非递归实现
2
public void showDLRNotRecursion(TreeNode treeNode) {
3
Stack<TreeNode> stack = new Stack<>();
4
TreeNode node = treeNode;
5
while(null != node || stack.size() >0) {
6
while(null != node) {
7
showData(node);
8
stack.push(node);
9
node = node.left;
10
}
11
if(stack.size() > 0) {
12
node = stack.pop();
13
node = node.right;
14
}
15
}
16
}
17
//遍历6 中序遍历的非递归实现
18
public void showLDRNotRecursion(TreeNode treeNode) {
19
Stack<TreeNode> stack = new Stack<>();
20
TreeNode node = treeNode;
21
while(null != node || stack.size() > 0) {
22
while(null != node) {
23
stack.push(node);
24
node = node.left;
25
}
26
if(stack.size() > 0) {
27
node = stack.pop();
28
showData(node);
29
node = node.right;
30
}
31
}
32
}
Copied!

七、树的路径

1
public static void main(String[] args) {
2
TreeNode node1 = new TreeNode("1");
3
TreeNode node2 = new TreeNode("2");
4
TreeNode node3 = new TreeNode("3");
5
TreeNode node4 = new TreeNode("4");
6
TreeNode node5 = new TreeNode("5");
7
TreeNode node6 = new TreeNode("6");
8
TreeNode node7 = new TreeNode("7");
9
node1.left = node2;
10
node1.right = node3;
11
node2.left = node4;
12
node2.right = node5;
13
node5.left = node6;
14
node5.right = node7;
15
16
List<TreeNode> list = new ArrayList<>();
17
list.add(node1);
18
lujing(list, node1);
19
}
20
// 打印二叉树的所有路径
21
public static void lujing(List<TreeNode> list, TreeNode node) {
22
if (node.left == null && node.right == null) {
23
for (int i = 0; i < list.size(); i++) {
24
System.out.print(list.get(i).val + " --> ");
25
}
26
System.out.println();
27
return;
28
}
29
30
if (node.left != null) {
31
List<TreeNode> newList = new ArrayList<>(list);
32
newList.add(node.left);
33
lujing(newList, node.left);
34
}
35
36
if (node.right != null) {
37
List<TreeNode> newList = new ArrayList<>(list);
38
newList.add(node.right);
39
lujing(newList, node.right);
40
}
41
}
Copied!

八、二叉树的左旋和右旋

  • 左旋:节点右儿子的左儿子(若存在)变为节点的右儿子,节点变为右儿子的左儿子;
  • 右旋:节点左二子的右儿子(若存在)变为节点的左二子,节点变为左二子的右儿子。
举个例子:
可以看到,如果旋转前是一个二叉排序树,那么旋转后仍然是一个二叉排序树。
1
// 左旋
2
public static void zuoxuan(TreeNode head) {
3
TreeNode headRight = head.right;
4
head.right = headRight.left;
5
headRight.left = head;
6
}
7
8
// 右旋
9
public static void youxuan(TreeNode head) {
10
TreeNode headLeft = head.left;
11
head.left = headLeft.right;
12
headLeft.right = head;
13
}
Copied!
Last modified 1yr ago