数据结构专题——二叉树

二叉树专题——二叉树定义、创建和递归遍历

定义

// 定义二叉树的节点类
class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    public TreeNode(int value) {
        this.value = value;
        left = null;
        right = null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

// 二叉树的定义和创建方法
public class BinaryTree {
    private TreeNode root;

    public BinaryTree() {
        root = null;
    }

    public void createTree(int[] values) {
        root = createTreeHelper(values, 0);
    }

    private TreeNode createTreeHelper(int[] values, int index) {
        if (index >= values.length) {
            return null;
        }
        TreeNode newNode = new TreeNode(values[index]);
        newNode.left = createTreeHelper(values, 2 * index + 1);
        newNode.right = createTreeHelper(values, 2 * index + 2);

        return newNode;
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

前序遍历

public static void preorderTraversalHelper(TreeNode node) {
    if (node != null) {
        System.out.print(node.value + " ");
        preorderTraversalHelper(node.left);
        preorderTraversalHelper(node.right);
    }
}

1
2
3
4
5
6
7
8

中序遍历

public static void preorderTraversalHelper(TreeNode node) {
    if (node != null) {
        preorderTraversalHelper(node.left);
        System.out.print(node.value + " ");    
        preorderTraversalHelper(node.right);
    }
}
1
2
3
4
5
6
7

后序遍历

public static void preorderTraversalHelper(TreeNode node) {
    if (node != null) {
        preorderTraversalHelper(node.left);         
        preorderTraversalHelper(node.right);
        System.out.print(node.value + " ");  
    }
}
1
2
3
4
5
6
7