线索二叉树

  • 线索二叉树：加上线索的二叉树，线索就是指向该节点前驱和后继的指针
  • 引入目的：方便查找结点的前驱和后继
  • 实现方法：利用二叉树的空指针区域，存放该节点前驱和后继
  • 将left指针存放前驱结点，将right指针存放后继结点
  • 没有箭头的绿色部分均为空指针域

  • 会不会出现空指针不足的情况

    空指针永远比结点多一个

  • 怎么区分left指针存放的是前驱还是左孩子

    新增两个变量：ltag、rtag，0表示指针存放孩子节点，1表示指针存放线索

  • 创建二叉树

1
2
3
4
5
6
7
8
9
typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
    int ltag;  //0表示孩子节点，1表示线索
    int rtag;  //0表示孩子节点，1表示线索
} TreeNode;

typedef TreeNode* ThreadTree;  //别名

准备工作

  • 让头节点的left指向根节点
  • right指向遍历是访问的最后一个结点
  • 遍历的第一个节点的left指针指向头节点
  • 遍历的最后一个结点right指针指向头节点
  • 模仿双向链表，既可以从第一个结点开始遍历，也可以从最后一个结点开始遍历