二叉树的基本计算关于非递归遍历

好多间接级别不同啊？

img


#include<stdio.h>
#include<stdlib.h>
typedef char ElemType;
typedef struct BiTNode {
    ElemType data;
    struct BiTNode* lchild, * rchild;
}BiTNode,* BiTree;

typedef BiTree SElemType;
#include"stack.h"
typedef BiTree QElemType;
#include"queue.h"

void Create(BiTree* bt) {
    char ch;
    ch = getchar();
    if (ch == '#') {*bt = NULL;}
    else {
        *bt = (BiTree)malloc(sizeof(BiTNode));
        if (*bt == NULL) {// 处理内存分配失败的情况
            return;
        }
        else {
            (*bt)->data = ch;
            (*bt)->lchild = NULL;
            (*bt)->rchild = NULL;
            Create(&((*bt)->lchild));
            Create(&((*bt)->rchild));
        }
    }
}

void PrintTree(BiTree bt, int nLayer) {//按树状打印二叉树
    if (bt == NULL) return;
    PrintTree(bt->rchild, nLayer + 1);
    for (int i = 0; i < nLayer; i++) { printf(" "); }
    printf("%c\n", bt->data);
    PrintTree(bt->lchild, nLayer + 1);
}

void PreOrder(BiTree root) {//先序递归遍历二叉树
    if (root != NULL) {
        printf("%c", root->data);
        PreOrder(root->lchild);
        PreOrder(root->rchild);
    }
}

void InOrder(BiTree root) {//中序递归遍历二叉树
    if (root != NULL) {
        InOrder(root->lchild);
        printf("%c", root->data);
        InOrder(root->rchild);
    }
}

void PostOrder(BiTree root) {//后序递归遍历二叉树
    if (root != NULL) {
        PostOrder(root->lchild);
        PostOrder(root->rchild);
        printf("%c", root->data);
    }
}

int PostTreeDepth(BiTree bt) {//后序遍历求二叉树的高度
    int hl, hr, max;
    if (bt != NULL) {
        hl = PostTreeDepth(bt->lchild);
        hr = PostTreeDepth(bt->rchild);
        max = hl > hr ? hl : hr;
        return(max + 1);
    }
    else return(0);
}

int leaf(BiTree root) {//后序遍历统计叶子结点个数
    int LeafCount;
    if (root == NULL) LeafCount = 0;
    else if ((root->lchild == NULL) && (root->rchild == NULL)) LeafCount = 1;
    else LeafCount = leaf(root->lchild) + leaf(root->rchild);
    return LeafCount;
}

void PreOrder_stack(BiTree T){//先序非递归遍历二叉树
    SeqStack* S;
    InitStack(&S);
    BiTNode* p;
    p = T;
    while (p || !IsEmpty(&S))
    {
        if (p)
        {
            printf("%c", p->data);
            Push(S, p);
            p = p->lchild;
        }
        else
        {
            Pop(S, &p);
            p = p->rchild;
        }
    }
}

void InOrder_stack(BiTree T){
    SeqStack* S;
    InitStack(&S);
    BiTNode* p;
    p = T;
    while (p || !IsEmpty(&S)){
        if (p){
            Push(S, p);
            p = p->lchild;
        }
        else{
            Pop(S, &p);
            printf("%c", p->data);
            p = p->rchild;
        }
    }
}

int main()
{
    BiTree T;
    Create(&T);
    PrintTree(T, 3);
    return 0;
}


#define Stack_Size 20
#define TRUE 1
#define FALSE 0
typedef struct {
    SElemType elem[Stack_Size];
    int top;
}SeqStack;
void InitStack(SeqStack* s) {
    s->top = -1;
}
int IsEmpty(SeqStack* s) {
    if (s->top == -1)  return TRUE;
    else  return FALSE;
}
int IsFull(SeqStack* s) {
    if (s->top == Stack_Size - 1)  return TRUE;
    else  return FALSE;
}
int Push(SeqStack* S, SElemType e) {
    if (S->top == Stack_Size - 1)    return FALSE;
    S->top++;
    S->elem[S->top] = e;
    return TRUE;
}
int Pop(SeqStack* S, SElemType* e) {
    if (S->top == -1)    return FALSE;
    *e = S->elem[S->top];
    S->top--;
    return TRUE;
}
int GetTop(SeqStack* S, SElemType* e) {
    if (S->top == -1)    return FALSE;
    *e = S->elem[S->top];
    return TRUE;
}


#define MAXSIZE 20
#define TRUE 1
#define FALSE 0

typedef struct {
    QElemType elem[MAXSIZE];
    int front;
    int rear;
}SeqQueue;

void InitQueue(SeqQueue* Q)//初始化 
{
    Q->front = Q->rear = 0;
}

int EnterQueue(SeqQueue* Q, int e)//入队 
{
    if ((Q->rear + 1) % MAXSIZE == Q->front)
        return(FALSE);
    Q->elem[Q->rear] = e;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return(TRUE);
}

int DelQueue(SeqQueue* Q, int* x)//出队 
{
    if (Q->front == Q->rear)
        return(FALSE);
    *x = Q->elem[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return(TRUE);
}

int IsEmptyQueue(SeqQueue* Q)//判空 
{
    if (Q->rear == Q->front)
    {
        return(TRUE);
    }
    else
    {
        return(FALSE);
    }
}

int IsFullQueue(SeqQueue* Q)//判满 
{
    if ((Q->rear + 1) % MAXSIZE == Q->front) return(TRUE);
    else return(FALSE);
}

int GetHead(SeqQueue* Q, int* x)//读取队首元素 
{
    if (Q->rear == Q->front)
    {
        return(FALSE);
    }
    *x = Q->elem[Q->front];
    return(TRUE);
}

int GetTail(SeqQueue* Q)//读取队尾元素 
{
    if (Q->front == Q->rear)
    {
        return(FALSE);
    }
    int x = Q->elem[Q->rear - 1];
    return x;
}