中序遍历线索化二叉树
- 说明:对前面的中序线索化的二叉树, 进行遍历
- 分析:因为线索化后,各个结点指向有变化,因此原来的遍历方式不能使用,这时需要使用新的方式遍历线索化二叉树,各个节点可以通过线型方式遍历,因此无需使用递归方式,这样也提高了遍历的效率。 遍历的次序应当和中序遍历保持一致。
代码实现
package com.iflytek.tree;public class ThreadBinaryTreeDemo { public static void main(String[] args) { HeroNode2 root = new HeroNode2(1, "tom"); HeroNode2 node2 = new HeroNode2(3, "jack"); HeroNode2 node3 = new HeroNode2(6, "smith"); HeroNode2 node4 = new HeroNode2(8, "mary"); HeroNode2 node5 = new HeroNode2(10, "king"); HeroNode2 node6 = new HeroNode2(14, "dim"); root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadBinaryTree threadedBinaryTree = new ThreadBinaryTree(); threadedBinaryTree.setRoot(root); threadedBinaryTree.infixThreadBidNodes(); System.out.println("node5 = " + node5); System.out.println("10 号结点的前驱结点是 =" + node5.getLeft()); System.out.println("10 号结点的后继结点是=" + node5.getRight()); threadedBinaryTree.infixThreadList(threadedBinaryTree.getRoot()); }}class ThreadBinaryTree { private HeroNode2 root; private HeroNode2 pre = null; public void setRoot(HeroNode2 root) { this.root = root; } public HeroNode2 getRoot() { return root; } public void infixThreadBidNodes() { this.infixThreadBiNodes(root); } public void preThreadBidNodes() { this.preThreadBiNodes(root); } public void postThreadBiNodes() { this.postThreadBiNodes(root); } public void infixThreadBiNodes(HeroNode2 node) { if (node == null) { return; } if (node.getLeftType() == 0) { infixThreadBiNodes(node.getLeft()); } 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.getRightType() == 0) { infixThreadBiNodes(node.getRight()); } } public void preThreadBiNodes(HeroNode2 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() == 0) { preThreadBiNodes(node.getLeft()); } if (node.getRightType() == 0) { preThreadBiNodes(node.getRight()); } } public void postThreadBiNodes(HeroNode2 node) { if (node == null) { return; } if (node.getLeftType() == 0) { postThreadBiNodes(node.getLeft()); } if (node.getRightType() == 0) { postThreadBiNodes(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; } public void infixThreadList(HeroNode2 root) { HeroNode2 node = root; while (node != null) { while (node.getLeftType() == 0) { node = node.getLeft(); } System.out.println(node); while (node.getRightType() == 1) { node = node.getRight(); System.out.println(node); } node = node.getRight(); } }}class HeroNode2 { private int no; private String name; private HeroNode2 left; private HeroNode2 right; private int leftType; private int rightType; public int getNo() { return no; } public void setNo(int no) { this.no = no; } public String getName() { return name; } public void setName(String name) { this.name = name; } public HeroNode2 getLeft() { return left; } public void setLeft(HeroNode2 left) { this.left = left; } public HeroNode2 getRight() { return right; } public void setRight(HeroNode2 right) { this.right = right; } public int getLeftType() { return leftType; } public void setLeftType(int leftType) { this.leftType = leftType; } public int getRightType() { return rightType; } public void setRightType(int rightType) { this.rightType = rightType; } public HeroNode2(int no, String name) { this.no = no; this.name = name; } @Override public String toString() { return "HeroNode2{" + "no=" + no + ", name='" + name + '\'' + ", leftType=" + leftType + ", rightType=" + rightType + '}'; }}
字库吧