数据结构_线索化二叉树

﹏ヽ暗。殇╰゛Y 2023-07-11 08:49 23阅读 0赞

*  n个结点的二叉链表中含有`2n-(n-1)=n+1` 个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为"线索"）
 *  这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

public class ThreadedBinaryTree {
        
    	private TreeNode root;
    	private TreeNode pre;
    
    	public ThreadedBinaryTree(TreeNode root) {
        
    		super();
    		this.root = root;
    	}
    
    	/**
    	 * 中序线索化遍历
    	 */
    	public void infixList() {
        
    		TreeNode cur = root;
    		while (cur != null) {
        
    			while (cur.leftType == 0) {
        
    				cur = cur.left;
    			}
    			System.out.println(cur);
    			while (cur.rightType == 1) {
        
    				cur = cur.right;
    				System.out.println(cur);
    			}
    			cur = cur.right;
    		}
    	}
    
    	/**
    	 * 中序线索化
    	 * @param treeNode
    	 */
    	public void infixThreadedTreeNodes(TreeNode treeNode) {
        
    		if (treeNode == null) {
        
    			return;
    		}
    		//线索化左子树
    		infixThreadedTreeNodes(treeNode.left);
    		//处理当前节点前驱节点
    		if (treeNode.left == null) {
        
    			treeNode.left = pre;
    			treeNode.leftType = treeNode.PRECURSOR_OR_SUCCESSOR;
    		}
    		//处理当前节点后继节点，实际是在递归的上一层处理的
    		if (pre != null && pre.right == null) {
        
    			pre.right = treeNode;
    			pre.rightType = treeNode.PRECURSOR_OR_SUCCESSOR;
    		}
    		//使当前节点称为下一个节点的先驱节点
    		pre = treeNode;
    		//线索化右子树
    		infixThreadedTreeNodes(treeNode.right);
    	}
    
    }
    
    class TreeNode {
        
    	int val;
    	TreeNode left;
    	TreeNode right;
    	//左右指向的类型
    	int leftType;
    	int rightType;
    	//0表示子树，1表示前驱或者后继节点
    	static final int SUBTREE = 0;
    	static final int PRECURSOR_OR_SUCCESSOR = 1;
    
    	public TreeNode(int val) {
        
    		super();
    		this.val = val;
    	}
    
    	@Override
    	public String toString() {
        
    		return "TreeNode [val=" + val + "]";
    	}
    }