二叉树的操作（java实现）

交换二叉树左右子树图示：(其中橙色表示根节点，蓝色表示普通节点)


image.png
public interface BTreeOperationInterface<TreeNode> {

    /**
     * 创建二叉树
     * @param arr
     */
    TreeNode createBTree(int[] arr);

    /**
     * 判断二叉树是否为空
     * @param treeNode
     * @return
     */
    boolean BTreeEmpty(TreeNode treeNode);

    /**
     * 先序遍历二叉树
     * @param treeNode
     */
    void preOrderTraverseBTree(TreeNode treeNode);

    /**
     * 中序遍历二叉树
     * @param treeNode
     */
    void inOrderTraverseBTree(TreeNode treeNode);

    /**
     * 后序遍历二叉树
     * @param treeNode
     */
    void postOrderTraverseBTree(TreeNode treeNode);

    /**
     * 层次遍历二叉树
     */
    void levelTraverseBTree(TreeNode treeNode);

    /**
     * 求二叉树深度
     * @param treeNode
     * @return
     */
    int BTreeDepth(TreeNode treeNode);

    /**
     * 清空二叉树
     * @param treeNode
     */
    void clearBTree(TreeNode treeNode);

    /**
     * 统计叶子节点个数
     * @param root
     * @return
     */
    int countLeaf(TreeNode root);

    /**
     * 交换左右子树
     */
    TreeNode swapSubLeftTreeAndRightTree(TreeNode root);
}

import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Stack;

public class BinaryTreeTest {
    public static void main(String[] args){
        int[] arr={0,1,2,3,4,5,6};
        BTreeOpration bTreeOpration=new BTreeOpration();
        //创建二叉树
        TreeNode root=bTreeOpration.createBTree(arr);

        //层次遍历二叉树
        System.out.print("层次遍历：");
        bTreeOpration.levelTraverseBTree(root);

        //递归先序遍历
        System.out.print("先序遍历(递归)：");
        bTreeOpration.preOrderTraverseBTree(root);
        System.out.println();

        System.out.print("根 右 左：");
        bTreeOpration.traverseBTree(root);
        System.out.println();

        //迭代先序遍历
        System.out.print("先序遍历(迭代)：");
        bTreeOpration.preOrderTraverseBTreeIterator(root);

        //递归中序遍历
        System.out.print("中序遍历(递归)：");
        bTreeOpration.inOrderTraverseBTree(root);
        System.out.println();

        //迭代中序遍历
        System.out.print("中序遍历(迭代)：");
        bTreeOpration.inOrderTraverseBTreeIterator(root);

        //递归后序遍历
        System.out.print("后序遍历(递归)：");
        bTreeOpration.postOrderTraverseBTree(root);
        System.out.println();

        //迭代后序遍历
        System.out.print("后序遍历(迭代)：");
        bTreeOpration.postOrderTraverseBTreeIterator(root);

        System.out.println("树的深度："+bTreeOpration.BTreeDepth(root));

        System.out.println("叶子节点个数："+bTreeOpration.countLeaf(root));

        //交换左右子树
        root=bTreeOpration.swapSubLeftTreeAndRightTree(root);
        System.out.print("交换后的层次遍历：");
        bTreeOpration.levelTraverseBTree(root);
    }

    static class BTreeOpration implements BTreeOperationInterface<TreeNode>{
        /**
         * 根结点
         */
        private TreeNode root;


        /**
         * 给定一组整数，请按照从上到下，从左到右的顺序构造一棵二叉树(其实就是完全二叉树)
         * eg: arr=[2,4,5,1,3];
         * return=2(4(1,3),5)
         * @param arr
         * @return TreeNode
         */
        @Override
        public TreeNode createBTree(int[] arr) {
            List<TreeNode> nodeList = new LinkedList<TreeNode>();
            //将数组的值转化为TreeNode
            for(int index=0;index < arr.length;index++){
                nodeList.add(new TreeNode(arr[index]));
            }

            //按照数组中父节点与孩子节点下标的关系建立二叉树
            //从上往下构建
            //右端点：2*i+2≤n => i≤(n/2)-1
            for(int i=0;i<(arr.length >> 1);i++){
                //左孩子：2*i+1
                nodeList.get(i).setLeft(nodeList.get((i<<1)+1));
                //右孩子：2*i+2
                //右孩子存在，才建立右孩子
                if((i<<1)+2 < arr.length){
                    nodeList.get(i).setRight(nodeList.get((i<<1)+2));
                }
            }
            root=nodeList.get(0);
            return root;
        }

        @Override
        public boolean BTreeEmpty(TreeNode treeNode) {
            return treeNode==null;
        }


        /**
         * 先序遍历递归实现
         * @param node
         */
        @Override
        public void preOrderTraverseBTree(TreeNode node) {
            //用的是if，若用while，会卡在左子树最左边的地方出不去
            if (node != null){
                System.out.print(node.data+" ");
                preOrderTraverseBTree(node.left);
                preOrderTraverseBTree(node.right);
            }

        }

        /**
         * 根 右 左
         * @param node
         */
        public void traverseBTree(TreeNode node) {
            //用的是if，若用while，会卡在左子树最左边的地方出不去
            if (node != null){
                System.out.print(node.data+" ");
                traverseBTree(node.right);
                traverseBTree(node.left);
            }

        }
        /**
         * 先序遍历迭代实现
         * @param node
         */
        public void preOrderTraverseBTreeIterator(TreeNode node) {
            StringBuilder sb=new StringBuilder();
            if(node==null)
                return;
            Stack<TreeNode> stack=new Stack<>();
            TreeNode currentNode=node;

            while (currentNode != null || !stack.isEmpty()){
                while (currentNode != null){
                    sb.append(currentNode.data);
                    sb.append(" ");
                    stack.push(currentNode);
                    currentNode=currentNode.left;
                }
                //该位置已经到最左边
                //注意，叶子节点的左右节点（为null）同样需要判断
                if(!stack.isEmpty()){
                    currentNode=stack.pop();
                    currentNode=currentNode.right;
                }
            }
            System.out.println(sb.toString().trim());

        }
        @Override
        public void inOrderTraverseBTree(TreeNode node) {
            if (node != null){
                inOrderTraverseBTree(node.left);
                System.out.print(node.data+" ");
                inOrderTraverseBTree(node.right);
            }
        }

        /**
         * 中序遍历迭代实现
         * @param node
         */
        public void inOrderTraverseBTreeIterator(TreeNode node) {
            StringBuilder sb=new StringBuilder();
            TreeNode currentNode = node;
            if (currentNode == null)
                return;
            Stack<TreeNode> stack = new Stack<>();
            while (currentNode!=null || !stack.isEmpty()){
                while (currentNode!=null){
                    stack.push(currentNode);
                    currentNode=currentNode.left;
                }
                //此时，currentNode已经为null（最左边的叶子节点的左节点）
                if(!stack.isEmpty()){
                    //最左边的叶子节点，弹栈
                    currentNode=stack.pop();
                    sb.append(currentNode.data);
                    sb.append(" ");
                    currentNode=currentNode.right;
                }
            }
            System.out.println(sb.toString().trim());
        }
        @Override
        public void postOrderTraverseBTree(TreeNode node) {
            if (node != null){
                postOrderTraverseBTree(node.left);
                postOrderTraverseBTree(node.right);
                System.out.print(node.data+" ");
            }
        }

        /**
         * 后序遍历迭代实现（可用双栈实现）
         * （类似前序遍历）：首先按： 根 右 左次序遍历，然后反转，得左 右 根
         * @param node
         */
        public void postOrderTraverseBTreeIterator(TreeNode node) {
            StringBuilder sb=new StringBuilder();
            TreeNode currentNode = node;
            if (currentNode == null)
                return;
            Stack<TreeNode> stack=new Stack<>();
            while (currentNode !=null || !stack.isEmpty()){
                while (currentNode!=null){
                    stack.push(currentNode);
                    sb.append(currentNode.data);
                    sb.append(" ");
                    currentNode=currentNode.right;
                }
                if(!stack.isEmpty()){
                    currentNode=stack.pop();
                    currentNode=currentNode.left;
                }
            }
            System.out.println(sb.reverse().toString().trim());
        }

        /**
         * 层次遍历二叉树
         * @param treeNode
         */
        @Override
        public void levelTraverseBTree(TreeNode treeNode){
            StringBuilder sb=new StringBuilder();
            Queue<TreeNode> queue=new LinkedList<>();
            queue.offer(treeNode);
            while (!queue.isEmpty()){
                TreeNode root=queue.poll();
                sb.append(root.data);
                sb.append(" ");
                if(root.left!=null)
                    queue.offer(root.left);
                if(root.right!=null)
                    queue.offer(root.right);
            }
            System.out.println(sb.toString().trim());
        }

        @Override
        public int BTreeDepth(TreeNode treeNode) {
            if(treeNode==null)
                return 0;
            int depLeft=BTreeDepth(treeNode.left);
            int depRight=BTreeDepth(treeNode.right);
            return depLeft > depRight ? depLeft+1 : depRight+1;
        }

       //不一定正确
        @Override
        public void clearBTree(TreeNode treeNode) {
            treeNode=null;
        }

//####################################################################
    /**
     * 叶子节点个数
     */
    private int count=0;

    /**
     * 统计叶子节点个数
     */
    @Override
    public int countLeaf(TreeNode root){
        if(root==null)
            return 0;
        if(root.getLeft()==null && root.getRight()==null){
            count++;
        }
        countLeaf(root.getLeft());
        countLeaf(root.getRight());
        return count;
    }

    /**
     * 交换左右子树
     */
    @Override
    public TreeNode swapSubLeftTreeAndRightTree(TreeNode root){
        if(root==null)
            return null;
        //交换左右子树
        TreeNode leftTree=root.getLeft();
        root.setLeft(root.getRight());
        root.setRight(leftTree);

        swapSubLeftTreeAndRightTree(root.getLeft());
        swapSubLeftTreeAndRightTree(root.getRight());
        return root;
    }
    }

    /**
     * 二叉树结点
     */
    static class TreeNode {
        private TreeNode left;
        private TreeNode right;
        private int data;
        /**
         * 构造节点
         * @param data
         */
        public TreeNode(int data) {
            this.data = data;
            this.left=null;
            this.right=null;
        }
        public TreeNode(){}

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

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

        public Integer getData() {
            return data;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "left=" + left +
                    ", right=" + right +
                    ", data=" + data +
                    '}';
        }
    }
}

结果：


image.png
最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 216,919评论 6赞 502
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 92,567评论 3赞 392
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 163,316评论 0赞 353
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 58,294评论 1赞 292
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 67,318评论 6赞 390
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 51,245评论 1赞 299
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,120评论 3赞 418
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,964评论 0赞 275
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 45,376评论 1赞 313
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,592评论 2赞 333
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,764评论 1赞 348
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 35,460评论 5赞 344
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,070评论 3赞 327
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,697评论 0赞 22
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,846评论 1赞 269
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 47,819评论 2赞 370
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 44,665评论 2赞 354