#include <stdio.h>
#include <stdlib.h>
#include<malloc.h>

//雙親表示法
#define MAX_TREE_SIZE 10
#define OK 1
#define ERROR 0
#define true 1
#define false 0
#define EOVERFLOW 0
typedef char ElemType;
typedef int bool;
typedef int Status;
enum TREEWAY
{
      PREORDER, INORDER, POSTORDER, LEVEL
};
enum TREEWAY treeWay = PREORDER;
char blankStr=' ';//空格


typedef struct _BTNode{
    ElemType data;
    struct _BTNode *lchild,*rchild;
}BiTNode,*BiTree;


//---------------棧（鏈表）相關開始----------------------
typedef BiTree SElemType;
typedef struct _SqNode{
    SElemType data;
    struct _SqNode *next;
}SqNode;
typedef struct _SqStack{
    SqNode *top;
    int count;//棧計數(shù)器
}SqStack;
void Init_Stack(SqStack *stack){
    stack->top=NULL;
    stack->count=0;
}
//壓棧
Status Push(SqStack *stack,SElemType e){
    SqNode *node=NULL;
    do{
        node=(SqNode*)malloc(sizeof(SqNode));
    }while(!node);
    node->data=e;
    node->next=stack->top;
    stack->top=node;
    stack->count++;
    return OK;
}
//出棧 后進先出
Status Pop(SqStack *stack,SElemType *e){
    if(stack->top){
        SqNode *tmp=stack->top;
        stack->top=tmp->next;
        *e=tmp->data;
        free(tmp);
        stack->count--;
        return OK;
    }else{
        printf("棧為空，出棧失敗\n");
        return ERROR;
    }
}
void Clear_Stack(SqStack *stack){
    if(!stack->top)return;
    SqNode *p=stack->top;
    SqNode *tmp;
    while(p){
        tmp=p;
        p=tmp->next;
        free(tmp);
    }
    stack->top=NULL;
    stack->count=0;
}
void Destory_Stack(SqStack *stack){
    Clear_Stack(stack);
    free(stack);
}
int Stack_IsEmpty(SqStack stack){
    if(stack.top){
        return false;
    }
    return true;
}

//---------------棧相關結束----------------------

//---------------隊列（順序結構，循環(huán)）相關開始----------------------
const int INIT_QUEUE_SIZE=100;
const int INCREAMENT_QUEUE_SIZE=2;
typedef BiTree QElemType;
typedef struct _SqQueue{
    int front;//對頭
    int rear;//對尾
    QElemType *base;
    int size;
    int capacity;
}Queue;
Queue* Init_Queue(){
    Queue* q=(Queue*)malloc(sizeof(Queue));
    if(!q){
        return NULL;
    }
    q->base=(QElemType*)malloc(sizeof(QElemType)*INIT_QUEUE_SIZE);
    q->front=q->rear=0;
    q->size=0;
    q->capacity=INIT_QUEUE_SIZE;
    return q;
}
int Queue_IsFull(Queue *q){
    if(q->size==q->capacity){
        return true;
    }
    return false;
}
int Queue_IsEmpty(Queue *q){
    if(q->size==0){
        return true;
    }
    return false;
}
void Clear_Queue(Queue *queue){
    queue->front=queue->rear=0;
    queue->size=0;
}
void Destroy_Queue(Queue *queue){
    free(queue->base);
    queue->base=NULL;
}
//擴容  未完善
Queue* Copy_Queue(Queue *q){
    if(q->base==NULL){
        return q;
    }

    Queue* newQueue=(Queue*)malloc(sizeof(Queue));
    newQueue->base=(QElemType*)malloc(sizeof(QElemType)*(q->capacity+INCREAMENT_QUEUE_SIZE));
    newQueue->front=newQueue->rear=0;
    newQueue->size=0;
    newQueue->capacity=q->capacity+INCREAMENT_QUEUE_SIZE;
    int i,end,index=0;
    //隊尾與對頭相減大于0 則最大下標為隊尾，否則下標為隊列最大容量 可能存在重頭開始情況
    bool flag=q->rear-q->front>0;
    if(flag){
        end=q->rear;
    }else{
        end=q->capacity;
    }
    for(i=q->front;i<end;i++){
        newQueue->base[index++]=q->base[i];
    }
    if(!flag){
        for(int j=0;j<q->rear;j++){
            newQueue->base[index++]=q->base[j];
        }
    }
    newQueue->size=q->size;
    return newQueue;
}

//入隊列
void Push_Queue(Queue *q,QElemType e){
    //判斷隊列容量是否已經(jīng)滿了 重新分配
    if(Queue_IsFull(q)){
        printf("\n隊列已滿，無法入隊\n");
        return ;
    }
    //將新元素賦值到隊尾
    q->base[q->rear]=e;
    //重新設置隊尾
    //獲取下一個下標，取模 循環(huán)當下標到最大時，從0開始;
    int nextIndex=(q->rear+1)%(q->capacity);
    q->rear=nextIndex;
    q->size++;
}
void Pop_Queue(Queue *q,QElemType *e){
    //判斷是否為空
    if(q->size==0){
        printf("隊列為空，不能出隊\n");
        return;
    }
    *e=q->base[q->front];
    int nexIndex=(q->front+1)%q->capacity;
    q->front=nexIndex;
    q->size--;
}


//---------------隊列相關結束----------------------




//創(chuàng)建二叉樹
void CreateBiTree(BiTree *Root){
    ElemType val=0;
    val=getchar();
    //如果輸入' '，則指向為空
    if(val == blankStr){
        (*Root) = NULL;
    //如果輸入非' '，則給數(shù)據(jù)域賦值
    }else{
        *Root = (BiTNode*)malloc(sizeof(BiTNode));//根節(jié)點
        if(!(*Root)){
            printf("創(chuàng)建節(jié)點失敗，無法分配可用內(nèi)存...");
            exit(EOVERFLOW);
        }else{
            (*Root)->data=val;
            //創(chuàng)建左子樹
            CreateBiTree(&(*Root)->lchild);//左節(jié)點
            //創(chuàng)建右子樹
            CreateBiTree(&(*Root)->rchild);//右節(jié)點
        }
    }
}
//判斷二叉樹是否為空
int BiTreeEmpty(BiTree T){
    if(T){
        return false;
    }
    return true;
}
int BiTreeDepth(BiTree T){
    if(!T){
        return 0;
    }
    //樹的高度 = max(左子樹的高度，右子樹的高度) + 1
    int leftDepth = BiTreeDepth(T->lchild);
    int rightDepth = BiTreeDepth(T->rchild);
    return leftDepth >= rightDepth ? leftDepth + 1 : rightDepth + 1;
}

//獲取樹的葉子節(jié)點個數(shù)

int getLeafNum(BiTree T){
    if(!T){
        return 0;
    }
    if(!T->lchild && !T->rchild){
        return 1;
    }
    int num=0;
    num+=getLeafNum(T->lchild);
    num+=getLeafNum(T->rchild);
    return num;
}
//打印所有葉子節(jié)點
void  printLeaf(BiTree T){
    if(!T)return;
    //葉子節(jié)點 打印
    if(!T->lchild && !T->rchild){
        putchar(T->data);
        return;
    }
    printLeaf(T->lchild);
    printLeaf(T->rchild);
}
void Traverse(BiTree T,enum TREEWAY treeWay){
    if(T){
        //前序遍歷
        //訪問根結點 (V)；
        //前序遍歷左子樹 (L)；
        //前序遍歷右子樹 (R)
        if(treeWay==PREORDER){
            putchar(T->data);
            Traverse(T->lchild,treeWay);
            Traverse(T->rchild,treeWay);
        //中序遍歷
        //前序遍歷左子樹 (L)；
        //訪問根結點 (V)；
        //前序遍歷右子樹 (R)
        }else if(treeWay==INORDER){
            Traverse(T->lchild,treeWay);
            putchar(T->data);
            Traverse(T->rchild,treeWay);
        //后序遍歷
        //前序遍歷左子樹 (L)；
        //訪問根結點 (V)；
        //前序遍歷右子樹 (R)
        }else if(treeWay==POSTORDER){
            Traverse(T->lchild,treeWay);
            Traverse(T->rchild,treeWay);
            putchar(T->data);
        //層序遍歷：
        //從樹的第一層開始，從上而下逐層遍歷，在同一層中，按從左到右順序逐個訪問；
        }else if(treeWay==LEVEL){
            //關鍵中間變量存放每一層的數(shù)據(jù)
            BiTree temp[100];
            int in=0,out =0;
            temp[in++]=T;
            //每次把這一層存入，然后輸出的時候就把他的左右節(jié)點存入
            //例如一顆完全二叉樹abcdefg  輸出a的時候把bc放入,輸出b的時候把b的孩子放入也就是de，再輸出c并且放入孩子fg，依次這樣，達到層序的要求
            while(in>out){
                if(temp[out]){
                    putchar(temp[out]->data);
                    temp[in++]=temp[out]->lchild;
                    temp[in++]=temp[out]->rchild;
                }
                out++;
            }
        }
    }
}
//以遞歸形式先序遍歷二叉樹
void PreOrderTraverse(BiTree T){
    Traverse(T,PREORDER);
}
//以遞歸形式中序遍歷二叉樹
void InOrderTraverse(BiTree T){
    Traverse(T,INORDER);
}
//以遞歸形式后序遍歷二叉樹
void PostOrderTraverse(BiTree T){
    Traverse(T,POSTORDER);
}
void LevelTraverse1(BiTree T){
    Traverse(T,LEVEL);
}
//層序遍歷
void LevelTraverse(BiTree T){
    if(T){
        Queue *queue=Init_Queue();
        //根節(jié)點入隊
        Push_Queue(queue,T);
        BiTree tmp;
        while(!Queue_IsEmpty(queue)){
            Pop_Queue(queue,&tmp);
            putchar(tmp->data);
            if(tmp->lchild){
                Push_Queue(queue,tmp->lchild);
            }
            if(tmp->rchild){
                Push_Queue(queue,tmp->rchild);
            }
        }


    }

}


//前序非遞歸遍歷
void NoPreOrderTraverse(BiTree T){
    if(!T){
        fprintf(stdout, "樹為空\n");
        return;
    }
    SqStack stack;//棧記錄遍歷過的左子樹
    Init_Stack(&stack);
    BiTree tmp= T;

    while(tmp || !Stack_IsEmpty(stack)){
        //將tmp節(jié)點的左子樹全部壓入棧并打印，
        while(tmp){
            Push(&stack,tmp);
            putchar(tmp->data);
            tmp=tmp->lchild;
        }
        //到葉子結點后，出棧，獲取右子樹
        if(!Stack_IsEmpty(stack)){
            Pop(&stack, &tmp);
            //將 tmp 置為右節(jié)點
            tmp = tmp->rchild;
        }
        //繼續(xù)循環(huán) 壓入右子樹的左子樹。
    }
}

//中序非遞歸遍歷
void NoInOrderTraverse(BiTree T){
    if(!T){
        fprintf(stdout, "樹為空\n");
        return;
    }
    SqStack stack;
    Init_Stack(&stack);
    BiTree tmp= T;
    while(tmp || !Stack_IsEmpty(stack)){
        //將tmp節(jié)點的左子樹壓入棧
        while(tmp){
            Push(&stack,tmp);
            tmp=tmp->lchild;
        }
        //到葉子結點后，出棧，訪問該棧頂結點并打印， 獲取右子樹
        if(!Stack_IsEmpty(stack)){
            Pop(&stack, &tmp);
            putchar(tmp->data);
            //將 tmp 置為右節(jié)點
            tmp = tmp->rchild;
        }
        //繼續(xù)循環(huán) 壓入右子樹的左子樹。
    }
}
//后序非遞歸遍歷
//后序遍歷中，要保證左孩子和右孩子都已被訪問，并且左孩子在右孩子之前訪問才能訪問根結點
void NoPostOrderTraverse(BiTree T){
    if(!T){
        fprintf(stdout, "樹為空\n");
        return;
    }
    SqStack stack;
    Init_Stack(&stack);
    BiTree cur;//當前節(jié)點
    BiTree pre=NULL;//前一次訪問的結點
    BiTree tmp;
    //將根節(jié)點入棧
    Push(&stack, T);
    while(!Stack_IsEmpty(stack)){
        //獲取當前節(jié)點
        cur=stack.top->data;
        //如果當前節(jié)點不存在左孩子和右孩子（相對的根節(jié)點），則可以直接訪問它
        //或者 當前節(jié)點存在左孩子或右孩子，但是其左孩子和右孩子都已經(jīng)被訪問過 則可以直接訪問它
        if((!cur->lchild && !cur->rchild)||(pre && (pre==cur->lchild||pre==cur->rchild))){
            putchar(cur->data);//如果當前結點沒有孩子結點或者孩子結點都已被訪問過
            Pop(&stack, &tmp);
            pre = cur;
        }else{
            //將當前節(jié)點的右孩子和左孩子依次入棧，這樣就保證了每次取棧頂元素的時候，左孩子在右孩子之前別訪問，左孩子和右孩子都在根結點前面被訪問
            if(cur->rchild){
                Push(&stack,cur->rchild);
            }
            if(cur->lchild){
                Push(&stack,cur->lchild);
            }
        }

    }
}
int main()
{
    BiTree tree=NULL;
    printf("請先序輸入二叉樹的節(jié)點數(shù)據(jù)： ");
    CreateBiTree(&tree);
    printf("\n前序遍歷結果為：");
    PreOrderTraverse(tree);
    printf("\n中序遍歷結果為：");
    InOrderTraverse(tree);
    printf("\n后序遍歷結果為：");
    PostOrderTraverse(tree);
    printf("\n層序遍歷結果為：");
    LevelTraverse1(tree);
    printf("\n樹的深度為：%d\n",BiTreeDepth(tree));
    printf("\n樹的葉子節(jié)點個數(shù)為：%d\n",getLeafNum(tree));
    printf("\n獲取所有葉子節(jié)點結果為：");
    printLeaf(tree);

    printf("\n非遞歸前序遍歷結果為：");
    NoPreOrderTraverse(tree);
    printf("\n非遞歸中序遍歷結果為：");
    NoInOrderTraverse(tree);
    printf("\n非遞歸后序遍歷結果為：");
    NoPostOrderTraverse(tree);
    return 0;
}

號為空格

ABD###CE##FG###

image.png