王道书 P191 思维拓展

/**
 * 王道书 P191 思维拓展
 *
 * ①算法思想
 *
 * ②算法设计
 */
 
#include <stdio.h>
#include <iostream>
#define MaxSize 100
 
typedef struct BiTreeNode{
    int data;
    BiTreeNode *lchild,*rchild;
}BiTreeNode,*BiTree;
 
 
//思维拓展
void FindPathEQData(BiTree T,int data){
    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 -> lchild == NULL && p -> rchild == NULL){//如果是叶子节点
                    int sum = 0;
                    for (int i = 0; i <= top ; ++i) {
                        sum += stack[i] -> data;
                    }
                    if(sum == data){//打印路径
                        for (int i = 0; i <= top; ++i) {
                            printf("%d ",stack[i] -> data);
                        }
                    }
                }
                top --;
                p = NULL;
            }
        }
    }
}