打印所有根到叶路径

Question

我尝试打印二叉树中所有根到叶路径的代码。

#include<iostream>
#include<stack>
using namespace std;

bool visited[100];
void intilize(){
    for(int i=0;i<100;i++)
      visited[i]=false;
}
struct node
{
    int data;
    struct node *left,*right;
};
struct node* createNode(int k)
{
    struct node* temp = new node;
    temp->left = NULL;
    temp->right = NULL;
    temp->data = k;
    return temp;
}
stack<node*> s,s1;
void print(){
    while(!s.empty()){
        s1.push(s.top());
        s.pop();
    }
    while(!s1.empty()){
        struct node* a= s1.top();
        cout<<a->data<<" ";
        s1.pop();
        s.push(a);
        if(s1.empty())
        return;

    }


}
void printpath(struct node* node){
    if(node==NULL) return;
    s.push(node);

    while(!s.empty()){
    struct node* top=s.top();
    visited[top->data]=true;

    if(top->left!=NULL&&visited[top->left->data]==false)
     printpath(top->left);
    else if(top->right!=NULL&&visited[top->right->data]==false)
     printpath(top->right);
    else if(top->left==NULL&&top->right==NULL){
    print();
     cout<<"\n";    
    }

     s.pop();   
    }

}


int main() {
    struct node* root = createNode(50);
    root->left = createNode(7);
    root->right = createNode(2);

    root->right->left = createNode(1);
    root->right->right = createNode(30);
    root->right->right->right = createNode(40);
    root->right->left->left = createNode(10);
    root->right->left->left->left = createNode(12);

    intilize();
    printpath(root);

    return 0;
}

代码给出了分段错误，因为终止条件存在一些问题。谁能帮我解决这个问题。

Answer 1

该方法过于复杂且脆弱。

为此不需要单独的堆栈。

不需要单独的 "visible" 数组。

所需要的只是一个递归下降到这棵树中的库存递归访问者，它还为动态构建在堆栈上的结构提供了一个额外的参数，该结构动态构建到根的路径，使用 link 列表是这样的：

struct path_to_root {
   struct path_to_root *next;
   struct node *n;
};

现在，打印每个叶子笔记的路径所需要的只是一个沼泽标准访问者，它递归地遍历树，以及这个附加参数。以下是一般方法的粗略概念：

void printpath(struct node *n, struct path_to_root *p)
{
   struct path_to_root pnext;

   if (!n)
       return;

   if (!n->left && !n->right)
   {
       /* Your homework assignment here is to print the path that's in "p" */
   }

   pnext.n=n;
   pnext.next=p;

   printpath(n->left, &pnext);
   printpath(n->right, &pnext);
}

这将被调用为：

printpath(root, NULL);

如前所述，您的家庭作业是在指示的 space 中使用 p 参数实现打印叶子路径的实际代码。届时，叶子的路径将在 p 参数中找到。

现在，这里有一个棘手的部分是 p 将成为叶的父级，p->next 将成为其祖父级，依此类推。所以路径是从下到上，而不是从上到下，但这是一个小细节，可以在打印代码中处理。

或者，或者，以相同的方式从上到下动态构建到叶节点的路径不会有太多额外的工作。

打印所有根到叶路径

Printing all root to leaf paths

c++

tree

stack

binary-tree