线索化二叉树

亦凉 2024-04-18 21:44 173阅读 0赞

一、问题

将数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树. n+1=7
在这里插入图片描述
问题分析:

  1. 当我们对上面的二叉树进行中序遍历时，数列为{8,3,10,1,6,14}
  2. 但是6,8,10,14这几个节点的左右指针，并没有完全的利用上.
  3. 如果我们希望充分的利用各个节点的左右指针，让各个节点可以指向自己的前后节点,怎么办? 4) 解决方案-线索二叉树

二、线索二叉树基本介绍

  1. n 个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】 个空指针域。利用二叉链表中的空指针域，存放指向
    该结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为”线索”)
  2. 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(ThreadedBinaryTree)。根据线索性质
    的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种
  3. 一个结点的前一个结点，称为前驱结点
  4. 一个结点的后一个结点，称为后继结点

三、线索二叉树应用案例

应用案例说明:将下面的二叉树，进行中序线索二叉树。中序遍历的数列为 {8, 3, 10, 1, 14, 6}
在这里插入图片描述
思路分析: 中序遍历的结果:{8, 3, 10, 1, 14, 6}
在这里插入图片描述
说明: 当线索化二叉树后，Node 节点的 属性 left 和 right ，有如下情况:

  1. left 指向的是左子树，也可能是指向的前驱节点. 比如 1 节点 left 指向的左子树, 而 10 节点的 left 指向的就是前驱节点.
  2. right 指向的是右子树，也可能是指向后继节点，比如 1 节点 right 指向的是右子树，而10 节点的 right 指向的是后继节点.

四、遍历线索化二叉树

  1. 说明:对前面的中序线索化的二叉树， 进行遍历
  2. 分析:因为线索化后，各个结点指向有变化，因此原来的遍历方式不能使用，这时需要使用新的方式遍历 线索化二叉树，各个节点可以通过线型方式遍历，因此无需使用递归方式，这样也提高了遍历的效率。 遍历的次 序应当和中序遍历保持一致。

五、代码实现:

  1. package tree.threadedbinarytree;
  3. /**
  4.  * @program: text
  5.  * @description: 线索二叉树
  6.  * @author: min
  7.  * @create: 2019-09-12 11:14
  8.  **/
  9. public class ThreadedBinaryTreeDemo {
  11.     public static void main(String[] args) {
  12.         HeroNode root = new HeroNode(1, "tom");
  13.         HeroNode node2 = new HeroNode(3, "jack");
  14.         HeroNode node3 = new HeroNode(6, "smith");
  15.         HeroNode node4 = new HeroNode(8, "mary");
  16.         HeroNode node5 = new HeroNode(10, "king");
  17.         HeroNode node6 = new HeroNode(14, "dim");
  19.         //二叉树，后面我们要递归创建, 现在简单处理使用手动创建
  20.         root.setLeft(node2);
  21.         root.setRight(node3);
  22.         node2.setLeft(node4);
  23.         node2.setRight(node5);
  24.         node3.setLeft(node6);
  25.         //测试中序线索化
  26.         ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
  27.         threadedBinaryTree.setRoot(root);
  28.         threadedBinaryTree.threadedNodes();
  29.         //测试: 以 10 号节点测试
  30.         HeroNode leftNode = node5.getLeft();
  31.         HeroNode rightNode = node5.getRight();
  32.         System.out.println("10 号结点的前驱结点是 =" + leftNode); //3
  33.         System.out.println("10 号结点的后继结点是=" + rightNode); //1
  34.         //当线索化二叉树后，能在使用原来的遍历方法
  35.         // threadedBinaryTree.infixOrder();
  36.         System.out.println("使用线索化的方式遍历 线索化二叉树");
  37.         threadedBinaryTree.threadedList(); // 8, 3, 10, 1, 14, 6
  38.     }
  39. }
  41. //定义 ThreadedBinaryTree 实现了线索化功能的二叉树
  42. class ThreadedBinaryTree {
  43.     private HeroNode root;
  44.     //为了实现线索化，需要创建要给指向当前结点的前驱结点的指针
  45.     // 在递归进行线索化时，pre 总是保留前一个结点
  46.     private HeroNode pre = null;
  48.     public void setRoot(HeroNode root) {
  49.         this.root = root;
  50.     }
  52.     //重载一把 threadedNodes 方法
  53.     public void threadedNodes() {
  54.         this.threadedNodes(root);
  55.     }
  57.     //遍历线索化二叉树的方法
  58.     public void threadedList() {
  60.         //定义一个变量，存储当前遍历的结点，从 root 开始
  61.         HeroNode node = root;
  62.         while (node != null) {
  63.             //循环的找到 leftType == 1 的结点，第一个找到就是 8 结点
  64.             // 后面随着遍历而变化,因为当 leftType==1 时，说明该结点是按照线索化
  65.             // 处理后的有效结点
  66.             while (node.getLeftType() == 0) {
  67.                 node = node.getLeft();
  68.             }
  69.             //打印当前这个结点
  70.             System.out.println(node);
  71.             //如果当前结点的右指针指向的是后继结点,就一直输出
  72.             while (node.getRightType() == 1) {
  73.                 //获取到当前结点的后继结点
  74.                 node = node.getRight();
  75.                 System.out.println(node);
  76.             } //替换这个遍历的结点
  77.             node = node.getRight();
  78.         }
  79.     }
  81.     // 二叉树进行中序线索化
  82.     public void threadedNodes(HeroNode node) {
  83.         //如果 node==null, 不能线索化
  84.         if (node == null) {
  85.             return;
  86.         }
  88.         //(一)先线索化左子树
  89.         threadedNodes(node.getLeft());
  90.         //(二)线索化当前结点[有难度]
  91.         //处理当前结点的前驱结点
  92.         //以 8 结点来理解
  93.         //8 结点的.left = null , 8 结点的.leftType = 1
  94.         if (node.getLeft() == null) {
  95.             //让当前结点的左指针指向前驱结点
  96.             node.setLeft(pre);
  97.             //修改当前结点的左指针的类型,指向前驱结点
  98.             node.setLeftType(1);
  99.         }
  101.         //处理后继结点
  102.         if (pre != null && pre.getRight() == null) {
  103.             //让前驱结点的右指针指向当前结点
  104.             pre.setRight(node);
  105.             //修改前驱结点的右指针类型
  106.             pre.setRightType(1);
  107.         }
  109.         //!!! 每处理一个结点后，让当前结点是下一个结点的前驱结点
  110.         pre = node;
  111.         //(三)在线索化右子树
  112.         threadedNodes(node.getRight());
  114.     }
  116.     //删除结点
  117.     public void delNode(int no) {
  118.         if (root != null) {
  119.             //如果只有一个 root 结点, 这里立即判断 root 是不是就是要删除结点
  120.             if (root.getNo() == no) {
  121.                 root = null;
  122.             } else {
  123.                 //递归删除
  124.                 root.delNode(no);
  125.             }
  126.         } else {
  127.             System.out.println("空树，不能删除~");
  128.         }
  129.     }
  131.     //前序遍历
  132.     public void preOrder() {
  133.         if (this.root != null) {
  134.             this.root.preOrder();
  135.         } else {
  136.             System.out.println("二叉树为空，无法遍历");
  137.         }
  138.     }
  140.     //中序遍历
  141.     public void infixOrder() {
  142.         if (this.root != null) {
  143.             this.root.infixOrder();
  144.         } else {
  145.             System.out.println("二叉树为空，无法遍历");
  146.         }
  147.     }
  149.     //后序遍历
  150.     public void postOrder() {
  151.         if (this.root != null) {
  152.             this.root.postOrder();
  153.         } else {
  154.             System.out.println("二叉树为空，无法遍历");
  155.         }
  156.     }
  158.     //前序遍历
  159.     public HeroNode preOrderSearch(int no) {
  160.         if (root != null) {
  161.             return root.preOrderSearch(no);
  162.         } else {
  163.             return null;
  164.         }
  165.     }
  167.     //中序遍历
  168.     public HeroNode infixOrderSearch(int no) {
  169.         if (root != null) {
  170.             return root.infixOrderSearch(no);
  171.         } else {
  172.             return null;
  173.         }
  174.     }
  176.     //后序遍历
  177.     public HeroNode postOrderSearch(int no) {
  178.         if (root != null) {
  179.             return this.root.postOrderSearch(no);
  180.         } else {
  181.             return null;
  182.         }
  183.     }
  184. }
  186. //先创建 HeroNode 结点
  187. class HeroNode {
  188.     private int no;
  189.     private String name;
  190.     private HeroNode left; //默认 null
  191.     private HeroNode right; //默认 null
  192.     //说明
  193.     //1. 如果 leftType == 0 表示指向的是左子树, 如果 1 则表示指向前驱结点
  194.     //2. 如果 rightType == 0 表示指向是右子树, 如果 1 表示指向后继结点
  195.     private int leftType;
  196.     private int rightType;
  198.     public int getLeftType() {
  199.         return leftType;
  200.     }
  202.     public void setLeftType(int leftType) {
  203.         this.leftType = leftType;
  204.     }
  206.     public int getRightType() {
  207.         return rightType;
  208.     }
  210.     public void setRightType(int rightType) {
  211.         this.rightType = rightType;
  212.     }
  214.     public HeroNode(int no, String name) {
  215.         this.no = no;
  216.         this.name = name;
  217.     }
  219.     public int getNo() {
  220.         return no;
  221.     }
  223.     public void setNo(int no) {
  224.         this.no = no;
  225.     }
  227.     public String getName() {
  228.         return name;
  229.     }
  231.     public void setName(String name) {
  232.         this.name = name;
  233.     }
  235.     public HeroNode getLeft() {
  236.         return left;
  237.     }
  239.     public void setLeft(HeroNode left) {
  240.         this.left = left;
  241.     }
  243.     public HeroNode getRight() {
  244.         return right;
  245.     }
  247.     public void setRight(HeroNode right) {
  248.         this.right = right;
  249.     }
  251.     @Override
  252.     public String toString() {
  253.         return "HeroNode [no=" + no + ", name=" + name + "]";
  254.     }
  255.     //递归删除结点
  256.     //1.如果删除的节点是叶子节点，则删除该节点
  257.     //2.如果删除的节点是非叶子节点，则删除该子树
  258.     public void delNode(int no) {
  259.         //思路
  260.         /** 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断 当前这个结点是不是需要删除结点.
  261.          2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
  262.          3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
  263.          4. 如果第 2 和第 3 步没有删除结点，那么我们就需要向左子树进行递归删除
  264.          5. 如果第 4 步也没有删除结点，则应当向右子树进行递归删除.*/
  265.         //2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将 this.left = null; 并且就返回(结束递归删除)
  266.         if (this.left != null && this.left.no == no) {
  267.             this.left = null;
  268.             return;
  269.         }
  270.         //3.如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将 this.right= null ;并且就返回(结 束递归删除)
  271.         if (this.right != null && this.right.no == no) {
  272.             this.right = null;
  273.             return;
  274.         }
  275.         //4.我们就需要向左子树进行递归删除
  276.         if (this.left != null) {
  277.             this.left.delNode(no);
  278.         }
  279.         //5.则应当向右子树进行递归删除
  280.         if (this.right != null) {
  281.             this.right.delNode(no);
  282.         }
  283.     }
  285.     //编写前序遍历的方法
  286.     public void preOrder() {
  287.         System.out.println(this); //先输出父结点 //递归向左子树前序遍历
  288.         if (this.left != null) {
  289.             this.left.preOrder();
  290.         }
  291.         //递归向右子树前序遍历
  292.         if (this.right != null) {
  293.             this.right.preOrder();
  294.         }
  295.     }
  297.     //中序遍历
  298.     public void infixOrder() {
  299.         //递归向左子树中序遍历
  300.         if (this.left != null) {
  301.             this.left.infixOrder();
  302.         }
  303.         //输出父结点
  304.         System.out.println(this);
  305.         //递归向右子树中序遍历
  306.         if (this.right != null) {
  307.             this.right.infixOrder();
  308.         }
  309.     }
  311.     //后序遍历
  312.     public void postOrder() {
  313.         if (this.left != null) {
  314.             this.left.postOrder();
  315.         }
  316.         if (this.right != null) {
  317.             this.right.postOrder();
  318.         }
  319.         System.out.println(this);
  320.     }
  322.     /**
  323.      * @param no 查找 no
  324.      * @return 如果找到就返回该 Node ,如果没有找到返回 null
  325.      */
  326.     public HeroNode preOrderSearch(int no) {
  327.         System.out.println("进入前序查找"); //比较当前结点是不是
  328.         if (this.no == no) {
  329.             return this;
  330.         }
  331.         //1.则判断当前结点的左子节点是否为空，如果不为空，则递归前序查找
  332.         //2.如果左递归前序查找，找到结点，则返回
  333.         HeroNode resNode = null;
  334.         if (this.left != null) {
  335.             resNode = this.left.preOrderSearch(no);
  336.         }
  337.         if (resNode != null) {//说明我们左子树找到
  338.             return resNode;
  339.         }
  340.         //1.左递归前序查找，找到结点，则返回，否继续判断，
  341.         //2.当前的结点的右子节点是否为空，如果不空，则继续向右递归前序查找
  342.         if (this.right != null) {
  343.             resNode = this.right.preOrderSearch(no);
  344.         }
  345.         return resNode;
  346.     }
  348.     //中序遍历查找
  349.     public HeroNode infixOrderSearch(int no) {
  350.         //判断当前结点的左子节点是否为空，如果不为空，则递归中序查找
  351.         HeroNode resNode = null;
  352.         if (this.left != null) {
  353.             resNode = this.left.infixOrderSearch(no);
  354.         }
  355.         if (resNode != null) {
  356.             return resNode;
  357.         }
  358.         System.out.println("进入中序查找");
  359.         //如果找到，则返回，如果没有找到，就和当前结点比较，如果是则返回当前结点
  360.         if (this.no == no) {
  361.             return this;
  362.         }
  363.         //否则继续进行右递归的中序查找
  364.         if (this.right != null) {
  365.             resNode = this.right.infixOrderSearch(no);
  366.         }
  367.         return resNode;
  368.     }
  370.     //后序遍历查找
  371.     public HeroNode postOrderSearch(int no) {
  372.         //判断当前结点的左子节点是否为空，如果不为空，则递归后序查找
  373.         HeroNode resNode = null;
  374.         if (this.left != null) {
  375.             resNode = this.left.postOrderSearch(no);
  376.         }
  377.         if (resNode != null) {//说明在左子树找到
  378.             return resNode;
  379.         }
  380.         //如果左子树没有找到，则向右子树递归进行后序遍历查找
  381.         if (this.right != null) {
  382.             resNode = this.right.postOrderSearch(no);
  383.         }
  384.         if (resNode != null) {
  385.             return resNode;
  386.         }
  387.         System.out.println("进入后序查找");
  388.         //如果左右子树都没有找到，就比较当前结点是不是
  389.         if (this.no == no) {
  390.             return this;
  391.         }
  392.         return resNode;
  393.     }
  394. }

转载至：尚硅谷_韩顺平_图解Java数据结构和算法.pdf

发表评论

表情：
评论列表 （有 0 条评论，173人围观）

还没有评论，来说两句吧...

相关阅读

    相关 树：线索化二叉树

    1，线索化二叉树基本介绍 线索化二叉树是对普通二叉树的扩展，对于普通二叉树而言，一个节点会包含一个数据域以及指向左右子节点的位置索引；但是对于叶子节点来讲，左右子节

    曾经终败给现在曾经终败给现在/ 0 赞/ 88 阅读

    相关 二叉树线索化算法

    二叉树线索化 简述 为什么需要线索二叉树？ 1. 对于普通的二叉树来说，如果随便给出二叉树中的一个结点，让你从这个结点遍历整个二叉树，这是做不到的（其实对于普通

    向右看齐向右看齐/ 0 赞/ 277 阅读

    相关 线索化二叉树

    二叉树是一种非线性结构，遍历二叉树几乎都是通过递归或者用栈辅助实现非递归的遍历。用二叉树作为存储结构时，取到一个节点，只 能获取节点的左孩子和右孩子，不能直接得到节点的任一遍历

    柔光的暖阳◎柔光的暖阳◎/ 0 赞/ 231 阅读