アルゴリズム-01

一、二叉木

1、前順遍歴:ルートノードに先にアクセスし、左サブツリーに前順遍歴し、右サブツリーに前順遍歴する

private void preorderTraversal() {
    preorderTraversal(root);
}

private void preorderTraversal(Node node) {
    if(node == null) return;
    System.out.printIn(node.element);
    preorderTraversal(root.left);
    preorderTraversal(root.right);
}

2、中序遍歴：まず中序遍歴左サブツリー、ルートノード、中序遍歴右サブツリーにアクセスする

private void inorderTraversal() {
    inorderTraversal(root);
}

private void inorderTraversal(Node node) {
    if(node == null) return;
    inorderTraversal(root.left);
    System.out.printIn(node.element);
    inorderTraversal(root.right);
}

3、後順遍歴：先に訪問した後に左サブツリー、後に右サブツリー、ルートノードを遍歴する

private void postorderTraversal() {
    postorderTraversal(root);
}

private void postorderTraversal(Node node) {
    if(node == null) return;
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    System.out.printIn(node.element);
}

4、層順遍歴:上から下へ、左から右へ各ノードに順次アクセスし、キューを使用する

構想:1、ルートノードをエンキューする2、キューが空のaになるまで、キューヘッダノードAをエンキューし、bにアクセスし、Aの左サブノードをエンキューするc、Aの右サブノードをエンキューする

public void reverseTree() {
    if(root == null) return;
    Queue queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()) {
        Node node = queue.poll()
        Sysytem.out.printIn(node.element)
        if(node.left != null) {
            queue.offer(node.left)
        }
        if(node.right != null) {
            queue.offer(node.right)
        }
    }
}

5、二叉木の高さを計算する

public int height() {
    return height(root);
}

1、  
private int height(Node node) {
    if(node == null) return 0;
    return 1 + Max.max(height.left, height.right);
}

2、  ，        
public int height() {
    if(root== null) return 0;
    int height = 0;
    int levelSize = 1;
    Queue queue = new LinkedList<>();
    queue.offer(root);

    while(!queue.isEmpty()) {
        Node node = queue.poll()
        levelSize--;
        if(node.left != null) {
            queue.offer(node.left)
        }
        if(node.right != null) {
            queue.offer(node.right)
        }
        if(levelSize == 0) {
            levelSize = queue.size();
            height++;
        }
    }
}

6、一つの木が完全二叉木かどうかを判断する

1、考え方a、木が空の場合false b、木が空でない場合、二叉樹の層順遍歴(キュー方式)を開始する

node.left !=null && node.right != null、node.left、node.rightは順番に

に入隊した.

node.left == null && node.right != null、false

を返します

node.left != null && node.ああ...left == null && node.right==nullで、後ろを通るすべてのノードがリーフノードであり、完全な二叉木である.そうしないとfalse

に戻る.

public boolean isComplete() {
    if(root == null) return false;
    Queue queue = new LinkedList<>();
    queue.offer(root);

    boolean leaf = false;

    while(!queue.isEmpty()) {
        Node node = queue.poll();
        if(lead && !(node.left == null && node.right == null)) {
            return false;
        }
        if(node.left != null && node.right != null) {
            queue.offer(node.left);
            queue.offer(node.right);
        } else if(nodel.left = == null && node.right != null) {
            return false;
        } else { //                
            leaf = true;
        }
    }
    return true;
}

7、ツリーを反転

a、前順遍歴

private TreeNode invertTree(TreeNode root) {
    if(root == null) return root;
    
    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    invertTree(root.left);
    invertTree(root.right);

    return root;
}

b、中序遍歴

private TreeNode invertTree(TreeNode root) {
    if(root == null) return root;
    
    invertTree(root.left);

    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;
    invertTree(root.left);

    return root;
}

c、後順遍歴

private TreeNode invertTree(TreeNode root) {
    if(root == null) return root;
    
    invertTree(root.left);
    invertTree(root.right);

    TreeNode tmp = root.left;
    root.left = root.right;
    root.right = tmp;

    return root;
}

d、層順遍歴

private TreeNode invertTree(TreeNode root) {
    if(root == null) return root;

    Queue queue = new LinkedList<>();
    queue.offer(root);

    while (! queue.isEmpty()) {

        Node node = queue.poll();
        Node tmp = node.left;
        node.left = node.right;
        node.right = tmp;

        if(node.left != null) {
            queue.offer(node.left);
        }
        if(node.left != null) {
            queue.offer(node.right);
        }
    }
}

二、完全二叉木の結点個数を計算する

// n：     
 n   ，n0 = n / 2
 n   ，n0 = (n + 1)/2
n0 = (n + 1) >> 1