本文总结了二叉树常见的题目。
如下是头文件的部分声明：
//tree.h
#ifndef TEST_TREE_H
#define TEST_TREE_H
typedef int ElementType;
struct TreeNode;
typedef struct TreeNode *Position;
typedef struct TreeNode *SearchTree;
struct TreeNode {
ElementType element;
SearchTree left;
SearchTree right;
};
...
#endif
从上述的声明可以看出Positon、SearchTree均是指向树型结构的指针，在下面的程序中注意。
如下的程序中，有的是借助二叉搜索树的性质，因此是二叉树特有的；而大部分都是二叉树均有的算法。在每段代码开头都注明了是仅用于二叉搜素树或者是通用的。
二叉搜索树按照中序遍历时，输出的节点是从小到大排列好的。如果各个节点关键字不相等，那么节点x的前驱就是中序遍历的x的前一个，后继就是中序遍历的x的后一个节点。
寻找节点后继的思想：如果节点的右子树不为空，其后继就是右子树的最小节点；如果节点x右子树为空，并且该节点有后继节点y，则y是x的最低的祖先节点，并且y的左儿子也是x的祖先(这里可以认为每个节点都是自己的祖先)。
如下图所示，节点13没有右子树，而该节点是有后继的，因此其后继节点就是其最低的祖先节点，且该祖先节点的左孩子也是其祖先。那么可以判断13的后继节点是15。
再比如，节点9没有右子树，且该节点有后继节点；那么13是节点9的后继节点，此时13的右孩子是节点9自己，此时可以认为9是自己的祖先节点。
同理，对于寻找前驱节点：如果节点x有左子树，那么其前驱节点就是左子树中最大的那个节点；如果该节点x没有左子树，且该节点存在前驱节点y，则y是x的最低祖先结点，且y的右孩子也是x的祖先（可以认为自己是自己的祖先节点）。
例如上图中9没有左子树，因此其前驱为7，此时7是9的祖先，且7的右节点也是9的祖先。
再比如7的前驱是6，此时6的右孩子（节点7本身）是节点7的祖先节点（7是7本身的祖先节点）。
从上面的分析可以看出，要求出某结点的前驱和后继节点，都需要指向结点父亲的指针，如果有指向父节点的指针，那么，问题就很容易了，代码参考STL源码：红黑树。
伪代码如下：
找后继：
TREE-SUCCESSOR(x)
if rithx[x]≠NIL
then return TREE-MINIMUM(right[x])
y←p[x]
while y≠NIL and x=right[y]
do x←y
y←p[y]
return y
找前驱：
TREE-PREDECESSOR(x)
if left[x]≠NIL
then return TREE-MAXMUM(left[x])
y←p[x]
while y≠NIL and x=left[x]
do x←y
y←p[y]
return y