看了两天的树，困于调不通奇怪的C++代码，教程里偏工程化的代码也让我看得眼花缭乱。听取了人生导师的意见，开始调整学习方案：在搞懂思路的基础上先自己实现，再去看教程里的代码。而且，毕竟机试和竞赛不走那么工程的，写得太健壮没什么用，就拿半吊子的C跑通了就好。
于是我开始把C++代码都精简掉，数据域也直接扔一个int来代表，瞬间看起来清爽极了。我又把基础的操作实现了一下：
struct BinNode{
int data;
BinNode *parent, *lc, *rc;
};
BinNode* createNode(int d){ //创建节点
BinNode* node = new BinNode;
node -> data = d;
node -> parent = NULL;
node -> lc = NULL;
node -> rc = NULL;
return node;
}
BinNode* insertAsRoot(int d, BinNode* & root){ //插入树根
root = createNode(d);
}
BinNode* insertAsLc(int d, BinNode* & position){ //作为左孩子插入
position-> lc = createNode(d);
position-> lc-> parent = position;
}
BinNode* insertAsRc(int d, BinNode* & position){ //作为右孩子插入
position-> rc = createNode(d);
position-> rc-> parent = position;
然后又包装了几个判断，下面用着方便：
bool isRoot(BinNode* position){return (!(position -> parent));}//是否树根
bool islc(BinNode* position){ //是否左孩子
if(isRoot(position)) return false;
return (position -> parent -> lc == position);
}
bool isrc(BinNode* position){ //是否右孩子
if(isRoot(position)) return false;
return (position -> parent -> rc == position);
}
嗯，极爽。迭代就用打印数值来代表，先序、中序、后序遍历的递归版如此清爽：
void travPreR(BinNode* root){ //先序遍历 递归
if(! root) return;
printf("%d ", root -> data);
travPreR(root -> lc);
travPreR(root -> rc);
}
void travInR(BinNode* root){ //中序遍历 递归
if(! root) return;
travInR(root -> lc);
printf("%d ", root -> data);
travInR(root -> rc);
}
void travPostR(BinNode* root){ //后序遍历 递归
if(! root) return;
travPostR(root -> lc);
travPostR(root -> rc);
printf("%d ", root -> data);
}
又画了一会图，扫了下教程代码之后，开始写迭代版的先序遍历。I1版从每个局部出发考虑，对栈里弹出的x， 先把自己操作了，然后分别把右、左孩子推入栈中。I2版可以容易被中序和后序遍历借鉴，是从一条左下行的链出发考虑的，在左下行过程中逐个操作，顺带把右孩子入栈，这样，这批右孩子出栈的次序是从下向上的，出了栈之后对这个右子树也做同样左下行操作。
void travPreI1(BinNode* root){ //先序遍历 迭代
BinNode *stack[50], *x; //假装我是个栈
int len = 1;
stack[0] = root;
while(1){
if(len == 0) break;
x = stack[len - 1]; len --;
if(!x) continue;
printf("%d ", x -> data);
stack[len] = x -> rc; len ++;
stack[len] = x -> lc; len ++;
}
}
void travPreI2(BinNode* root){ //先序遍历 迭代
BinNode *stack[50], *x = root; //假装我是个栈
int len = 0;
while(1){
while(x){
printf("%d ", x -> data);
if(x -> rc) {stack[len] = x -> rc; len ++;}
x = x -> lc;
}
if(len == 0) break;
x = stack[len - 1]; len --;
}
}
中序遍历的迭代I1版是仿照前面I2的。不过，中序遍历是跳过了左下行链条上的节点，直至找到最下的才开始操作，就把这条链上的节点存入栈中。然后从下向上，访问链条上的点及其右子树，所以操作完之后别忘了x = x -> rc：
void travInI1(BinNode* root){ //中序遍历 迭代1
BinNode *stack[50], *x = root;
int len = 0;
while(1){
while(x){
stack[len] = x; len ++;
x = x -> lc;
}
if(len == 0) break;
x = stack[len - 1]; len --;
printf("%d ", x -> data);
x = x -> rc; //注意
}
}
据说中序遍历的直接后继挺有用的，那就……也写一下，感觉有点暴力，我也要画半天才能搞清楚。其实也就是两类：如果有右孩子，对于这个局部而言，就是访问完父节点该访问右子树了，去右边找；没有的话就是该往上回溯了，这里再分我是左孩子还是右孩子。在绕晕的边缘，我又用后继写了个中二的遍历函数，可以测试看下后继写对了没有：
BinNode* succ(BinNode *x){ //直接后继
if(x -> rc){ //有右孩子，后继一定在右子树
x = x -> rc; //给右孩子
while(x -> lc) x = x -> lc; //右孩子如果有左孩子，会传下去的
}else{ //没有右孩子
while(isrc(x)){ //如果x是作为父节点的右孩子，那父节点的右子树就访问完了
x = x -> parent; //找到父节点
}
x = x -> parent;//x是作为左孩子存在的，找父节点；对于最后一个节点，得到NULL
}
return x;
}
void travInI2(BinNode* root){ //中序遍历 迭代2 暴力用succ找下去
BinNode* x = root;
while(x -> lc) x = x -> lc;
while(x){
printf("%d ", x -> data);
x = succ(x);
}
}
在main函数里，我复制粘贴建了一棵树，然后试了一下：
BinNode* root = NULL;
insertAsRoot(0, root);
insertAsLc(1, root);
insertAsRc(2, root);
insertAsLc(3, root -> lc);
insertAsRc(4, root -> lc);
insertAsLc(5, root -> rc);
insertAsRc(6, root -> rc);
insertAsLc(7, root -> lc -> lc);
insertAsRc(8, root -> lc -> lc);
insertAsLc(9, root -> lc -> rc);
insertAsRc(10, root -> lc -> rc);
insertAsLc(11, root -> rc -> lc);
insertAsRc(12, root -> rc -> lc);
insertAsLc(13, root -> rc -> rc);
insertAsRc(14, root -> rc -> rc);
travPreR(root); printf("\n");
travPreI1(root); printf("\n");
travPreI2(root); printf("\n");
travInR(root); printf("\n");
travInI1(root); printf("\n");
travInI2(root); printf("\n");
travPostR(root); printf("\n");
没毛病。思路又回顾完了，我回去继续写中序遍历的其它实现还有后续遍历了。
人生导师还给我布置了两道题来着，啊呀，慢慢来。
