class ThreadedBinaryTree{
private Node root;
private Node pre=null;
public void setRoot(Node root) {
this.root = root;
}
public void threadNodes(){
this.threadedNodes(root);
}
//中序線索化
public void threadedNodes(Node node){
if(node==null)
return;
threadedNodes(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;
threadedNodes(node.getRight());
}
//前序線索化
public void threadedNodesPre(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()==0)
threadedNodes(node.getLeft());
if(node.getRightType()==0)
threadedNodes(node.getRight());
}
//后序線索化
public void threadedNodesPost(Node node){
if(node==null)
return;
if(node.getLeftType()==0)
threadedNodes(node.getLeft());
if(node.getRightType()==0)
threadedNodes(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;
}
}
Node節(jié)點類添加了:
private int leftType;//0表示指向左子樹户辞,1表示指向前驅(qū)節(jié)點
private int rightType;//0表示指向右子樹,1表示指向后繼節(jié)點
public int getLeftType() {
return leftType;
}
public int getRightType() {
return rightType;
}
public void setLeftType(int leftType) {
this.leftType = leftType;
}
public void setRightType(int rightType) {
this.rightType = rightType;
}
遍歷中序線索化二叉樹
//遍歷中序線索化二叉樹
public void threadedList(){
Node 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();
}
}
優(yōu)勢
(1)利用線索二叉樹進(jìn)行中序遍歷時癞谒,不必采用堆棧處理底燎,速度較一般二叉樹的遍歷速度快,且節(jié)約存儲空間
(2)任意一個結(jié)點都能直接找到它的前驅(qū)和后繼結(jié)點
不足
(1)結(jié)點的插入和刪除麻煩扯俱,且速度也較慢
(2)線索子樹不能共用
https://baike.baidu.com/item/%E7%BA%BF%E7%B4%A2%E4%BA%8C%E5%8F%89%E6%A0%91/10810037?fr=aladdin