线索二叉树

线索二叉树

鉴于拥有N个节点的二叉查找树包含N+1个NULL指针，因此在该结构中，用于指针信息的空间有一半被闲置。当某节点的左子节点为NULL时，其左子指针将指向该节点的 中缀前驱（inorder predecessor） ；而当某节点的右子节点为NULL时，其右子指针则指向该节点的 中缀后继（inorder successor） 。这种结构被称为 线索二叉树（threaded tree） ，其中新增加的指针则被定义为 线索（thread） 。

• 为了能够从实际的子节点指针中识别出线索的存在，每个节点需额外增加一个字段，用以标识当前指针是代表线索还是指向实际的子节点。

    typedef enum
    {
    Linked,	// 表示正常孩子
    Thread	// 表示线索
    } PointerTag;
    
    typedef int ElementType;
    struct ThreadTree;
    typedef struct ThreadTree *Tree;
    typedef struct ThreadTree *Position;
    struct ThreadTree
    {
    ElementType Element;
    Tree