二叉树遍历-JAVA实现

基础二叉树

二叉树遍历分为前序、中序、后序递归和非递归遍历、还有层序遍历。

//二叉树节点
public class BinaryTreeNode {
    private int data;
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    
    public BinaryTreeNode() {}

    public BinaryTreeNode(int data, BinaryTreeNode left, BinaryTreeNode right) {
        super();
        this.data = data;
        this.left = left;
        this.right = right;
    }

    public int getData() {
        return data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public BinaryTreeNode getLeft() {
        return left;
    }

    public void setLeft(BinaryTreeNode left) {
        this.left = left;
    }

    public BinaryTreeNode getRight() {
        return right;
    }

    public void setRight(BinaryTreeNode right) {
        this.right = right;
    }
}

前序递归遍历算法：访问根结点-->递归遍历根结点的左子树-->递归遍历根结点的右子树

中序递归遍历算法：递归遍历根结点的左子树-->访问根结点-->递归遍历根结点的右子树

后序递归遍历算法：递归遍历根结点的左子树-->递归遍历根结点的右子树-->访问根结点

import com.ccut.aaron.stack.LinkedStack;

public class BinaryTree {
    //前序遍历递归的方式
    public void preOrder(BinaryTreeNode root){
        if(null!=root){
            System.out.print(root.getData()+"\t");
            preOrder(root.getLeft());
            preOrder(root.getRight());
        }
    }
    
    //前序遍历非递归的方式
    public void preOrderNonRecursive(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
        while(true){
            while(root!=null){
                System.out.print(root.getData()+"\t");
                stack.push(root);
                root=root.getLeft();
            }
            if(stack.isEmpty()) break;
            root=stack.pop();
            root=root.getRight();
        }
    }
    
    //中序遍历采用递归的方式
    public void inOrder(BinaryTreeNode root){
        if(null!=root){
            inOrder(root.getLeft());
            System.out.print(root.getData()+"\t");
            inOrder(root.getRight());
        }
    }
    
    //中序遍历采用非递归的方式
    public void inOrderNonRecursive(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
        while(true){
            while(root!=null){
                stack.push(root);
                root=root.getLeft();
            }
            if(stack.isEmpty())break;
            root=stack.pop();
            System.out.print(root.getData()+"\t");
            root=root.getRight();
        }
    }
    
    //后序遍历采用递归的方式
    public void postOrder(BinaryTreeNode root){
        if(root!=null){
            postOrder(root.getLeft());
            postOrder(root.getRight());
            System.out.print(root.getData()+"\t");
        }
    }
    
    //后序遍历采用非递归的方式
    public void postOrderNonRecursive(BinaryTreeNode root){
        Stack<BinaryTreeNode> stack=new Stack<BinaryTreeNode>();
        while(true){
            if(root!=null){
                stack.push(root);
                root=root.getLeft();
            }else{
                if(stack.isEmpty()) return;
                
                if(null==stack.lastElement().getRight()){
                    root=stack.pop();
                    System.out.print(root.getData()+"\t");
                    while(root==stack.lastElement().getRight()){
                        System.out.print(stack.lastElement().getData()+"\t");
                        root=stack.pop();
                        if(stack.isEmpty()){
                            break;
                        }
                    }
                }
                
                if(!stack.isEmpty())
                    root=stack.lastElement().getRight();
                else
                    root=null;
            }
        }
    }

    //层序遍历
    public void levelOrder(BinaryTreeNode root){
        BinaryTreeNode temp;
        Queue<BinaryTreeNode> queue=new LinkedList<BinaryTreeNode>();
        queue.offer(root);
        while(!queue.isEmpty()){
            temp=queue.poll();
            System.out.print(temp.getData()+"\t");
            if(null!=temp.getLeft()) 
                queue.offer(temp.getLeft());
            if(null!=temp.getRight()){
                queue.offer(temp.getRight());
            }
        }
    }
    
    public static void main(String[] args) {
        BinaryTreeNode node10=new BinaryTreeNode(10,null,null);
        BinaryTreeNode node8=new BinaryTreeNode(8,null,null);
        BinaryTreeNode node9=new BinaryTreeNode(9,null,node10);
        BinaryTreeNode node4=new BinaryTreeNode(4,null,null);
        BinaryTreeNode node5=new BinaryTreeNode(5,node8,node9);
        BinaryTreeNode node6=new BinaryTreeNode(6,null,null);
        BinaryTreeNode node7=new BinaryTreeNode(7,null,null);
        BinaryTreeNode node2=new BinaryTreeNode(2,node4,node5);
        BinaryTreeNode node3=new BinaryTreeNode(3,node6,node7);
        BinaryTreeNode node1=new BinaryTreeNode(1,node2,node3);
        
        BinaryTree tree=new BinaryTree();
        //采用递归的方式进行遍历
        System.out.println("-----前序遍历------");
        tree.preOrder(node1);
        System.out.println();
        //采用非递归的方式遍历
        tree.preOrderNonRecursive(node1);
        System.out.println();

        
        //采用递归的方式进行遍历
        System.out.println("-----中序遍历------");
        tree.inOrder(node1);
        System.out.println();
        //采用非递归的方式遍历
        tree.inOrderNonRecursive(node1);
        System.out.println();
        
        //采用递归的方式进行遍历
        System.out.println("-----后序遍历------");
        tree.postOrder(node1);
        System.out.println();
        //采用非递归的方式遍历
        tree.postOrderNonRecursive(node1);
        System.out.println();
        
        //采用递归的方式进行遍历
        System.out.println("-----层序遍历------");
        tree.levelOrder(node1);
        System.out.println();
    }
}

二叉搜索树

如果我们给二叉树加一个额外的条件，就可以得到一种被称作二叉搜索树(binary search tree)的特殊二叉树。二叉搜索树要求：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉排序树。

节点查找

//查找节点
public BinaryTreeNode find(int key) {
    BinaryTreeNode current = root;
    while(current != null){
        if(current.data > key){//当前值比查找值大，搜索左子树
            current = current.left;
        }else if(current.data < key){//当前值比查找值小，搜索右子树
            current = current.right;
        }else{
            return current;
        }
    }
    return null;//遍历完整个树没找到，返回null
}

插入节点

//插入节点
public boolean insert(BinaryTreeNode root, int data) {
    BinaryTreeNode newNode = new BinaryTreeNode(data);
    if(root == null){//当前树为空树，没有任何节点
        root = newNode;
        return true;
    }else{
        BinaryTreeNode current = root;
        BinaryTreeNode parentNode = null;
        while(current != null){
            parentNode = current;
            if(current.data > data){//当前值比插入值大，搜索左子节点
                current = current.left;
                if(current == null){//左子节点为空，直接将新值插入到该节点
                    parentNode.left = newNode;
                    return true;
                }
            }else{
                current = current.right;
                if(current == null){//右子节点为空，直接将新值插入到该节点
                    parentNode.right = newNode;
                    return true;
                }
            }
        }
    }
    return false;
}

查找最大值和最小值

要找最小值，先找根的左节点，然后一直找这个左节点的左节点，直到找到没有左节点的节点，那么这个节点就是最小值。同理要找最大值，一直找根节点的右节点，直到没有右节点，则就是最大值。

//找到最大值
public BinaryTreeNode findMax(){
    BinaryTreeNode current = root;
    BinaryTreeNode maxNode = current;
    while(current != null){
        maxNode = current;
        current = current.right;
    }
    return maxNode;
}
//找到最小值
public BinaryTreeNode findMin(){
    BinaryTreeNode current = root;
    BinaryTreeNode minNode = current;
    while(current != null){
        minNode = current;
        current = current.left;
    }
    return minNode;
}

删除节点

删除节点是二叉搜索树中最复杂的操作，删除的节点有三种情况，前两种比较简单，但是第三种却很复杂。

1、该节点是叶节点（没有子节点）

2、该节点有一个子节点

3、该节点有两个子节点

image

删除没有子节点的节点
public boolean delete(int key) {
    BinaryTreeNode current = root;
    BinaryTreeNode parent = root;
    boolean isLeftChild = false;
    //查找删除值，找不到直接返回false
    while(current.data != key){
        parent = current;
        if(current.data > key){
            isLeftChild = true;
            current = current.left;
        }else{
            isLeftChild = false;
            current = current.right;
        }
        if(current == null){
            return false;
        }
    }
    //如果当前节点没有子节点
    if(current.left == null && current.right == null){
        if(current == root){
            root = null;
        }else if(isLeftChild){
            parent.left = null;
        }else{
            parent.right = null;
        }
        return true;
    }
    return false;
}

删除有一个子节点的节点，我们只需要将其父节点原本指向该节点的引用，改为指向该节点的子节点即可。