二叉树-1

看了两天的树，困于调不通奇怪的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");

没毛病。思路又回顾完了，我回去继续写中序遍历的其它实现还有后续遍历了。

人生导师还给我布置了两道题来着，啊呀，慢慢来。