二叉树应用_二叉树的下一个节点

淡淡的烟草味﹌ 2022-05-22 04:07 251阅读 0赞

题目：给定一个二叉树和其中的一个节点，找出中序遍历的下一个节点。树中的节点除了有指向左右节点的两个指针之外，还有一个指向父节点的指针。  
分析：对于这个问题分情况讨论，1、如果一个节点有右子树，那么它中序遍历的下一个节点就是它的右子树的最左子节点。2、如果一个节点没有右子树，并且是他父节点的左子节点，那么他的父节点就是中序遍历中的下一个节点。3、如果一个节点既没有右子树，并且他还是父节点的右子节点，我们就沿着父子节点向上找，直到找到一个节点是他父节点的左子节点，那么找到节点的父节点就为下一个节点。  
实现如下：

struct TreeLinkNode {
        int val;
        struct TreeLinkNode *left;
        struct TreeLinkNode *right;
        struct TreeLinkNode *next;
        TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {
    
        }
    };
    */
    
    TreeLinkNode *nextnode(TreeLinkNode *pnode)
    {
        TreeLinkNode *pnext=NULL;
        if(!pnode)
            return pnext;
        if(pnode->right)
        {
            TreeLinkNode *pleft=pnode->right;
            while(pleft->left)
                pleft=pleft->left;
            pnext=pleft;
        }
        //（1、若为节点A的左子树则下一个节点就为A，2、若为节点A的右子树则 沿着当前节点向上找直到找到一个节点B它是节点C的左子节点 则C就为下一个节点）
        else if(pnode->next)
        {
            TreeLinkNode *pcurrent=pnode;
            TreeLinkNode *pparent=pnode->next;
            while(pparent&&pcurrent==pparent->right)
            {
                pcurrent=pparent;
                pparent=pcurrent->next;
            }
            pnext=pparent;
        }
        return pnext;
    }