Java 数据结构进阶二叉树题集下

Java 数据结构进阶二叉树题集下攻略

本文将分享 Java 数据结构进阶二叉树题集下的完整攻略，希望能对读者有所帮助。本文具体展示的是如何使用 Java 实现二叉树的相关算法。

1. 二叉树的创建

二叉树的创建有多种方式，本文以手工创建的方式为例。代码如下：

class Node {
    Node left;      
    Node right;     
    int value;      

    public Node(int value){
        this.value=value;
        this.left=null;
        this.right=null;
    }
}

public class BinaryTree{
    private Node root;     

    public BinaryTree(){
        root=null;
    }

    public void insert(int value){
        Node node=new Node(value);
        if(root==null){
            root=node;
            return;
        }else{
            Node current=root;
            Node parent=null;
            while(true){
                parent=current;
                if(value<current.value){
                    current=current.left;
                    if(current==null){
                        parent.left=node;
                        return;
                    }
                }else{
                    current=current.right;
                    if(current==null){
                        parent.right=node;
                        return;
                    }
                }
            }
        }
    }
}

上述代码中，我们首先定义了一个 Node 类作为二叉树的结点。然后在 BinaryTree 类中，定义了一个私有变量 root 作为二叉树的根结点，并提供了一个 insert 方法用于插入新的结点。

在 insert 方法中，我们首先判断二叉树是不是空树，如果是空树则直接将新结点设置为根结点。否则我们需要找到新插入结点的位置，这里我们采用了二叉查找树的方式，即比较新插入结点的值与当前结点值的大小，如果小于当前结点值则向左查找，如果大于当前结点值则向右查找。在找到合适的插入位置后，我们将结点插入该位置。

2. 二叉树遍历

二叉树的遍历是指按照某种次序依次访问二叉树中的所有结点。常见的遍历方法有三种：先序遍历、中序遍历和后序遍历。

2.1 先序遍历

先序遍历的顺序是先访问根结点，再访问左子树，最后访问右子树。代码如下：

public void preOrder(Node localRoot){
    if(localRoot!=null){
        System.out.print(localRoot.value+" ");
        preOrder(localRoot.left);
        preOrder(localRoot.right);
    }
}

上述代码中，我们采用递归的方式实现先序遍历。如果当前结点非空，则首先输出当前结点的值，然后递归遍历左子树和右子树。

2.2 中序遍历

中序遍历的顺序是先访问左子树，再访问根结点，最后访问右子树。代码如下：

public void inOrder(Node localRoot){
    if(localRoot!=null){
        inOrder(localRoot.left);
        System.out.print(localRoot.value+" ");
        inOrder(localRoot.right);
    }
}

上述代码中，类似先序遍历，我们也采用递归的方式实现中序遍历。如果当前结点非空，则首先遍历左子树，然后输出当前结点的值，最后递归遍历右子树。

2.3 后序遍历

后序遍历的顺序是先访问左子树，再访问右子树，最后访问根结点。代码如下：

public void postOrder(Node localRoot){
    if(localRoot!=null){
        postOrder(localRoot.left);
        postOrder(localRoot.right);
        System.out.print(localRoot.value+" ");
    }
}

上述代码中，同样采用递归的方式实现后序遍历。如果当前结点非空，则首先递归遍历左子树，然后递归遍历右子树，最后输出当前结点的值。

3. 二叉树的查找

二叉树的查找是指在二叉树中查找某个值是否存在。下面我们给出一个二叉查找树的查找方法。代码如下：

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

上述代码中，我们采用二叉查找树的方式实现查找。首先从根结点开始遍历，如果查找值小于当前结点的值，则向左查找；否则向右查找。如果当前结点为空，则表示该值不存在于二叉树中，返回 null。如果找到了相应的结点，则返回该结点。

示例说明

示例 1

假设我们已经创建了一个二叉树，如下所示：

      12
     /   \
    5     20
   / \   /  \
  2   7 15  22

接下来，我们可以调用二叉树的遍历方法和查找方法，例如：

BinaryTree bt = new BinaryTree();
bt.insert(12);
bt.insert(5);
bt.insert(20);
bt.insert(2);
bt.insert(7);
bt.insert(15);
bt.insert(22);

System.out.println("先序遍历结果：");
bt.preOrder(bt.root);
System.out.println();

System.out.println("中序遍历结果：");
bt.inOrder(bt.root);
System.out.println();

System.out.println("后序遍历结果：");
bt.postOrder(bt.root);
System.out.println();

System.out.println("查找结点 20：");
System.out.println(bt.find(20).value);

上述代码中，我们首先创建了一个二叉树，并分别调用其遍历方法和查找方法。输出结果如下：

先序遍历结果：
12 5 2 7 20 15 22 
中序遍历结果：
2 5 7 12 15 20 22 
后序遍历结果：
2 7 5 15 22 20 12 
查找结点 20：
20

示例 2

假设我们需要构建一个二叉查找树，并插入一些结点，如下所示：

BinaryTree bt = new BinaryTree();
bt.insert(15);
bt.insert(6);
bt.insert(18);
bt.insert(3);
bt.insert(7);
bt.insert(17);
bt.insert(20);

接下来，我们可以调用二叉树的查找方法，例如：

System.out.println("查找结点 7：");
System.out.println(bt.find(7).value);

上述代码中，我们首先创建了一个二叉查找树，并插入了一些结点。然后我们查找值为 7 的结点。输出结果为：

查找结点 7：
7

结论

本文分享了 Java 数据结构进阶二叉树题集下的完整攻略，包含二叉树的创建、遍历和查找等方面的内容。希望这篇文章对读者有所帮助，让读者能更好地掌握二叉树的相关算法。