王道书 P150 T12（打印x的所有祖先） + 拓展（打印从根节点到某个节点的路径、求根节点到某个节点的路径长度、求根节点的最大路径长度）

/**
 * 用二叉树链式存储实现 王道 P150 T12（打印x的所有祖先）
 * + 拓展（打印从根节点到某个节点的路径、求根节点到某个节点的路径长度、求根节点的最大路径长度）
 *
 * ①算法思想
 * ①②③④都是非递归方式，除了④都是从非递归先序遍历改来的，
 * ④也可以说是从“求树高”的代码改来的,因为求根节点的最长路径,就相当于求某出个节点的最深层次,和求树高过程一样,
 * 求树高可以从层次和后序等改来的(参考P149 T5 文章).
 * ①②③他们的思维过程和遇到某个值时弹出栈里的元素是一样的。
 * ①打印x的所有祖先
 * ②打印从根节点到某个节点的路径
 * ③求根节点到某个节点的路径长度
 * ④求根节点的最大路径长度
 * ⑤求根节点的最长路径
 *
 * ②算法设计
 */
 
#include <stdio.h>
#include <iostream>
#define MaxSize 100
 
typedef struct BiTreeNode{
    int data;
    BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
 
 
//P150 T12
//①打印x节点的所有祖先
void PrintPreByPreOrderNR(BiTree T,int x){
    BiTree stack[MaxSize],p = T;
    int top = -1,tag[MaxSize] = {0};
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            tag[top] = 1;
            p = p -> lchild;
        }else{
            if(tag[top] == 1){
                tag[top] = 2;
                p = stack[top];
                p = p -> rchild;
            }else{//说明是叶子节点了
                p = stack[top--];
//                Visit(p);
                //打印祖先
                if(p -> data == x){
                    for (int i = 0; i <= top ; ++i) {
                        printf("%d ",stack[i] -> data);
                    }
                }
                p = NULL;
            }
        }
    }
}
//②打印从根节点到某个节点的路径
void PrintPathByPreOrderNR(BiTree T,int x){
    BiTree stack[MaxSize],p = T;
    int top = -1,tag[MaxSize] = {0};
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            tag[top] = 1;
            p = p -> lchild;
        }else{
            if(tag[top] == 1){
                tag[top] = 2;
                p = stack[top];
                p = p -> rchild;
            }else{//说明是叶子节点了
//                p = stack[top--];
                //这边要把出栈放缓，不让就打印不出来了
                p = stack[top];
//                Visit(p);
                //打印路径
                if(p -> data == x){
                    for (int i = 0; i <= top ; ++i) {
                        printf("%d ",stack[i] -> data);
                    }
                }
                //把top--放这
                top--;
                p = NULL;
            }
        }
    }
}
//③求根节点到某个节点的路径长度
int XPathLengthByPreOrderNR(BiTree T,int x){
    BiTree stack[MaxSize],p = T;
    int top = -1,tag[MaxSize] = {0};
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            tag[top] = 1;
            p = p -> lchild;
        }else{
            if(tag[top] == 1){
                tag[top] = 2;
                p = stack[top];
                p = p -> rchild;
            }else{//说明是叶子节点了
//                p = stack[top--];
                //这边要把出栈放缓，不让就打印不出来了
                p = stack[top];
//                Visit(p);
                //打印路径长度
                if(p -> data == x){
                    return top + 1;
                }
                //把top--放这
                top--;
                p = NULL;
            }
        }
    }
    return -1;
}
//④求根节点的最大路径长度
int GetMaxPathLength(BiTree T){
    BiTree stack[MaxSize],p = T;
    int top = -1,tag[MaxSize] = {0},max = -1;//max用来记录高度
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            tag[top] = 1;
            p = p -> lchild;
        }else{
            if(tag[top] == 1){
                tag[top] = 2;
                p = stack[top];//找到栈顶元素，这样才能接着往下找
                p = p -> rchild;
            }else{//说明是叶子节点了
                p = stack[top];//访问这个点的时候先不急着出栈，因为如果直接出栈的话，高度就有损失了
                if(p -> lchild == NULL && p -> rchild == NULL){//说明是叶子节点
                    if(top + 1 > max)//top是从-1开始的，或者说top是数组的下标，所以要+1才是路径的长度
                        //注意这个top是一直在变化的，所以每遇到一个叶子节点，就要来比较一下，这样才能找到路径最长的叶子节点。
                        max = top + 1;
                }
                top--;
                p = NULL;
            }
        }
    }
    return max;
}
//⑤求根节点的最长路径
int GetMaxPathByPostOrder(BiTree T){
    BiTree stack[MaxSize],p = T;
    int top = -1,tag[MaxSize] = {0};
    int max = -1,path[MaxSize];
    while(p || top != -1){
        if(p){
            stack[++top] = p;
            tag[top] = 1;
            p = p -> lchild;
        }else{
            if(tag[top] == 1){
                tag[top] = 2;
                p = stack[top];
                p = p -> rchild;
            }else{//说明是叶子节点了
                p = stack[top];//放缓一步
//                Visit(p);
                if(p -> lchild == NULL && p -> rchild == NULL){
                    if(top + 1 > max){
                        max = top + 1;
                        for (int i = 0; i < top; ++i) {
                            path[i] = stack[i] -> data;
                        }
                    }
                }
                top--;
                p = NULL;
            }
        }
    }
    for (int i = 0; i < max ; ++i) {
        printf("%d ",path[i]);
    }
    return max;
}