您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

线索化二叉树(图文)

第十三双眼睛2023-10-19【数据结构与算法】人已围观

简介线索化二叉树

线索化二叉树
package com.xingchen.day009;
public class ThreadedBinTree {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1,"1");
        HeroNode heroNode2 = new HeroNode(3,"3");
        HeroNode heroNode3 = new HeroNode(6,"6");
        HeroNode heroNode4 = new HeroNode(8,"8");
        HeroNode heroNode5 = new HeroNode(10,"10");
        HeroNode heroNode6 = new HeroNode(14,"14");
        root.left = heroNode2;
        root.right = heroNode3;
        heroNode2.left = heroNode4;
        heroNode2.right = heroNode5;
        heroNode3.left = heroNode6;
        //开始线索化
        ThreadedTree threadedTree = new ThreadedTree();
        threadedTree.root = root;
        threadedTree.threadedNodes(root);
        HeroNode left = heroNode5.left;
        HeroNode right = heroNode5.right;
        System.out.println(left);
        System.out.println(right);
    }
}
class ThreadedTree {
    public HeroNode root;
    //为了实现线索化，需要创建一个指向当前节点前面节点的指针
    public HeroNode pre;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    //线索化
    public void threadedNodes(HeroNode node) {
        if(node == null) {
            return;
        }
        //先线索化左子树
        threadedNodes(node.left);
        //线索化当前节点
        if (node.left == null) {
            node.left = pre;
            node.leftType = 1;
        }
        // 让前驱节点的右指针指向当前节点
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType=1;
        }
        //移动辅助节点
        pre = node;
        //先说化右子树
        threadedNodes(node.right);
    }
    public void preOrder () {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    public void delNode(int no) {
        if (root != null) {
            if (root.no == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("空树，无法删除");
        }
    }
}
class HeroNode {
    public int no;
    public String name;
    public HeroNode left;
    public HeroNode right;
    public int leftType;//如果是0表示指向子树，如果是1，表示指向前驱节点
    public int rightType;////如果是0表示指向子树，如果是1，表示指向后继节点
    public HeroNode(int no,String name) {
        this.no = no;
        this.name = name;
    }
    public void preOrder() {
        System.out.println(this);
        //递归左子树
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归右子树
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    public void infixOrder() {
        //先递归左子树
        if (this.left!= null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        //递归右子树
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroNode res = null;
        if (this.left != null) {
            res = this.left.preOrderSearch(no);
        }
        if (res != null) {
            return res;
        }
        if (this.right != null) {
            res = this.right.preOrderSearch(no);
        }
        return res;
    }
    public HeroNode infixOrderSearch(int no) {
        HeroNode res = null;
        if (this.left != null) {
            res = this.left.infixOrderSearch(no);
        }
        if (res.no == no) {
            return res;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            res = this.right.infixOrderSearch(no);
        }
        return res;
    }
    public HeroNode postOrderSearch(int no) {
        HeroNode res = null;
        if (this.left != null) {
            res = this.left.postOrderSearch(no);
        }
        if (res != null) {
            return res;
        }
        if (this.right != null) {
            res = this.right.postOrderSearch(no);
        }
        if (res != null) {
            return res;
        }
        //如果左右子树都没有找到,就比较当前节点
        if (this.no == no) {
            return this;
        }
        return null;
    }
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "name='" + name + '\'' +
                '}';
    }
}

线索化二叉树的遍历
package com.xingchen.day009;
public class ThreadedBinTree {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1,"1");
        HeroNode heroNode2 = new HeroNode(3,"3");
        HeroNode heroNode3 = new HeroNode(6,"6");
        HeroNode heroNode4 = new HeroNode(8,"8");
        HeroNode heroNode5 = new HeroNode(10,"10");
        HeroNode heroNode6 = new HeroNode(14,"14");
        root.left = heroNode2;
        root.right = heroNode3;
        heroNode2.left = heroNode4;
        heroNode2.right = heroNode5;
        heroNode3.left = heroNode6;
        //开始线索化
        ThreadedTree threadedTree = new ThreadedTree();
        threadedTree.root = root;
        //threadedTree.threadedNodes(root);
        HeroNode left = heroNode5.left;
        HeroNode right = heroNode5.right;
        //System.out.println(left);
        //System.out.println(right);
        //threadedTree.list();
        //threadedTree.infixOrder();
    }
}
class ThreadedTree {
    public HeroNode root;
    //为了实现线索化，需要创建一个指向当前节点前面节点的指针
    public HeroNode pre;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    public void list() {
        HeroNode node = root;
        while (node != null){
            //先找到leftType为1的节点
            while (node.leftType == 0){
                node = node.left;
            }
            System.out.println(node);
            while (node.rightType == 1) {
                node = node.right;
                System.out.println(node);
            }
            node = node.right;
        }
    }
    //线索化
    public void threadedNodes(HeroNode node) {
        if(node == null) {
            return;
        }
        //先线索化左子树
        threadedNodes(node.left);
        //线索化当前节点
        if (node.left == null) {
            node.left = pre;
            node.leftType = 1;
        }
        // 让前驱节点的右指针指向当前节点
        if (pre != null && pre.right == null) {
            pre.right = node;
            pre.rightType=1;
        }
        //移动辅助节点
        pre = node;
        //先说化右子树
        threadedNodes(node.right);
    }
    public void preOrder () {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空");
        }
    }
    public void delNode(int no) {
        if (root != null) {
            if (root.no == no) {
                root = null;
            } else {
                root.delNode(no);
            }
        } else {
            System.out.println("空树，无法删除");
        }
    }
}
class HeroNode {
    public int no;
    public String name;
    public HeroNode left;
    public HeroNode right;
    public int leftType;//如果是0表示指向子树，如果是1，表示指向前驱节点
    public int rightType;////如果是0表示指向子树，如果是1，表示指向后继节点
    public HeroNode(int no,String name) {
        this.no = no;
        this.name = name;
    }
    public void preOrder() {
        System.out.println(this);
        //递归左子树
        if (this.left != null) {
            this.left.preOrder();
        }
        //递归右子树
        if (this.right != null) {
            this.right.preOrder();
        }
    }
    public void infixOrder() {
        //先递归左子树
        if (this.left!= null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        //递归右子树
        if (this.right != null) {
            this.right.infixOrder();
        }
    }
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }
    public HeroNode preOrderSearch(int no) {
        if (this.no == no) {
            return this;
        }
        HeroNode res = null;
        if (this.left != null) {
            res = this.left.preOrderSearch(no);
        }
        if (res != null) {
            return res;
        }
        if (this.right != null) {
            res = this.right.preOrderSearch(no);
        }
        return res;
    }
    public HeroNode infixOrderSearch(int no) {
        HeroNode res = null;
        if (this.left != null) {
            res = this.left.infixOrderSearch(no);
        }
        if (res.no == no) {
            return res;
        }
        if (this.no == no) {
            return this;
        }
        if (this.right != null) {
            res = this.right.infixOrderSearch(no);
        }
        return res;
    }
    public HeroNode postOrderSearch(int no) {
        HeroNode res = null;
        if (this.left != null) {
            res = this.left.postOrderSearch(no);
        }
        if (res != null) {
            return res;
        }
        if (this.right != null) {
            res = this.right.postOrderSearch(no);
        }
        if (res != null) {
            return res;
        }
        //如果左右子树都没有找到,就比较当前节点
        if (this.no == no) {
            return this;
        }
        return null;
    }
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }
    @Override
    public String toString() {
        return "HeroNode{" +
                "name='" + name + '\'' +
                '}';
    }
}

Tags：

很赞哦！ ()

上一篇：顺序存储二叉树(图文)

下一篇：堆排序(图文)

相关文章

随机图文

文章评论

    共有条评论来说两句吧...

    用户名:

    验证码:

点击排行

前缀，中缀，后缀表达式(图文)

本站推荐

标签云

猜你喜欢

站点信息

  • 网站名称：JavaStudy
  • 建站时间：2019-1-14
  • 网站程序：帝国CMS7.5
  • 文章统计：242篇文章
  • 标签管理：标签云
  • 统计数据：百度统计
  • 微信公众号：扫描二维码，关注我们