[数据结构与算法]树与二叉树学习记录

一、线索二叉树的构造（中序、前序和后序）：添加前驱和后继的位置应该和visit(T)的位置一样。

    void InTree(TreeNode *p, TreeNode *pre){
        if(p!=null){
            InTree(p->left,pre);
            if(p->left == null){
                p->left = pre;
                p->ltag = 1;
            }
            if(pre->right == null){
                pre->right = p;
                pre->rtag = 1;
            }
            pre=p;
            InTree(p->right,pre);
        }
    }

    void PreTree(TreeNode *p, TreeNode *pre){
        if(p!=null){
            if(p->left == null){
                p->left = pre;
                p->ltag = 1;
            }
            if(pre->right == null){
                pre->right = p;
                pre->rtag = 1;
            }
            pre=p;
            PreTree(p->left,pre);
            PreTree(p->right,pre);
        }
    }

    void PostTree(TreeNode *p, TreeNode *pre){
        if(p!=null){
            PostTree(p->left,pre);
            PostTree(p->right,pre);
            if(p->left == null){
                p->left = pre;
                p->ltag = 1;
            }
            if(pre->right == null){
                pre->right = p;
                pre->rtag = 1;
            }
            pre=p;
        }
    }

二、遍历中序线索二叉树

如果是要找某个节点的后继节点分两种情况：

1、rtag=1，直接访问后继节点

2、rtag=0，要找出中序遍历的后继结点，根据中序遍历是左->根->右的特性，后继节点一定是当前节点右子树的最左下点。也就是说遍历右子树的left节点，如果ltag != 0，则找到后继节点。

    void Inorder(TreeNode *p){
        for(p=FirstNode(p);p!=NULL;p=NextNode(p)){
            visit(p);
        }
    }
    TreeNode *NextNode(TreeNode *p){
        if(p->rtag == 0) return FirstNode(p->right);
        else return p->right;
    }
    TreeNode *FirstNode(TreeNode *p){
        while(p->ltag == 0)
            p=p->left;
        return p;
    }

找前驱节点时，也分两种情况：

1、ltag=1，直接访问前驱节点

2、ltag=0，要找出中序遍历的前驱结点，根据中序遍历是左->根->右的特性，前驱节点一定是当前节点左子树的最右下点。也就是说遍历左子树的right节点，如果rtag != 0，则找到前驱节点。

//与寻找后继节点相比，只需修改找最后一个节点的方法和找下个节点的方法即可
    TreeNode *NextNode(TreeNode *p){
        if(p->ltag == 0) return FirstNode(p->left);
        else return p->left;
    }
    TreeNode *LastNode(TreeNode *p){
        while(p->rtag == 0)
            p=p->right;
        return p;
    }

三、遍历前序线索二叉树

找前序线索二叉树的后继节点看上去是两种情况,，但其实只有一种情况，根据前序遍历是根->左->右的特性，后续节点一定是当前节点的左孩子或者右孩子。

    void Preorder(TreeNode *p){
        for(p;p!=NULL;p=NextNode(p)){
            visit(p);
        }
    }
    TreeNode *NextNode(TreeNode *p){
        if(p->left != null && p->latg == 0) return p->left;
        else return p->right;
    }

找前序线索二叉树的前驱节点，如果ltag=1，且结构上没有指向父节点的指针则无法找到前驱节点。若结构上存在指向父节点的指针，则只需要找到父节点的左子树的最右侧指针。

    TreeNode *NextNode(TreeNode *parent,TreeNode *p){
        if(p == parent->left) return parent;
        else{
            p = parent->right;
            while(p->rtag==0)
                p=p->rtag;
            return p;
        }
    }