博客

问题1

给定一颗二叉树，给定某个结点X的值，要求打印出该结点的祖先。

思路

想想上一篇中有讲到后序遍历的非递归算法，其中栈里面保存的正是从根结点到当前结点的一条路径。如果当前结点就是要找的结点X的话，那么栈里面保存的就是该结点的所有祖先，依次输出即可。如果当前结点不是要找的结点X，如果标记位为1则继续遍历，否足则对该结点进行空遍历（即将该结点弹出栈）

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <malloc.h>
#include <stack>
#include <queue>
#include <bits/stdc++.h>

using namespace std;


typedef struct BiTNode{
    char data;
    struct BiTNode *left,*right;
}BiTNode,*BiTree;


BiTree build()
{
    char c;
    BiTree st = nullptr;
    c=getchar();
    if(c!='#')

    {

        st = new BiTNode();
        st ->data = c;//已知为先序遍历，先填充根节点
        st ->left = build();//递归形式填充左分支
        st ->right = build();//递归形式填充左分支
    }
    return st;
}