c语言遍历二叉树

admin

[mw_shl_code=c,true]#include<iostream>
#include<cstdio>
#include<stdlib.h>
using namespace std;


#define Maxsize 50
typedef char ElemType;
typedef struct BiTNode* ElemTypes;
const char* str = "ABDH#K###E##CFI###G#J##";
int index = 0;

//创建二叉树
typedef struct BiTNode {
        ElemType data;
        struct BiTNode* lchild;
        struct BiTNode* rchild;
}BiTNode;


// 创建栈
typedef struct {
        struct BiTNode* data[Maxsize];
        int top;
}StackBiTNode;

//初始化栈
void initStack(StackBiTNode* &s) {
        s = (StackBiTNode*)malloc(sizeof(StackBiTNode));
        s->top = -1;
}

//入栈
void Push(StackBiTNode*& s, ElemTypes t) {
        if (s->top >= Maxsize)
                return;
        else {
                s->top++;
                s->data[s->top] = t;
        }
}
//出栈
void Pop(StackBiTNode*& s, ElemTypes  &r) {
        if (s->top == -1)
                return;
        else {
                r = s->data[s->top];
                s->top--;
        }
}
// 判断栈是否为空
bool StackEmpty(StackBiTNode* s) {
        return(s->top == -1);
}

// 获取栈顶元素
struct BiTNode* GetElemType(StackBiTNode* s) {
        return s->data[s->top];
}

//先序遍历创建二叉树
void PreCreateBiTNode(BiTNode* &B) {
        char ch = str[index++];
        if (ch == '#')
                B = NULL;
        else {
                B = (BiTNode*)malloc(sizeof(BiTNode));
                B->data = ch;
                PreCreateBiTNode(B->lchild);
                PreCreateBiTNode(B->rchild);
        }
}

//先序递归遍历二叉树
void PreOrderBiTNode(BiTNode* B) {
        if (B == NULL)
                return;
        else {
                cout << B->data;
                PreOrderBiTNode(B->lchild);
                PreOrderBiTNode(B->rchild);
        }
}

//中序递归遍历二叉树
void MidOrderBiTNode(BiTNode* B) {
        if (B == NULL)
                return;
        else {
                MidOrderBiTNode(B->lchild);
                cout << B->data;
                MidOrderBiTNode(B->rchild);
        }
}

//后序遍历递归实现
void PostOrderBiTNode(BiTNode* B) {
        if (B == NULL)
                return;
        else {
                PostOrderBiTNode(B->lchild);
                PostOrderBiTNode(B->rchild);
                cout << B->data;
        }
}

//先序遍历非递归实现
void PreOrderBiTNode1(BiTNode* B) {
        StackBiTNode* S;
        struct BiTNode* e;
        initStack(S);
        Push(S, B);
        while (!StackEmpty(S)) {
                Pop(S, e);
                B = e;
                cout << e->data;
                if (B->rchild) {
                        Push(S, B->rchild);
                }
                if (B->lchild) {
                        Push(S, B->lchild);
                }
        }
}


//中序遍历非递归
BiTNode* GoForBiTNode(BiTNode* B, StackBiTNode* S) {
        if (!B)
                return NULL;
        while (B->lchild) {
                Push(S, B);
                B = B->lchild;
        }
        return B;
}
void MidOrderBiTNode1(BiTNode* B) {
        StackBiTNode *S;
        initStack(S);
        struct BiTNode* e;
        BiTNode* t = GoForBiTNode(B, S);
        while (t) {
                cout << t->data;
                if (t->rchild) {
                        t = GoForBiTNode(t->rchild, S);
                }
                else if (!StackEmpty(S)) {
                        Pop(S, e);
                        t = e;
                }
                else {
                        t = NULL;
                }       
        }
}

//后序遍历递归实现
void PostOrderBiTNode1(BiTNode* B) {
        StackBiTNode *S;
        struct BiTNode* e;
        initStack(S);
        bool flag;
        BiTNode* p, * r;
                p = B;
                do {
                        while (p != NULL) {
                                Push(S, p);
                                p = p->lchild;
                        }
                        r = NULL;
                        flag = true;
                        while (!StackEmpty(S) && flag) {
                                p = GetElemType(S);
                                if (p->rchild == r) {
                                        cout << p->data;
                                        Pop(S, e);
                                        p = e;
                                        r = p;
                                }
                                else {
                                        p = p->rchild;
                                        flag = false;
                                }
                        }
                } while (!StackEmpty(S));
                cout << endl;
}

int main() {

        StackBiTNode* s;
        BiTNode* B;
        initStack(s);
        PreCreateBiTNode(B);  //创建二叉树
        cout << "*************__二叉树递归遍历__*****************"<<endl;
        cout << "先序遍历：";
        PreOrderBiTNode(B);
        cout << endl;
        cout << "中序遍历：";
        MidOrderBiTNode(B);
        cout << endl;
        cout << "后序遍历：";
        PostOrderBiTNode(B);
        cout << endl;
        cout << "*************__二叉树非递归遍历__*****************" << endl;
        cout << "先序遍历:";
        PreOrderBiTNode1(B);
        cout << endl;
        cout << "中序遍历：";
        MidOrderBiTNode1(B);
        cout << endl;
        cout << "后序序遍历:";
        PostOrderBiTNode1(B);
        cout << endl;
        system("pause");
        return 0;
}

[/mw_shl_code]