二叉树基本操作代码递归遍历非递归遍历层次遍历分层输出的层次遍历删除子树求树的深度数组构建哈夫曼树平衡二叉树

本文章记录一些二叉树的基本操作：

先来准备一个简单的树的节点：

//节点类
class Node{

    int value;//节点值
    Node left;//左子树
    Node right;//右子树

    public Node(int v){  this.value = v; }
}

递归遍历

前序遍历

    //递归前序遍历
    static void preOrderShow(Node node){
        if (node==null) return;
        System.out.print(node.value+" ");
        preOrderShow(node.left);
        preOrderShow(node.right);
    }

中序遍历

    //递归中序遍历
    static void inOrderShow(Node node){
        if (node==null) return;
        preOrderShow(node.left);
        System.out.print(node.value+" ");
        preOrderShow(node.right);
    }

后序遍历

    //递归后序遍历
    static void tailOrderShow(Node node){
        if (node==null) return;
        preOrderShow(node.left);
        preOrderShow(node.right);
        System.out.print(node.value+" ");
    }

非递归遍历

前序遍历

    //非递归前序遍历
    static void preOrderShow1(Node node){
        Stack<Node> stack = new Stack<>();
        Node p = node;//用一个p指针指向当前的节点
        while(p!=null||stack.size()>0){
            if (p!=null){
                System.out.print(p.value+" ");//输出p节点的值
                stack.push(p);
                p = p.left;
            }else{
                p = stack.pop();
                p = p.right;
            }
        }
    }

中序遍历

    //非递归中序遍历
    static void inOrderShow1(Node node){
        Stack<Node> stack = new Stack<>();
        Node p = node;//用一个p指针指向当前的节点
        while(p!=null||stack.size()>0){
            if (p!=null){
                stack.push(p);
                p = p.left;
            }else{
                p = stack.pop();
                System.out.print(p.value+" ");//输出p节点的值
                p = p.right;
            }
        }
    }

后序遍历

    //非递归后序遍历
   static List<Integer> tailOrderShow1(Node node){
        Stack<Node> stack = new Stack<>();
        List<Integer> list = new ArrayList<>();
        queue.push(node);
        while(stack.size()>0){
            Node node1 = stack.pop();
            list.add(node1.value);
            if (node1.left!=null) stack.push(node1.left);
            if (node1.right!=null) stack.push(node1.right);
        }
        Collections.reverse(list);
        return list;
    }

层次遍历

    //层次遍历
    static void levelShow(Node node){
        //模拟队列
        LinkedList<Node> queue = new LinkedList<>();
        //把头节点加入队列
        queue.addLast(node);
        //当前节点指针
        Node p;
        while(queue.size()>0){
            //出队列
            p = queue.removeFirst();
            System.out.print(p.value+" ");
            //左节点进队列
            if (p.left!=null) queue.addLast(p.left);
            //右节点进队列
            if (p.right!=null) queue.addLast(p.right);
        }
    }

分层输出的层次遍历

    //层次遍历分层输出
    static void levelShow1(Node node){
        //模拟队列
        LinkedList<Node> queue = new LinkedList<>();
        //把头节点加入队列
        queue.addLast(node);
        //当前节点指针
        Node p;
        //记录的当前行最后一个节点
        Node currentlastNode = node;
        //记录下一行的最后一个节点
        Node nextlastNode = null;
        
        while(queue.size()>0){
            p = queue.removeFirst();
            System.out.print(p.value+" ");
            //左节点进队列
            if (p.left!=null){
                queue.addLast(p.left);
                nextlastNode = p.left;
            }
            //右节点进队列
            if (p.right!=null) {
                queue.addLast(p.right);
                nextlastNode = p.right;
            }
            //如当前遍历的节点是记录行的最后一个节点，证明当前行已经遍历结束了，输出换行符
            //把下一行的最后一个节点赋给当前行最后一个节点
            if (currentlastNode==p) {
                System.out.println();
                currentlastNode = nextlastNode;
            }
        }
    }

删除子树

    //删除子树,返回新的树根结点
    static Node deleteChild(Node node,int val){
        //树为null直接返回null
        if (node==null) return null;
        //要删除的是根节点，返回新的树根节点就是null
        if (val==node.value) return null;
        //发现左子树的值是需要删除的节点，把左子树设为null；
        if (node.left!=null&&val==node.left.value){
            node.left=null;
            return node;
        }
        //发现右子树的值是需要删除的节点，把右子树设为null；
        else if (node.right!=null&&val==node.right.value) {
            node.right = null;
            return node;
        }
        //左右子树都不是，在左右子树上递归寻找
        else {
            deleteChild(node.left,val);
            deleteChild(node.right,val);
            return node;
        }
    }

求树的深度

   //求树的深度
   static int depth(Node node){
        //如node为null，深度为0
        if (node==null) return 0;
        //求出左子树的高度
        int leftDepth = depth(node.left);
        //求出右子树的高度
        int rightDepth = depth(node.right);
        //左右子树高度的最大值加上1就是本节点的高度
        return Math.max(leftDepth,rightDepth)+1;
    }

数组构建哈夫曼树

    //构建哈夫曼树
    static Node haff(int[] arr) {
        List<Node> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            list.add(new Node(arr[i]));
        }

        while (list.size() > 1) {
            Collections.sort(list, (o1, o2) -> o1.value - o2.value);
            Node n1 = list.get(0);
            Node n2 = list.get(1);
            Node parent = new Node(n1.value + n2.value);
            parent.left = n1;
            parent.right = n2;
            list.remove(n1);
            list.remove(n2);
            list.add(parent);
        }
        Node node = list.get(0);
         return node;
    }
}

平衡二叉树

添加节点

//平衡二叉树添加节点(root!=null)
    static void addNode(Node root,Node node){
        if (node==null) return;
        if (node.value<=root.value){
            if (root.left==null) root.left = node;
            else addNode(root.left,node);
        }else{
            if (root.right==null) root.right = node;
            else addNode(root.right,node);
        }
    }

左旋

    //平衡二叉树的左旋，返回新头节点
    static Node leftRotate(Node node){
        Node newRoot = node.right;
        node.right = newRoot.left;
        newRoot.left = node;
        return newRoot;
    }

右旋

    //平衡二叉树的右旋，返回新的头节点
    static Node rightRotate(Node node){
        Node newRoot = node.left;
        node.left = newRoot.right;
        newRoot.right = node;
        return newRoot;
    }

自调整

    //平衡二叉树的自调整
    static Node rotate(Node node){

        //空树直接返回
        if (node==null) return node;

        //左子树深度-右子树>1，需要右旋
        if (depth(node.left)-depth(node.right)>1) {
            //判断左子树需不需要先左旋
            if (node.left != null && depth(node.left.right) > depth(node.left.left)){
                node.left = leftRotate(node.left);
            }
            return rightRotate(node);
        }

        //右子树深度-左子树>1，需要左旋
        if (depth(node.right)-depth(node.left)>1) {
            //判断右子树需不需要先右旋
            if (node.right!=null&&depth(node.right.left)>depth(node.right.right)){
                node.right = rightRotate(node.right);
            }
            return leftRotate(node);
        }
        return node;
    }

最后

以上就是高贵银耳汤为你收集整理的二叉树基本操作代码递归遍历非递归遍历层次遍历分层输出的层次遍历删除子树求树的深度数组构建哈夫曼树平衡二叉树的全部内容，希望文章能够帮你解决二叉树基本操作代码递归遍历非递归遍历层次遍历分层输出的层次遍历删除子树求树的深度数组构建哈夫曼树平衡二叉树所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。