39、PHP 实现二叉树的下一个结点（含源码）

题目： PHP 实现二叉树的下一个结点

描述：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

<?php
/*class TreeLinkNode{
    var $val;
    var $left = NULL;
    var $right = NULL;
    var $next = NULL;
    function __construct($x){
        $this->val = $x;
    }
}*/
function GetNext($pNode)
{
    if($pNode==null)
        return null;
    if($pNode->right)
        {
        $pNode=$pNode->right;
        while($pNode->left)
            {
            $pNode=$pNode->left;
        }
        return $pNode;
    }
    else
        while($pNode->next)
            {
            if($pNode->next->left==$pNode)
                return $pNode->next;
            $pNode = $pNode->next;
        }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32