用Java实现二叉树

使用Java实现int值类型的排序二叉树

二叉树是一种递归数据结构，每个节点最多具有两个子节点.

通常，二叉树是二叉搜索树二叉树 java实现，每个节点的值都大于或等于其左子树节点上的值，并且小于或等于其右子树节点上的值，如下所示

为了实现二叉树，我们使用Node类来表示节点，这些节点存储int类型值和对子节点的引用.

package com.java.node.BinaryTree;
public class Node {
    int data;
    Node left;
    Node right;
    public Node(int data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

然后添加树的根节点

package com.java.node.BinaryTree;
public class BinaryTree {
    Node root;
}

首先，我们必须找到新节点的位置，以维持树的顺序. 我们必须从根节点开始，并且必须遵循以下规则:

    private Node addNode(Node current, int value) {
        if (current == null) {
            return new Node(value);
        }
        if (value < current.data) {
            current.left = addNode(current.left, value);
        } else if (value > current.data) {
            current.right = addNode(current.right, value);
        } else {
            return current;
        }
        return current;
    }
    public void addNode(int value) {
        root = addNode(root, value);
    }

您可以使用该方法创建二叉树

public BinaryTree createBinaryTree() {
        BinaryTree bt = new BinaryTree();
        bt.addNode(6);
        bt.addNode(4);
        bt.addNode(8);
        bt.addNode(10);
        return bt;
    }

    private boolean containNode(Node current, int value) {
        if (current == null) {
            return false;
        }
        if (value == current.data) {
            return true;
        }
        return value < current.data ? containNode(current.left, value) : containNode(current.right, value);
    }
    public boolean containNode(int value) {
        return containNode(root, value);
    }

private Node deleteNode(Node current, int value) {
        if (current == null) {
            return null;
        }
        if (value == current.data) {
            if (current.left == null && current.right == null) {
                return null;
            }
            if (current.left == null) {
                return current.right;
            }
            if (current.right == null) {
                return current.left;
            }
            int smallestValue = findSmallestValue(current.right);
            current.data = smallestValue;
            current.right = deleteNode(current.right, smallestValue);
            return current;
        }
        if (value < current.data) {
            current.left = deleteNode(current.left, value);
            return current;
        }
        current.right = deleteNode(current.right, value);
        return current;
    }
    private int findSmallestValue(Node root) {
        return root.left == null ? root.data : findSmallestValue(root.right);
    }

我们将以不同的方式遍历树，即深度优先二叉树 java实现，宽度优先.

深度优先遍历树

深度优先查询是在查询同级节点之前尽可能多地查询每个子节点的一种方法.

有序，前序和后序方法都以深度优先的方式遍历树.

按顺序遍历是先遍历左侧子树，然后遍历根节点，最后遍历右侧子树.

    public void traverseInOrder(Node root) {
        if (root != null) {
            traverseInOrder(root.left);
            System.out.println(root.data);
            traverseInOrder(root.right);
        }
    }

预遍历首先是根节点，然后是左子树，最后是右子树.

public void traversePreOrder(Node root) {
        if (root != null) {
            System.out.println(root.data);
            traversePreOrder(root.left);
            traversePreOrder(root.right);
        }
    }

后序遍历首先遍历左子树，然后遍历右子树，最后遍历根节点.

public void traversePostOrder(Node root) {
        if (root != null) {
            traversePostOrder(root.left);
            traversePostOrder(root.right);
            System.out.println(root.data);
        }
    }

以广度优先进行遍历

它将遍历当前级别的所有节点，然后遍历下一级别的节点.

这种遍历类型也称为水平顺序. 遍历树从根节点开始，从左到右运行.

为此，使用一个队列来存储每个级别的节点. 我们将从列表中获取每个节点. 然后将他的子节点添加到队列中.

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-164539-1.html