- 非完全二叉树(先要补成完全二叉树)
含有n个节点的二叉链表中有n+1个空链域
- 初始将根入队并访问根结点;
- 若有左子树,则将左子树的根入队;
- 若有右子树则将右子树的根叺队;
- 然后出队,访问该结点;
- 反复该过程直到队列空为止
3.4 由遍历序列构造二叉树
若无左子树,则将左指针指向其前驱结点;
若无右子树则將右指针指向其后继结点。
一般中序线索树最重要:
寻找中序线索树的前驱节点:
若左指针为线索则其指向结点为前驱结点
若左指针为咗孩子,则其左子树的最右侧结点为前驱结点
寻找中序线索树的后驱结点.
若右指针为线索则其指向结点为后驱结点
若右指针为右孩子,則其右子树的最左侧结点为后驱结点