二叉树的创建与遍历

发表于 更新于 分类于 本文字数： 4.1k 阅读时长 ≈ 4 分钟

二叉树创建

创建根据数组，值为0代表空节点

1
2
3
4
5
6
7
8
9
10
private static Node createTree(int[] data, int index) {
	if (index >= data.length || data[index] == 0) {
		return null;
	}
	Node node = new Node();
	node.setValue(data[index]);
	node.setLeftChild(createTree(data, 2 * index + 1));
	node.setRightChild(createTree(data, 2 * index + 2));
	return node;
}

createTree是创建以index索引代表节点为root的树，所以我们首先创建节点赋上对应值，然后设置左右子树，通过递归，最后得到二叉树。

二叉树的深度优先遍历的递归算法

深度优先遍历还分为先序、中序、后序。以先序为例，先序就是先访问根节点，再先序遍历左子树，然后先序遍历右子树，很明显可以递归完成。

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
/**
 * 先序
 * @param root
 */
private static void preOrder(Node root) {
	if (root != null) {
		System.out.println(root.getValue() + "");
		preOrder(root.getLeftChild());
		preOrder(root.getRightChild());
	}
}

/**
 * 中序
 * @param root
 */
private static void inOrder(Node root) {
	if (root != null) {
		preOrder(root.getLeftChild());
		System.out.println(root.getValue() + "");
		preOrder(root.getRightChild());
	}
}

/**
 * 后序 
 * @param root
 */
private static void postOrder(Node root) {
	if (root != null) {
		preOrder(root.getLeftChild());
		preOrder(root.getRightChild());
		System.out.println(root.getValue() + "");
	}
}

二叉树的深度优先遍历的非递归算法

先序

非递归方法我们使用栈来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * 先序非递归
 * @param node
 */
private static void pre(Node node) {
	if (node == null) {
		return;
	}
	ArrayDeque<Node> stack = new ArrayDeque<>();
	stack.push(node);
	while (!stack.isEmpty()) {
		Node n = stack.pop();
		System.out.println(n.getValue() + "");
		if (n.getRightChild() != null) {
			stack.push(n.getRightChild());
		}
		if (n.getLeftChild() != null) {
			stack.push(n.getLeftChild());
		}
	}
}

首先root入栈，然后循环访问栈顶元素并出栈，接下来将左右子节点入栈，入栈顺序要是先右后左。

后序

通过观察可以发现将后序的结果反过来就相当于将二叉树所有左右子树互换后的先序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * 后序非递归
 * @param node
 */
private static void after(Node node) {
	if (node == null) {
		return;
	}
	ArrayDeque<Node> stack = new ArrayDeque<>();
	List<Node> result = new ArrayList<>();
	stack.push(node);
	while (!stack.isEmpty()) {
		Node n = stack.pop();
		// 加到队列开头
		result.add(0, n.getValue());
		if (n.getLeftChild() != null) {
			stack.push(n.getLeftChild());
		}
		if (n.getRightChild() != null) {
			stack.push(n.getRightChild());
		}
	}
}

首先root入栈，然后循环访问栈顶元素并出栈，接下来将左右子节点入栈，入栈顺序要是先右后左。

前/中/后序非递归遍历的通用解法

以后序为例

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 Main {

    public static void main(String[] args) {
    }

    public List<Integer> traversal(TreeNode root) {
    	// 等待访问的节点
        Stack<TreeNode> toVisitStack = new Stack<TreeNode>();
        // 访问节点的顺序
        List<TreeNode> visitQueue = new ArrayList<TreeNode>();
        List<Integer> result = new ArrayList<Integer>();
        if (root == null) {
            return result;
        }
        visitQueue.add(root);
        toVisitStack.push(root);
        while (!toVisitStack.isEmpty()) {
            TreeNode node = toVisitStack.pop();
            visitNode(node, visitQueue, toVisitStack);
        }
        for (TreeNode treeNode : visitQueue) {
            result.add(treeNode.val);
        }
        return result;
    }

    // 后序
    private void visitNode(TreeNode node, List<TreeNode> visitQueue, Stack<TreeNode> toVisitStack) {
        int index = visitQueue.indexOf(node);
        if (node.left != null) {
            visitQueue.add(index, node.left);
            toVisitStack.push(node.left);
        }
        index = visitQueue.indexOf(node);
        if (node.right != null) {
            visitQueue.add(index, node.right);
            toVisitStack.push(node.right);
        }
    }

    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) {
          val = x;
      }
    }

}

visitQueue保存的是最后所有节点的访问顺序，从index=0开始，首先我们将root加入visitQueue和toVisitStack，随后从toVisitStack中获取visitNode，将子节点插入visitQueue，这里以后序为例，左右节点均在当前节点之前访问且左节点优先于右节点，所以在visitQueue中的当前节点位置之前插入左右节点，随后将左右节点加入toVisitStack表示后序将对左右节点进行上述操作。

二叉树的广度优先遍历

我们可以通过一个队列来保存访问过的节点的左右子节点，然后删除访问过的节点，直到队列为空

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private static void layer(Node root) {
	if (root == null) {
		return;
	}
	List<Node> nodeQueue = new ArrayList<Node>();
	nodeQueue.add(root);
	while (nodeQueue.size() != 0) {
		Node node = nodeQueue.remove(0);
		System.out.println(node.getValue() + "");
		if (node.getLeftChild() != null) {
			nodeQueue.add(node.getLeftChild());
		}
		if (node.getRightChild() != null) {
			nodeQueue.add(node.getRightChild());
		}
	}
}