1 前序

//前序线索化二叉树 public void threadedPreNode(HeroNode 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) { threadedPreNode(node.getLeft()); } //线索化右子树 if (node.getRightType() != 1) { threadedPreNode(node.getRight()); } } //前序线索化遍历 public void threadedPreList() { //定义一个变量，存储当前遍历的结点，从root开始 HeroNode node = root; while (node != null) { //打印当前这个结点 System.out.println(node); 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(); } }

2 后序

2.1 为节点添加父节点

2.1.1 节点中创建方法

//前序遍历添加父节点 public void preOrderAddPar() { while (this.getLeft() != null) { this.getLeft().setParent(this); break; } while (this.getRight() != null) { this.getRight().setParent(this); break; } if (this.getLeft() != null) {//2.向左遍历 this.getLeft().preOrderAddPar(); } if (this.getRight() != null) {//3.向右遍历 this.getRight().preOrderAddPar(); } }

2.1.2 二叉树中创建方法

//前序遍历添加父节点 public void preOrderAddPar() { if (this.root != null) { this.root.preOrderAddPar(); } else { System.out.println("二叉树为空"); } }

2.2 后序线索化及遍历

//后序线索化二叉树 8,10,3,14,6,1 public void threadedPostNode(HeroNode node) { if (node == null) { return; } //线索化左子树 threadedPostNode(node.getLeft()); //线索化右子树 threadedPostNode(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 threadedPostList() {//8,10,3,14,6,1 HeroNode node = root; while(node != null && node.getLeftType()!=1) { node = node.getLeft(); } HeroNode pre = null; while(node != null) { //右节点是线索 if (node.getRightType() == 1) { System.out.println(node); pre = node; node = node.getRight(); } else { //如果上个处理的节点是当前节点的右节点 if (node.getRight() == pre) { System.out.println(node); if (node == root) { return; } pre = node; node = node.getParent(); } else { //如果从左节点的进入则找到有子树的最左节点 node = node.getRight(); while (node != null && node.getLeftType() !=1) { node = node.getLeft(); } } } } }

3 中序

//重载中序线索化二叉树 public void threadedNode() { threadedNode(root); } //中序遍历线索化二叉树的方法 public void threadedList() { //定义一个变量，存储当前遍历的结点，从root开始 HeroNode node = root; while (node != null) { //循环的找到leftType == 1的结点，第一个找到就是8结点 //后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化 //处理后的有效结点 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(); } } //中序线索化二叉树 public void threadedNode(HeroNode node) { if (node == null) { return; } //线索化左子树 threadedNode(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; //线索化右子树 threadedNode(node.getRight()); }

4 完整代码

package edu.seu.demo10tree.demothreadedbinarytree; public class Demo01ThreadedBinaryTree { public static void main(String[] args) { //测试一把中序线索二叉树的功能 HeroNode root = new HeroNode(1, "tom"); HeroNode node2 = new HeroNode(3, "jack"); HeroNode node3 = new HeroNode(6, "smith"); HeroNode node4 = new HeroNode(8, "mary"); HeroNode node5 = new HeroNode(10, "king"); HeroNode node6 = new HeroNode(14, "dim"); //二叉树，后面我们要递归创建, 现在简单处理使用手动创建 root.setLeft(node2); root.setRight(node3); node2.setLeft(node4); node2.setRight(node5); node3.setLeft(node6); ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree(); threadedBinaryTree.setRoot(root); //为节点遍历添加父节点 threadedBinaryTree.preOrderAddPar(); // 中序 8, 3, 10, 1, 14, 6 /* threadedBinaryTree.threadedNode(); HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println("10号结点的前驱结点是=" + leftNode); //3 System.out.println("10号结点的后继结点是=" + rightNode); //1 System.out.println("使用线索化的方式遍历 线索化二叉树"); threadedBinaryTree.threadedList();*/ // 前序 1,3,8,10,6,14 /* threadedBinaryTree.threadedPreNode(root); HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println("10号结点的前驱结点是=" + leftNode); System.out.println("10号结点的后继结点是=" + rightNode); System.out.println("使用线索化的方式遍历 线索化二叉树"); threadedBinaryTree.threadedPreList();*/ //后序8,10,3,14,6,1 threadedBinaryTree.threadedPostNode(root); HeroNode leftNode = node5.getLeft(); HeroNode rightNode = node5.getRight(); System.out.println("10号结点的前驱结点是=" + leftNode); System.out.println("10号结点的后继结点是=" + rightNode); System.out.println("使用线索化的方式遍历 线索化二叉树"); threadedBinaryTree.threadedPostList(); } } class HeroNode { private int no;//英雄编号 private String name;//姓名 private HeroNode left;//左子节点 private HeroNode right;//右子节点 private HeroNode parent;//父节点 private int rightType;//表示右子节点：指针：0，后继：1 private int leftType;//表示左子节点：指针：0 前驱：1 public HeroNode getParent() { return parent; } public void setParent(HeroNode parent) { this.parent = parent; } public int getRightType() { return rightType; } public void setRightType(int rightType) { this.rightType = rightType; } public int getLeftType() { return leftType; } public void setLeftType(int leftType) { this.leftType = leftType; } public HeroNode(int no, String name) { this.no = no; this.name = name; } //读取与设置私有变量 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 HeroNode getLeft() { return left; } public void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() { return right; } public void setRight(HeroNode right) { this.right = right; } //打印输出 @Override public String toString() { return "HeroNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } //前序遍历添加父节点 public void preOrderAddPar() { while (this.getLeft() != null) { this.getLeft().setParent(this); break; } while (this.getRight() != null) { this.getRight().setParent(this); break; } if (this.getLeft() != null) {//2.向左遍历 this.getLeft().preOrderAddPar(); } if (this.getRight() != null) {//3.向右遍历 this.getRight().preOrderAddPar(); } } //前序遍历 public void preOrder() { System.out.println(this);//1.输出父节点 if (this.getLeft() != null) {//2.向左遍历 this.getLeft().preOrder(); } if (this.getRight() != null) {//3.向右遍历 this.getRight().preOrder(); } } //中序遍历 public void infixOrder() { if (this.getLeft() != null) { this.getLeft().infixOrder(); } System.out.println(this); if (this.getRight() != null) {//3.向右遍历 this.getRight().infixOrder(); } } //后序遍历 public void postOrder() { if (this.getLeft() != null) { this.getLeft().postOrder(); } if (this.getRight() != null) {//3.向右遍历 this.getRight().postOrder(); } System.out.println(this); } //前序遍历查找 public HeroNode preOrderSearch(int no) { System.out.println("前序查找比较次数"); if (this.getNo() == no) { return this; } HeroNode resHero = null; if (this.left != null) { resHero = this.left.preOrderSearch(no); } if (resHero != null) { return resHero; } if (this.right != null) { resHero = this.right.preOrderSearch(no); } return resHero; } //中序遍历查找 public HeroNode infixOrderSearch(int no) { HeroNode resHero = null; if (this.left != null) { resHero = this.left.infixOrderSearch(no); } if (resHero != null) { return resHero; } System.out.println("中序查找比较次数"); if (this.getNo() == no) { return this; } if (this.right != null) { resHero = this.right.infixOrderSearch(no); } return resHero; } //后序遍历查找 public HeroNode postOrderSearch(int no) { HeroNode resHero = null; if (this.left != null) { resHero = this.left.postOrderSearch(no); } if (resHero != null) { return resHero; } if (this.right != null) { resHero = this.right.postOrderSearch(no); } if (resHero != null) { return resHero; } System.out.println("后序查找比较次数"); if (this.getNo() == no) { return this; } return resHero; } //删除节点 public void delHeroNode(int no) { if (this.left != null && this.left.getNo() == no) { this.left = null; return; } if (this.right != null && this.right.getNo() == no) { this.right = null; return; } if (this.left != null) { this.left.delHeroNode(no); } if (this.right != null) { this.right.delHeroNode(no); } } } class ThreadedBinaryTree { private HeroNode root;//根节点 private HeroNode pre = null; public ThreadedBinaryTree() { } public HeroNode getRoot() { return root; } public void setRoot(HeroNode root) { this.root = root; } //重载中序线索化二叉树 public void threadedNode() { threadedNode(root); } //中序遍历线索化二叉树的方法 public void threadedList() { //定义一个变量，存储当前遍历的结点，从root开始 HeroNode node = root; while (node != null) { //循环的找到leftType == 1的结点，第一个找到就是8结点 //后面随着遍历而变化,因为当leftType==1时，说明该结点是按照线索化 //处理后的有效结点 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(); } } //中序线索化二叉树 public void threadedNode(HeroNode node) { if (node == null) { return; } //线索化左子树 threadedNode(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; //线索化右子树 threadedNode(node.getRight()); } //后序线索化二叉树 8,10,3,14,6,1 public void threadedPostNode(HeroNode node) { if (node == null) { return; } //线索化左子树 threadedPostNode(node.getLeft()); //线索化右子树 threadedPostNode(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 threadedPostList() {//8,10,3,14,6,1 HeroNode node = root; while(node != null && node.getLeftType()!=1) { node = node.getLeft(); } HeroNode preNode = null; while(node != null) { //右节点是线索 if (node.getRightType() == 1) { System.out.println(node); preNode = node; node = node.getRight(); } else { //如果上个处理的节点是当前节点的右节点 if (node.getRight() == preNode) { System.out.println(node); if (node == root) { return; } preNode = node; node = node.getParent(); } else { //如果从左节点的进入则找到有子树的最左节点 node = node.getRight(); while (node != null && node.getLeftType() !=1) { node = node.getLeft(); } } } } } //前序线索化二叉树 public void threadedPreNode(HeroNode 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) { threadedPreNode(node.getLeft()); } //线索化右子树 if (node.getRightType() != 1) { threadedPreNode(node.getRight()); } } //前序线索化遍历 public void threadedPreList() { //定义一个变量，存储当前遍历的结点，从root开始 HeroNode node = root; while (node != null) { //打印当前这个结点 System.out.println(node); 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(); } } //前序遍历添加父节点 public void preOrderAddPar() { if (this.root != null) { this.root.preOrderAddPar(); } else { System.out.println("二叉树为空"); } } //前序遍历 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 HeroNode preOrderSearch(int no) { if (root != null) { return root.preOrderSearch(no); } else { return null; } } //中序遍历查找 public HeroNode infixOrderSearch(int no) { if (root != null) { return root.infixOrderSearch(no); } else { return null; } } //后序遍历查找 public HeroNode postOrderSearch(int no) { if (root != null) { return this.root.postOrderSearch(no); } else { return null; } } //删除节点 public void delHeroNode(int no) { if (root != null) { if (root.getNo() == no) { root = null; } else { root.delHeroNode(no); } } else { System.out.println("二叉树为空"); } } }