当前位置:网站首页>Summary of common algorithms of binary tree

Summary of common algorithms of binary tree

2020-11-06 01:18:19 Clamhub's blog

Node definition

1
2
3
4
5
6
7
8
9
10
11
12
13
public static class BinaryNode<T> {
T element;
BinaryNode<T> left;
BinaryNode<T> right;
BinaryNode(T theElement) {
this(theElement, null, null);
}
BinaryNode(T theElement, BinaryNode<T> lt, BinaryNode<T> rt) {
element = theElement;
left = lt;
right = rt;
}
}

Binary tree nodes include element values and left and right child node references .

Create nodes

1
2
3
4
5
6
7
BinaryNode g = new BinaryNode(7);
BinaryNode f = new BinaryNode(6);
BinaryNode e = new BinaryNode(5);
BinaryNode d = new BinaryNode(4);
BinaryNode c = new BinaryNode(3, f, g);
BinaryNode b = new BinaryNode(2, d, e);
BinaryNode a = new BinaryNode(1, b, c);

Form like :
 Binary tree .jpg

1、 front 、 in 、 After the sequence traversal

In front of the binary tree 、 in 、 Before in postorder traversal 、 in 、 The root node ;
Before the order : Output the root node first , And then the left and right nodes .
Middle preface : First left , Then output the root node , To the right .
In the following order : First left and right , Then output the root node .

1
2
3
public static void visit(BinaryNode p) {
System.out.print(p.element + " ");
}

1.1、 The former sequence traversal

1
2
 root -> Left -> Right 
1 2 4 5 3 6 7
1.1.1、 Recursive implementation
1
2
3
4
5
6
 public static void recursivePreOrder(BinaryNode p) {
if (p == null) return;
visit(p);
recursivePreOrder(p.left);
recursivePreOrder(p.right);
}

If the node is null, Go straight back to ;
Print out the root node first , Then recursion left subtree , Then recurs the right subtree .
Just meet : First root , And then around .

1.1.2、 Non recursive implementation
1
2
3
4
5
6
7
8
9
10
11
public static void iterativePreOrder(BinaryNode p) {
if (p == null) return;
Stack<BinaryNode> stack = new Stack<>();
stack.push(p);
while (!stack.empty()) {
p = stack.pop();
visit(p);
if (p.right != null) stack.push(p.right);
if (p.left != null) stack.push(p.left);
}
}

Make full use of the idea of stack , First in, then out .
When the node is not empty , Putting nodes on the stack , Iterate the elements in the stack , Pop up top element , Currently the root element , After that, press the right and left child nodes on the stack respectively . In this way, the order of the child nodes is left first and then right .

1.2、 In the sequence traversal

1
2
 Left -> root -> Right 
4 2 5 1 6 3 7
1.2.1、 Recursive implementation
1
2
3
4
5
6
public static void recursiveInOrder(BinaryNode p) {
if (p == null) return;
recursiveInOrder(p.left);
visit(p);
recursiveInOrder(p.right);
}
1.2.2、 Non recursive implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
public static void iterativeInOrder(BinaryNode p) {
if (p == null) return;
Stack<BinaryNode> stack = new Stack<>();
while (!stack.empty() || p != null) {
while (p != null) {
stack.push(p);
p = p.left;
}
p = stack.pop();
visit(p);
p = p.right;
}
}

1.3、 After the sequence traversal

1
2
 Left -> Right -> root 
4 5 2 6 7 3 1
1.3.1、 Recursive implementation
1
2
3
4
5
6
public static void recursivePostOrder(BinaryNode p) {
if (p == null) return;
recursivePostOrder(p.left);
recursivePostOrder(p.right);
visit(p);
}
1.3.2、 Non recursive implementation
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void iterativePostOrder(BinaryNode p) {
if (p == null) return;
Stack<BinaryNode> stack = new Stack<>();
Stack<BinaryNode> result = new Stack<>();
while (!stack.empty() || p != null) {
while (p != null) {
stack.push(p);
result.push(p);
p = p.right;
}
if (!stack.empty()) p = stack.pop().left;
}
while (!result.empty()) {
p = result.pop();
visit(p);
}
}

2、BFS And DFS

1
1234567

Breadth first traversal is to read node elements by layer , We need to use the data structure of the queue .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void levelOrderTraversal(BinaryNode node) {
if (node == null) {
System.out.print("empty tree");
return;
}
LinkedList<BinaryNode> queue = new LinkedList<>();
queue.add(node);
while (!queue.isEmpty()) {
BinaryNode binaryNode = queue.pollFirst();
System.out.print(binaryNode.element + " ");
if (binaryNode.left != null) {
queue.add(binaryNode.left);
}
if (binaryNode.right != null) {
queue.add(binaryNode.right);
}
}
}
1
1245367

Starting from the root node , Select a branch to read all the elements , We need to use the data structure of the stack .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public static void depthTraversal(BinaryNode node) {
if (node == null) {
System.out.print("empty tree");
return;
}
LinkedList<BinaryNode> stack = new LinkedList<>();
stack.push(node);
while (!stack.isEmpty()) {
BinaryNode binaryNode = stack.pop();
System.out.print(binaryNode.element);
if (binaryNode.right != null) {
stack.push(binaryNode.right);
}
if (binaryNode.left != null) {
stack.push(binaryNode.left);
}
}
}

3、 The depth of the binary tree

104. The maximum depth of a binary tree

3.1、 recursive

1
2
3
4
5
6
7
8
9
10
private static int calcDepth(BinaryNode node) {
if (node == null) return 0;
int ld = calcDepth(node.left);
int rd = calcDepth(node.right);
if (ld > rd) {
return ld + 1;
} else {
return rd + 1;
}
}

3.2、 Depth first

maxDepth Compare the length of each branch to update , Finally get the deepest branch length .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public static int maxDepthDFS(BinaryNode node) {
if (node == null) return 0;
LinkedList<BinaryNode> stack = new LinkedList<>();
LinkedList<Integer> value = new LinkedList<>();
stack.push(node);
value.push(1);
int maxDepth = 0;
while (!stack.isEmpty()) {
BinaryNode binaryNode = stack.pop();
int temp = value.pop();
maxDepth = Math.max(temp, maxDepth);
if (binaryNode.right != null) {
stack.push(binaryNode.right);
value.push(temp + 1);
}
if (binaryNode.left != null) {
stack.push(binaryNode.left);
value.push(temp + 1);
}
}
return maxDepth;
}

3.3、 breadth-first

Search by layer , Every step into the floor , depth +1.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int maxDepthBFS(BinaryNode node) {
if (node == null) return 0;
LinkedList<BinaryNode> queue = new LinkedList<>();
queue.add(node);
int maxDepth = 0;
while (!queue.isEmpty()) {
maxDepth++;
BinaryNode binaryNode = queue.pollFirst();
if (binaryNode.left != null) {
queue.add(binaryNode.left);
}
if (binaryNode.right != null) {
queue.add(binaryNode.right);
}
}
return maxDepth;
}

4、 Binary tree image

Traverse by depth or breadth , Swap the left and right subtrees of nodes .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void mirror(BinaryNode root) {
if (root == null) return;
LinkedList<BinaryNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()) {
BinaryNode node = stack.pop();
BinaryNode temp = node.left;
node.left = node.right;
node.right = temp;
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}

5、 Symmetric binary tree

101. Symmetric binary tree
This problem is a variation of binary tree mirror image , If two binary trees are symmetric , be :

  1. Two root nodes have the same value
  2. The left subtree of each tree , Are the same as the right subtree of another tree
    Recursive implementation :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    public boolean isSymmetric(BinaryNode root) {
    return isMirror(root, root);
    }

    public boolean isMirror(BinaryNode t1, BinaryNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val)
    && isMirror(t1.right, t2.left)
    && isMirror(t1.left, t2.right);
    }
    Iterative implementation :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    public boolean isSymmetric(BinaryNode root) {
    LinkedList<BinaryNode> q = new LinkedList<>();
    q.add(root);
    q.add(root);
    while (!q.isEmpty()) {
    BinaryNode t1 = q.poll();
    BinaryNode t2 = q.poll();
    if (t1 == null && t2 == null) continue;
    if (t1 == null || t2 == null) return false;
    if (t1.val != t2.val) return false;
    q.add(t1.left);
    q.add(t2.right);
    q.add(t1.right);
    q.add(t2.left);
    }
    return true;
    }

summary

The algorithm of various topics of binary tree will think of recursion in the first consciousness , But when the recursion depth is too large, there will be stack overflow , So iterations will be used to implement accordingly , Accordingly, the data structure of queue or stack is introduced .
It feels like the most important algorithm is DFS And BFS, among DFS Depth first search uses the FIFO feature of the stack , and BFS Breadth first search uses the first in first out feature of the queue .

tencent.jpg

版权声明
本文为[Clamhub's blog]所创,转载请带上原文链接,感谢

随机推荐