数据结构线索二叉树怎么画,如何实现线索化二叉树?

　　00-1010 1.线索二叉树介绍2。线索二叉树的基本特征3。线索二叉树的应用案例4。预线程二叉树和遍历5。后线程二叉树。

　　00-1010将序列{1，3，6，8，10，14}构造成二叉树。

　　问题3360分析

　　1.当我们以中间顺序遍历上述二叉树时，序列是{8，3，10，1，6，14}

　　2.然而，节点6、8、10和14的左右指针没有被完全利用。

　　3.如果我们要充分利用每个节点的左右指针，让每个节点都能指向自己的前后节点呢？

　　4.解答线索二叉树

　　概念：用二叉链表作为二叉树的存储结构时，你可以很容易地找到某个节点的左右子；但一般情况下，在某个遍历序列中，这个节点的前任和后继节点是无法直接找到的。所以使用了clue，二叉树链表的空指针字段用于clue。

目录

n个节点的二进制链表包含n ^ 1个[公式2n-(n-1)=n ^ 1]空指针字段。使用二叉链表中的空指针字段，以一定的遍历顺序存储指向该节点的前一个和后一个节点的指针(这个额外的指针称为‘clue’)。

　　这种有线索的二元链表称为线索链表，对应的二叉树称为线索二叉树。根据线索的性质，线索二叉树可以分为三种类型：前序线索二叉树、中序线索二叉树和后序线索二叉树。

　　00-1010中序线索二叉树及其遍历

　　案例描述：下面的二叉树将作为中序线索二叉树。以中间顺序遍历的序列是{8，3，10，1，14，6}

　　思维分析

　　中间顺序遍历的结果：{8，3，10，1，14，6}

　　然后线程二叉树的左右指针见上图。

　　:二叉树被线程化时，节点左右的属性如下：3360

　　Left指向左边的子树或前任节点。比如 node left指向左边的子树， node left指向前任节点。right指向右边的子树或后续节点。比如节点右指向右边的子树，节点右指向后继节点。所以要改变原来二叉树的节点结构。

　　包com . study self . tree . threaded binary tree；/* * * @ author Wang * @ version 1.0 * @ package name com . study self . tree 01 * @ class name Node * @ date 2022/4/19 20336015 * @ description Node */public class Node {//Unique number private int num；//节点私有字符串名称的值；//左节点私有节点left；//右节点私有节点右；//该属性用于控制线索二叉树节点的指向。0表示指向左侧节点，1表示指向正向节点private int leftType//该属性用于控制线索二叉树节点的指向。0表示指向右边的节点，1表示指向后续节点的private int rightType//构造方法公共节点(intnum，string name){ this . num=num；this.name=name} public int get left type(){ return left type；} public void set left type(int left type){ this . left type=left type；} public int getRightType(){ return right type；} public void setRightType(int right type){ this . right type=right type；} public int getNum(){ return num；} public void setNum(int num){ this . num=num；}公共字符串getNam

　　e() { return name; } public void setName(String name) { this.name = name; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } @Override public String toString() { return "Node{" + "num=" + num + ", name=" + name + }; } /** * 前序遍历 */ public void preSelect() { //首先输出根结点 System.out.println(this); //其次判断是否有左结点 if (this.left != null) { //没有左结点，就递归调用本方法输出该结点。 this.left.preSelect(); } if (this.right != null) { this.right.preSelect(); } } /** * 中序遍历 */ public void infixSelect() { //首先判断左结点 if (this.left != null) { //如果左结点不为空，递归向左子树调用 this.left.infixSelect(); } //当左结点为空，再输出根结点。当他本身就是最后一个左结点的时候，会直接输出，且没有右节点 System.out.println(this); if (this.right != null) { //右节点同样如此，递归调用。直到没有结点为止。 this.right.infixSelect(); } } /** * 设二叉树有三个结点，根结点，左结点，右节点。 * 后序遍历,解释，当一个二叉树的左结点不为空，那么他会进入下一个递归调用自己的后序遍历方法 * 此时，根结点就是左结点，这时判断左结点，右节点均为空，就会输出左结点 * 回退到根结点为this的时候，左结点已经判断完毕，接下来是右节点，右节点不为空，进入后续遍历递归， * 此时的this就是右节点，进入递归后，判断，不存在左右结点，输出this，也就是整个二叉树的右节点 * 回退到this为根结点时，右节点也已经输出，走到最后一步，输出自己也就是this。 * 整个后序遍历就结束，那么该二叉树的遍历结果就是左，右，根 */ public void afterSelect() { if (this.left != null) { this.left.afterSelect(); } if (this.right != null) { this.right.afterSelect(); } System.out.println(this); } /** * @param num * @Date 2022/4/21 17:51 * @Param * @Return Node * @MetodName preSearchByNum * @Author wang * @Description 根据结点的编号来查询结点, 前序遍历查询，根，左，右 */ public Node preSearchByNum(int num) { //首先判断传进来的num与该结点的num是否相等 //如果相等，那该结点就是我们要找的结点。 if (this.num == num) { return this; } //如果不相等，该结点就不是我们要找的结点 //那么我们就遍历该结点的左子节点，和右子结点 //定义一个结点用于接收最后的返回结果 Node resultNode = null; //如果该结点的左子结点不为空，就递归调用前序遍历，继续查找，如果找到了，那么resultNode就是我们想要的值 if (this.left != null) { resultNode = this.left.preSearchByNum(num); } //如果遍历完左子结点，已经找到了我们想要的结果，直接返回结果即可， if (resultNode != null) { return resultNode; } //如果左子结点为空，且没有找到我们想要的结点的情况下。那就判断右子结点 if (this.right != null) { resultNode = this.right.preSearchByNum(num); } //最后，如果找到了，那么resultNode一定会被赋值，如果没找到，就会返回null return resultNode; } /** * @param num * @Date 2022/4/21 17:58 * @Param * @Return Node * @MetodName infixSearchByNum * @Author wang * @Description 中序遍历查找，左，根，右进行查询即可。 */ public Node infixSearchByNum(int num) { //首先判断左子结点,如果存在左子结点，递归继续查询遍历即可即可。 Node resultNode = null; if (this.left != null) { resultNode = this.left.infixSearchByNum(num); } //如果左子结点已经找到了我们想要的结点，直接返回当前结点即可 if (resultNode != null) { return resultNode; } //判断根结点 if (this.num == num) { return this; } //判断右子结点， if (this.right != null) { resultNode = this.right.infixSearchByNum(num); } //最后返回我们的结果即可。 return resultNode; } /** * @param num * @Date 2022/4/21 19:15 * @Param * @Return Node * @MetodName afterSearchNum * @Author wang * @Description 后续遍历结点进行查找结点。左，右，根 */ public Node afterSearchNum(int num) { Node resultNode = null; //首先遍历左结点 if (this.left != null) { resultNode = this.left.afterSearchNum(num); } //判断左结点是否找到哦啊 if (resultNode != null) { return resultNode; } //判断右节点是否为空 if (this.right != null) { resultNode = this.right.afterSearchNum(num); } //判断右节点是否找到 if (resultNode != null) { return resultNode; } //判断根结点是否为我们找的结点 if (this.num == num) { return this; } //最后返回 return resultNode; } /** * @param num * @Date 2022/4/25 19:30 * @Param * @Return void * @MetodName delNodeByNum * @Author wang * @Description 根据结点的编号删除结点 */ public void delNodeByNum(int num) { //首先，判断当前结点的左结点是否为空，并且左结点的num是否与num相等 if (this.left != null && this.left.num == num) { //如果相等，那就说明该结点就是我们要删除的结点,将其左结点置空即可 this.left = null; return; } //如果左结点没有执行，说明左结点没有我们想要的结果，也就是要删除的结点不在左结点 //那么就对右节点进行判断 if (this.right != null && this.right.num == num) { this.right = null; return; } //如果左右结点均没有找到目标结点 //那么就对左子树进行递归删除操作 if (this.left != null) { this.left.delNodeByNum(num); } //同理，如果左子树没有目标结点，向右子树进行递归删除操作 if (this.right != null) { this.right.delNodeByNum(num); } }}可以看到我们多出来了这么两个属性：

 //这个属性用来控制线索二叉树的结点的指向，0代表指向左结点，1代表指向前趋结点 private int leftType; //这个属性用来控制线索二叉树的结点的指向，0代表指向右结点，1代表指向后继结点 private int rightType;

中序线索化二叉树

 /**中序线索化二叉树*/ /** * @param node 该结点为根结点，从根节点开始线索化二叉树，中序 */ public void infixThreadNodes(Node node) { /**首先判断二叉树的根节点上会否为空，如果根结点为空，不可以线索化，因为没有二叉树*/ if (node == null) { return; } /**接着对左子树进行线索化*/ infixThreadNodes(node.getLeft()); /**对当前结点进行线索化*/ /**首先判断当前结点的左子结点是否为空*/ if (node.getLeft() == null) { //如果左子结点为空，说明就找到了我们需要线索化的结点 //就可以将pre也就是一直在当前结点的前趋结点设置给当前结点的左子结点， //如果这是第一个结点，那么pre为空，正好第一个结点的前趋结点也为空 node.setLeft(pre); //并且将它的左子结点的类型设置为前趋结点。1代表前趋结点 node.setLeftType(1); } /**接着判断前趋结点的右子结点是否为空，前提是前趋结点不能为空，如果他为空，说明这是第一个结点还没走完*/ if (pre != null && pre.getRight() == null) { //如果条件满足，说明前趋结点现在已经走到了值，并且还没有线索到后继结点， // 也就是当前结点的上一个结点（这个上一个结点就是当前的前趋结点）还没有后继， //那么上一个结点的后继结点就是当前结点，因此赋值前趋结点（也就是上一个结点）的后继结点为当前结点。 //这样这条线索就连接上了,并且只有满足叶子结点的结点才可以进行线索化 pre.setRight(node); pre.setRightType(1); } //当前两步走完之后，就可以将pre结点赋值为当前结点， // 因为下一个结点一走，当前结点就是前趋结点了。直到走到全部线索化结束 //这步十分重要，这一步不写，整个线索化就连接不上 pre = node; /**对右子树进行线索化*/ infixThreadNodes(node.getRight()); }

中序线索化二叉树思路

　　因为中序遍历的二叉树顺序是左根右，因此，首先对左子树进行线索化，递归线索化即可；当递归到左子树的最左结点的时候，他的左结点肯定为空，那么就对他的左结点赋值为pre（pre结点是在线索化的最后一步赋值为当前结点，这样递归才能进行下去）,注意左结点的类型一定要改为1，代表他是前趋结点。前趋结点就线索掉了。后继结点的处理则是判断前趋结点，当前趋结点不为空，并且前趋结点的右节点为空，那么设置前趋结点的右节点为当前结点，也就是上一个结点未设置的右节点，类型同样要设置为后继最后就是对pre这个结点赋值，为当前结点，因为下一次递归，当前结点就成了上一个结点，也就是这里的pre最后就是对二叉树的右子结点进行线索化。中序线索化二叉树的遍历

　　遍历中序线索化二叉树首先应该明确的是他的遍历顺序要和遍历原来的中序二叉树遍历的结果是一样的，才是遍历成功那么第一步应该就是判断根结点不为空，也就是循环结束条件接着就循环查找当前结点的左子结点类型为0的也就是没有被线索化的结点，只要他为0，那么结点就一直往左子结点赋值。直到找到第一个被线索化的结点，输出他，他就是我们第一个线索化并且也是中序遍历的第一个左子结点。输出之后，判断他的右子结点是否被线索化，如果被线索化，那么当前结点node就被赋值为它自己的右子结点，并且输出，如果他之后的结点的右子结点的类型又为1，那么继续往后走并赋值，说明他有后继直到右子结点的类型为0，退出循环之后，也应该向右再赋值，继续向后遍历代码演示

 /**遍历中序线索化二叉树*/ public void infixThreadNodesSelect() { /**第一个结点为根结点*/ Node node = root; while(node != null) { /**当结点不为空，就一直遍历*/ /**当该结点的左子结点的类型为1的时候，也就是说该结点是被线索化的结点, * 因为是中序遍历，所以应该遍历到最左边的最左子结点，那么就是第一个 * 左子结点类型为1的结点。*/ while(node.getLeftType() == 0) { node = node.getLeft(); } /**当左子结点的类型为1,输出左子结点*/ System.out.println(node); /**当右子结点类型为1，当前结点输出完毕后 * 中序遍历就应该输出右子结点，那么就是当前结点的右子结点类型只要为1，就往后移动 * 并且输出，当他为0，说明没有线索化，那么没有后继结点，但是他有右子结点， * 因此要在循环结束以后向后移动。*/ while (node.getRightType() == 1) { node = node.getRight(); System.out.println(node); } /**当右子结点循环退出，说明这里到了类型为0也就是后继结点*/ node = node.getRight(); }

4.前序线索化二叉树、遍历

线索化二叉树

 /** * 前序线索化二叉树 */ public void preThreadNodes(Node node) { /**首先判断当前节点是否为空*/ if (node == null) { return; } /**如果是前序遍历，那么先对当前结点进行判断，当前结点的前趋结点的操作*/ if (node.getLeft() == null) { node.setLeft(pre); node.setLeftType(1); } /**处理后继结点,定义的前趋结点不为空，说明他有值，就是已经存在了上一个结点的值，他的右子结点没有值的话，就可以 * 给他赋予后继结点为当前结点，这里赋予的也就是上一个结点*/ if (pre != null && pre.getRight() == null) { pre.setRight(node); pre.setRightType(1); } /**这里是关键的一步*/ pre = node; /**对左子结点进行线索化,注意，这里需要排除已经被线索化掉的结点,因为这里要考虑一个情况， * 比如这里已将到了最下面一个左子结点，由于是前序遍历，遍历到左子结点，他的前趋结点在上面就设置了 * 如果这里不判断左子结点的类型，那么就会进入递归，但是这个递归如果进去了，就是错误的递归，因为他传过去的结点 * 是我们刚刚给他赋值的前趋结点，也就是根结点。会发生错误。因此得判断类型*/ if (node.getLeftType() != 1) { preThreadNodes(node.getLeft()); } /**对右子结点进行递归线索化*/ if (node.getRightType() != 1) { preThreadNodes(node.getRight()); } }

遍历线索化二叉树

/** * 前序遍历线索二叉树*/ public void preThreadNodeSelect() { Node node = root; while(node !=null) { while(node.getLeftType() == 0) { /**前序遍历为根左右，先输出根结点,因为他每次进来循环肯定是先到根结点，所以一进该循环 * 就要输出根结点，当他的lefttype=1循环结束，说明遇到了被线索化的地方了。*/ System.out.println(node); /**再最左子结点进行遍历*/ node = node.getLeft(); } /**上面的循环结束之后就应该输出当前结点，也就是那个序列化的结点 * 之后结点向右移动继续遍历*/ System.out.println(node); node = node.getRight(); } }

图解

5.后序线索化二叉树

后续线索化二叉树

/** * 后序线索化二叉树的方法 */public void postThreadedBinaryTree(Node node) { /**首先判断结店不能为空*/ if (node == null) { return; } /**先后续线索化左子结点*/ postThreadedBinaryTree(node.getLeft()); /**在后续线索化右子结点*/ postThreadedBinaryTree(node.getRight()); /**处理当前结点的前趋结点*/ if (node.getLeft() == null) { node.setLeft(pre); node.setLeftType(1); } /**处理后继结点*/ if (pre != null && pre.getRight() == null) { pre.setRight(node); pre.setRightType(1); } pre = node;}

后续线索化思路类似，只不过将顺序改为了左右根。

　　以上就是Java数据结构之线索化二叉树的实现的详细内容，更多关于Java线索化二叉树的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。