二叉树的下一个节点——《剑指offer》

typedef struct node {
	int data;
	struct node* left;
	struct node* right;
	struct node*parent;
}Node,*PNode;

PNode GetNext(PNode p) {
	if (p == NULL) {
		return NULL;
	}

	PNode next = NULL;

	if (p->right != NULL) { //有右子树
		next = p->right;
		while (next->left != NULL) {
			next = next->left;
		}
	}
	else if (p->parent == NULL) { //无右子树且无父节点，即为无右子树的根结点
		next = NULL;
	}
	else {//无右子树但有根结点，找出第一个是左子树的祖先节点，这个节点的父结点就是下一个结点
		PNode Pcurrent = p, Pparent = p->parent;
		while (Pparent != NULL && Pcurrent != Pparent->left) {
			Pparent = Pparent->parent;
			Pcurrent = Pcurrent->parent;
		}//循环结束后，父节点为空时，代表没有作为左子树的祖先节点；或当前结点是左子树，则返回其父节点

		next = Pparent;
	}

	return next;
}