c语言-数据结构-非递归打印二叉树

Question

//非递归打印二叉树程序，非递归打印部分程序没有结果。

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
typedef struct bitree
{
    int data;
    struct bitree *lchild,*rchild;
}*BiTree,BiNode;

typedef struct stack
{
    struct stack *next;
 BiTree adress;
}Stack;

typedef struct
{
 Stack *base,*top;
}LinkStack;

void InsertAdress(LinkStack *s,BiTree p) //将每个节点地址插入栈中
{
    Stack *r;
    r = (Stack*)malloc(sizeof(Stack));
    r->next = NULL;
    r->adress =  p;
    s->top = r;
}

BiNode *DeleteAddress(LinkStack *s,BiTree *p)//出栈，但不删除栈中元素
{
  Stack *q;
  q = s->base;
  while(q->next != s->top)
    q = q->next;
  s->top = q;
  p = s->top;
  return p;  //返回上一个节点的地址
}

int Creat(BiTree *Tree)//递归建立二叉树
{
    int elem;
    scanf("%d",&elem);
    if(elem == 0) *Tree = NULL;
    else
    {
        *Tree = (BiTree)malloc(sizeof(BiNode));
        (*Tree)->data = elem;
        Creat(&(*Tree)->lchild);
        Creat(&(*Tree)->rchild);
    }
    return 0;
}

void Print(BiTree Tr) //递归打印二叉树
{
    if(Tr)
    {
        printf("%d ",Tr->data);
        Print(Tr->lchild);
        Print(Tr->rchild);
    }
}
//非递归打印部分程序没有结果
void PreOrder(BiTree Tr) //非递归打印二叉树
{
 LinkStack s;
 s.base = s.top = NULL;
    BiTree p;
 p = (BiTree*)malloc(sizeof(BiNode));
    p = Tr;
    while(p != NULL || s.base != s.top)
    {
        while(p != NULL) // 当 p 不为空，找到他最左下节点。
        {
            printf("%d ",p->data);
   InsertAdress(&s,p);
   p = p->lchild;
        }
  
  if(s.base != s.top)
  {
   DeleteAddress(&s,&p); //递归返回找右结点。
   p = p->rchild;
  }
    }
}


int main()
{
    Stack S;
    BiTree Tr;
    printf("输入二叉树: ");
    Creat(&Tr);
    printf("\n递归打印: ");
    Print(Tr);
    printf("\n非递归打印为: ");
    PreOrder(Tr);
}

Answer 1

• 帮你找了个相似的问题, 你可以看下: https://ask.csdn.net/questions/7754441