(目录)

1 二叉树后序线索化与后序线索化遍历

本文介绍了二叉树后序线索化与后序线索化遍历。

1.1 后序线索化二叉树

//后序线索化二叉树 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; }

1.2 后序遍历线索化二叉树的方法

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(); } } } } }