Cây nhị phân:

Các quy tắc duyệt:

• Duyệt tiền thứ tự:
  1. Truy cập nút gốc
  2. Duyệt tiền thứ tự cây con bên trái của nút gốc
  3. Duyệt tiền thứ tự cây con bên phải của nút gốc
• Duyệt trung thứ tự:
  1. Duyệt trung thứ tự cây con bên trái của nút gốc
  2. Truy cập nút gốc
  3. Duyệt trung thứ tự cây con bên phải của nút gốc
• Duyệt hậu thứ tự:
  1. Duyệt hậu thứ tự cây con bên trái của nút gốc
  2. Duyệt hậu thứ tự cây con bên phải của nút gốc
  3. Truy cập nút gốc

Đây là biểu đồ cây nhị phân được xác định bởi chương trình 2:

public class BinarySearchTree {
    private class TreeNode {
        int value;
        String label;
        TreeNode left;
        TreeNode right;

        TreeNode(int value, String label) {
            this.value = value;
            this.label = label;
        }

        @Override
        public String toString() {
            return label + " có giá trị " + value;
        }
    }

    private TreeNode root;

    public void insert(int value, String label) {
        TreeNode newNode = new TreeNode(value, label);
        if (root == null) {
            root = newNode;
        } else {
            TreeNode current = root;
            TreeNode parent;
            while (true) {
                parent = current;
                if (value < current.value) {
                    current = current.left;
                    if (current == null) {
                        parent.left = newNode;
                        return;
                    }
                } else {
                    current = current.right;
                    if (current == null) {
                        parent.right = newNode;
                        return;
                    }
                }
            }
        }
    }

    public void inorderTraversal(TreeNode node) {
        if (node != null) {
            inorderTraversal(node.left);
            System.out.println(node);
            inorderTraversal(node.right);
        }
    }

    public void preorderTraversal(TreeNode node) {
        if (node != null) {
            System.out.println(node);
            preorderTraversal(node.left);
            preorderTraversal(node.right);
        }
    }

    public void postorderTraversal(TreeNode node) {
        if (node != null) {
            postorderTraversal(node.left);
            postorderTraversal(node.right);
            System.out.println(node);
        }
    }

    public TreeNode search(int value) {
        TreeNode current = root;
        while (current.value != value) {
            if (value < current.value) {
                current = current.left;
            } else {
                current = current.right;
            }
            if (current == null) {
                return null;
            }
        }
        return current;
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(50, "Giám đốc");
        tree.insert(25, "Phó Giám đốc");
        tree.insert(15, "Quản lý Văn phòng");
        tree.insert(30, "Thư ký");
        tree.insert(75, "Quản lý Bán hàng");
        tree.insert(85, "Nhân viên Bán hàng 1");

        System.out.println("Duyệt trung thứ tự:");
        tree.inorderTraversal(tree.root);

        System.out.println("Duyệt tiền thứ tự:");
        tree.preorderTraversal(tree.root);

        System.out.println("Duyệt hậu thứ tự:");
        tree.postorderTraversal(tree.root);

        System.out.println("\nNút có giá trị 75:");
        System.out.println(tree.search(75));
    }
}

import java.util.Stack;

public class BinaryTree {
    private char data;
    private BinaryTree left;
    private BinaryTree right;

    public BinaryTree(char data) {
        this.data = data;
    }

    public static void recursivePreorder(BinaryTree node) {
        if (node == null) return;
        System.out.print(node.data);
        recursivePreorder(node.left);
        recursivePreorder(node.right);
    }

    public static void recursiveInorder(BinaryTree node) {
        if (node == null) return;
        recursiveInorder(node.left);
        System.out.print(node.data);
        recursiveInorder(node.right);
    }

    public static void recursivePostorder(BinaryTree node) {
        if (node == null) return;
        recursivePostorder(node.left);
        recursivePostorder(node.right);
        System.out.print(node.data);
    }

    public static void iterativePreorder(BinaryTree node) {
        Stack<BinaryTree> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                System.out.print(node.data);
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                node = node.right;
            }
        }
    }

    public static void iterativeInorder(BinaryTree node) {
        Stack<BinaryTree> stack = new Stack<>();
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            if (!stack.isEmpty()) {
                node = stack.pop();
                System.out.print(node.data);
                node = node.right;
            }
        }
    }

    public static void iterativePostorder(BinaryTree node) {
        Stack<BinaryTree> stack = new Stack<>();
        Stack<Integer> visited = new Stack<>();
        Integer marker = new Integer(1);
        while (node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                visited.push(new Integer(0));
                node = node.left;
            }
            while (!stack.isEmpty() && visited.peek().equals(marker)) {
                visited.pop();
                System.out.print(stack.pop().data);
            }
            if (!stack.isEmpty()) {
                visited.pop();
                visited.push(new Integer(1));
                node = stack.peek();
                node = node.right;
            }
        }
    }

    public static void main(String[] args) {
        BinaryTree root = new BinaryTree('a');
        BinaryTree b2 = new BinaryTree('b');
        BinaryTree b3 = new BinaryTree('c');
        BinaryTree b4 = new BinaryTree('d');
        BinaryTree b5 = new BinaryTree('e');

        root.left = b2;
        root.right = b3;
        b2.left = b4;
        b2.right = b5;

        System.out.println("Tiền thứ tự đệ quy:");
        recursivePreorder(root);
        System.out.println();

        System.out.println("Tiền thứ tự lặp:");
        iterativePreorder(root);
        System.out.println();

        System.out.println("Trung thứ tự đệ quy:");
        recursiveInorder(root);
        System.out.println();

        System.out.println("Trung thứ tự lặp:");
        iterativeInorder(root);
        System.out.println();

        System.out.println("Hậu thứ tự đệ quy:");
        recursivePostorder(root);
        System.out.println();

        System.out.println("Hậu thứ tự lặp:");
        iterativePostorder(root);
    }
}