uni_shiki

算法与数据结构_5_二叉树

  • 2023-03-22
  • 作者 uni_shiki
  • ~8.62K 字
  1. 1. 二叉树
  2. 2. 二叉树的相关概念及其实现判断

 

二叉树

  • 二叉树节点结构
    • 一个值类型
    • 一个指向左孩子的指针
    • 一个指向右孩子的指针
  • 左孩子、右孩子都为空的叫做叶节点
  • 最顶的节点叫做根节点或头节点
1
2
3
4
5
6
class Node<V>
{
	V value;
	Node left;
	Node right;
}
  • 二叉树的遍历，最简单是递归
1
2
3
4
5
6
7
8
9
10
11
12
public static void f(Node head)
{
	if (head == null)
	{
		return;
	}
	// 1
	f(head.left);
	// 2
	f(head.right);
	// 3
}
  • 先序 (头左右) : 递归序中第一次遇到该节点
  • 中序 (左头右) : 递归序中第二次遇到该节点
  • 后序 (左右头) : 递归序中第三次遇到该节点
  • 非递归先序
  • 流程 :
    • 准备一个栈，先把头节点放进去
    • 每次 :
        1. 从栈中弹出一个节点cur
        1. 打印(处理)cur
        1. 先右再左(如果有)
        1. 周而复始
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void preOrderUnRecur(Node head)
{
	System.out.print("pre-order: ");
	if (head != null)
	{
		Stack<Node> stack = new Stack<Node>();
		stack.add(head);
		while (!stack.isEmpty())
		{
			head = stack.pop();
			System.out.print(head.value + " ");
			if (head.right != null)
			{
				stack.push(head.right);
			}
			if (head.left != null)
			{
				stack.push(head.left);
			}
		}
	}
	System.out.println();
}
  • 非递归后序
  • 流程 :
    • 准备一个栈，先把头节点放进去，再准备一个收集栈
    • 每次 :
      • 弹当前节点cur
      • cur放入收集栈，弹一个放一个
      • 先压左再右
      • 周而复始
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
public static void posOrderUnRecur1(Node head)
{
	System.out.print("pos-order: ");
	if (head != null)
	{
		Stack<Node> s1 = new Stack<Node>();
		Stack<Node> s2 = new Stack<Node>();
		s1.push(head);
		while (!s1.isEmpty())
		{
			head = s1.pop();
			s2.push(head);
			if (head.left != null)
			{
				s1.push(head.left);
			}
			if (head.left != null)
			{
				s1.push(head.left);
			}
		}
		while (!s2.isEmpty())
		{
			System.out.print(s2.pop().value + " ");
		}
	}
	System.out.println();
}
  • 非递归中序
  • 流程 :
    • 每颗子树，整棵树左边界进栈，依次弹的过程中，打印，对弹出节点的右树重复
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static void inOrderUnRecur(Node head)
{
	System.out.print("in-order: ");
	if (head != null)
	{
		Stack<Node>() stack = new Stack<Node>();
		while (!stack.isEmpty() || head != null)
		{
			if (head != null)
			{
				stack.push(head);
				head = head.left;
			}
			else
			{
				head = stack.pop();
				System.out.print(head.value + " ");
				head = head.right;
			}
		}
	}
	System.out.println();
}

如何直观打印一颗二叉树

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
public static class Node
{
	public int value;
	public Node left;
	public Node right;

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

public static void printTree(Node head)
{
	System.out.println("Binary Tree:");
	printInOrder(head, 0, "H", 17);
	System.out.println();
}

public static void printInOrder(Node head, int height, String to, int len)
{
	if (head == null)
	{
		return;
	}
	printInOrder(head.right, height + 1, "v", len);
	String val = to + head.value + to;
	int lenM = val.length();
	int lenL = (len - lenM) / 2;
	int lenR = len - lenM - lenL;
	val = getSpace(lenL) + val + getSpace(lenR);
	System.out.println(getSpace(height * len) + val);
	printInOrder(head.left, height + 1, "^", len);
}

public static String getSpace(int num)
{
	String space = " ";
	StringBuffer buf = new StringBuffer("");
	for (int i = 0; i < num; i++)
	{
		buf.append(space);
	}
	return buf.toString();
}

public static void main(String[] args)
{
	Node head = new Node(1);
	head.left = new Node(-222222222);
	head.right = new Node(3);
	head.left.left = new Node(Integer.MIN_VALUE);
	head.right.left = new Node(555555);
	head.right.right = new Node(66);
	head.left.left.right = new Node(777);
	printTree(head);
}

如何完成二叉树的宽度优先遍历

  • 宽度遍历(层序遍历)用队列，头部进尾部出，先进先出，先放左孩子再放右孩子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static void w(Node head)
{
	if (head == null)
	{
		return;
	}
	Queue<Node> queue = new LinkedList<>();
	queue.add(head);
	while (!queue.isEmpty())
	{
		Node cur = queue.poll();
		System.out.println(cur.value);
		if (cur.left != null)
		{
			queue.add(cur.left);
		}
		if (cur.right != null)
		{
			queue.add(cur.right);
		}
	}
}

常见题目 : 求一棵二叉树的最大宽度

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 static int w(Node head)
{
	if (head == null)
	{
		return;
	}
	Queue<Node> queue = new LinkedList<>();
	queue.add(head);

	HashMap<Node, Integer> levelMap = new HashMap<>();
	levelMap.put(head, 1);
	int curLevel = 1;
	int curLevelNodes = 0;
	int max = Integer.MIN_VALUE;

	while (!queue.isEmpty())
	{
		Node cur = queue.poll();

		int curNodeLevel = levelMap.get(cur);
		if (curNodeLevel == curLevel)
		{
			curLevelNodes++;
		}
		else
		{
			max = Math.max(max, curLevelNodes);
			curLevel++;
			curLevelNodes = 1;
		}

		if (cur.left != null)
		{
			levelMap.put(cur.left, curNodeLevel + 1);
			queue.add(cur.left);
		}
		if (cur.right != null)
		{
			levelMap.put(cur.right, curNodeLevel + 1);
			queue.add(cur.right);
		}
	}
	return max;
}

二叉树的相关概念及其实现判断

如何判断一颗二叉树是否是搜索二叉树

  • 搜索二叉树 :
    对于每一颗子树来说，都满足 : 左数的节点都比它小，右树的节点都比它大(没有重复值)
  • 中序遍历

如何判断一颗二叉树是否是完全二叉树

  • 完全二叉树 :
    每层是满的，最后一层即使不满，也是从左往右变满的情况
  • 判断条件 :
    • 1)任一节点，有右无左返回false
    • 在1)不违规的条件下，如果遇到了第一个左右孩子不双全的情况下，那么接下来遇到的节点都为叶节点，否则返回false

如何判断一颗二叉树是否是满二叉树

  • 麻烦做法 :
    先求最大深度L，再求节点个数N，满足深度N = 2^L - 1

如何判断一颗二叉树是否是平衡二叉树

  • 平衡二叉树 :
    对于任何一颗子树来说，左树与右树的高度差不超过1
    递归套路，返回两个信息，是否平衡和高度

  • 树型DP的题，用递归套路，在可以向左右树索取信息的想法下

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
// 返回值类型
public static class Info()
{
	public int height;
	public int nodes;

	public Info(int h, int n)
	{
		height = h;
		nodes = n;
	}
}
// 递归函数
public static Info process(Node x)
{
	if (x == null)
	{
		return new Info(0, 0);
	}

	Info leftData = process(x.left);
	Info rightData = process(x.right);
	int height = Math.max(leftData.height, rightData.height) + 1;
	int nodes = leftData.nodes + rightData.nodes + 1;

	return new Info(height, nodes);
}

public static boolean isF(Node head)  // 主函数
{
	if (head == null)
	{
		return true;
	}
	Info data = process(head);
	return data.nodes == (1 << data.height - 1)  // 1 << n : 2的n次方
}

题目 : 给定两个二叉树的节点node1和node2，找到它们的最低公共祖先节点(首个汇聚的点)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static Node lowestAncestor(Node head, Node o1, Node o2)
{
	if (head == null || head == o1 || head == o2)
	{
		return head;
	}
	Node left = lowestAncestor(head.left, o1, o2);
	Node right = lowestAncestor(head.right, o1, o2);

	if (left != null && right != null)
	{
		return head;
	}
	// 左右并不都为null，返回不为null的那个
	return left != null ? left : right;
}

在二叉树中找到一个节点的后继节点

  • 后继节点 :
    中序遍历中，一个节点的下一个节点
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
public static Node getSuccessorNode(Node node)
{
	if (node == null)
	{
		return node;
	}
	if (node.right != null)
	{
		return getLeftMost(node.right);
	}
	else // 无右子树
	{
		Node parent = node.parent;
		while (parent != null && parent.left != null) // 当前节点是其父节点的右孩子
		{
			node = parent;
			parent = node.parent;
		}
		return parent;
	}
}

public static Node getLeftMost(Node node)
{
	if (node == null)
		return node;
	while (node.left != null)
	{
		node = node.left;
	}
	return node;
}

二叉树的序列化和反序列化
就是内存里的一颗树如何变成字符串形式

  • 做法 :
    先序遍历，数值直接写，值的结束用下划线_，遇到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
// 以head为头的树，请先序列化成字符串返回
public static String serialByPre(Node head)
{
	if (head == null)
		return "#_";
	String res = head.value + "_";
	res += serialByPre(head.left);
	res += serialByPre(head.right);
	return res;
}
// 反序列化
public static Node reconByPreString(String preStr)
{
	String[] values = preStr.split("_");
	Queue<String> queue = new LinkedList<String>();
	for (int i = 0; i != values.length; i++)
	{
		queue.add(values[i]);
	}
	return reconPreOrder(queue);
}

public static Node reconPreOrder(Queue<String> queue)
{
	String value = queue.poll();
	if (value.equals("#"))
	{
		return null;
	}
	Node head = new Node(Integer.valueOf(value));
	head.left = reconPreOrder(queue);
	head.right = reconPreOrder(queue);
	return head;
}

题目 : 对折一张纸n次打开，请打印出折痕凹凸情况
规律 :

  • 每次对折后，在上一次的每个折痕的上下都会出现一个新的折痕，上面的是凹折痕，下面的是凸折痕
  • 这是一颗头节点为凹折痕，每一棵左子树都是凹折痕，每一颗右子树都是凸折痕的满二叉树
1
2
3
4
5
6
7
8
9
// i是节点的层数，N一共的层数，down == true 凹 down == false 凸
public static void printProcess(int i, int N, boolean down)
{
	if (i > N) // 超过深度直接返回
		return;
	printProcess(i + 1, N, true);
	System.out.println(down ? "凹" : "凸");
	printProcess(i + 1, N, false);
}
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
最后编辑：2024-03-26