C语言——二叉树的基本遍历方法

/* 
    二叉树的基本遍历方法
*/
#include <stdio.h>
#include <stdlib.h>

#define type char
#define MAXSIZE 10

typedef struct BiTree {
    type data;
    struct BiTree * lchild;
    struct BiTree * rchild;
}BiNode, *BiTree;

// 访问节点函数
void visit(BiTree node) {
    printf("%c", node -> data);
}

// 先次遍历创建二叉树，无节点用#表示
int create_bitree(BiTree *T)
{
    type ch;
    scanf("%c", &ch);
    if(ch!=‘#‘) {
        *T = (BiNode*) malloc(sizeof(BiNode));
        (*T) -> data = ch;
        create_bitree(& ((*T) -> lchild));
        create_bitree(& ((*T) -> rchild));
    } else {
        *T = NULL;
    }
    return 1;
}

// 递归先序遍历
void pre_order_traversal(BiTree T) {
    if(T!=NULL) {
        visit(T);
        pre_order_traversal(T -> lchild);
        pre_order_traversal(T -> rchild);
    }
}

// 递归中序遍历
void in_order_traversal(BiTree T) {
    if (T != NULL) {
        in_order_traversal(T -> lchild);
        visit(T);
        in_order_traversal(T -> rchild);
    }
}

// 递归后续遍历
void sub_order_traversal(BiTree T) {
    if (T != NULL) {
        sub_order_traversal(T -> lchild);
        sub_order_traversal(T -> rchild);
        visit(T);
    }
}

// 层序遍历
void seq_order_traversal(BiTree T) {
    if (T == NULL)
        return ;
    int front = 0, rear = 0;
    BiTree queue[MAXSIZE];
    queue[(++rear) % MAXSIZE] = T;
    while (rear != front) {
        BiTree tmp = queue[(++front) % MAXSIZE];
        visit(tmp);
        if (tmp -> lchild != NULL)
            queue[(++rear) % MAXSIZE] = tmp -> lchild;
        if (tmp -> rchild != NULL)
            queue[(++rear) % MAXSIZE] = tmp -> rchild;
    }
}

// 非递归先序遍历
void pre_order_traversal2(BiTree T) {
    if (T == NULL)
        return ;
    int front= 0;
    BiTree stack[MAXSIZE];
    BiTree tmp = T;
    while (tmp != NULL || front != 0) {
        if (tmp != NULL) {
            visit(tmp);
            stack[++front] = tmp;
            tmp = tmp -> lchild;
        } else {
            tmp = stack[front--];
            tmp = tmp -> rchild;
        }
    }
}

// 非递归中序遍历
void in_order_traversal2(BiTree T) {
    if (T == NULL)
        return ;
    int front = 0;
    BiTree stack[MAXSIZE];
    BiTree tmp = T;
    while (tmp != NULL || front != 0) {
        if (tmp != NULL) {
            stack[++front] = tmp;
            tmp = tmp -> lchild;
        } else {
            tmp = stack[front--];
            visit(tmp);
            tmp = tmp -> rchild;
        }
    }
}

// 非递归后续遍历
void sub_order_traversal2(BiTree T) {
    if (T == NULL)
        return ;
    int front = 0;
    BiTree stack[MAXSIZE];
    BiTree tmp = T;
    BiTree r = NULL;
    while (tmp != NULL || front != 0) {
        if (tmp != NULL) {
            stack[++front] = tmp;
            tmp = tmp -> lchild;
        } else {
            tmp = stack[front];       
            if (tmp -> rchild != NULL && tmp -> rchild != r) {
                tmp = tmp -> rchild;
                stack[++front] = tmp;
                tmp = tmp -> lchild;
            } else {
                tmp = stack[front--];
                visit(tmp);
                r = tmp;
                tmp = NULL;
            }
        }
    }
    
}

int Equal(BiNode* T1, BiNode* T2) {
    if (T1 == NULL && T2 == NULL)
        return 1;
    else if (T1 == NULL || T2 == NULL)
        return 0;
    else
        if (T1 -> data != T2 -> data)
            return 0;
        else {
            int lflag = Equal(T1 -> lchild, T2 -> lchild);
            int rflag = Equal(T1 -> rchild, T2 -> rchild);
            return lflag && rflag;
        }
}

void GetPreSeq(BiTree T, int k) {
    static int count = 1;
    if (count > k)
        return ;
    if(T!=NULL) {
        if (count == k)
            printf("%c\n", T -> data);
        count++;
        GetPreSeq(T -> lchild, k);
        GetPreSeq(T -> rchild, k);
    }
}

int main(int argc, char const *argv[]) {
    BiTree T;
    BiTree T1;

    printf("请输入第一颗树(无节点用#表示):\n");
    create_bitree(&T);
 
    printf("递归先序遍历：\n");
    pre_order_traversal(T);
    printf("\n");
    
    GetPreSeq(T, 0);



    // printf("请输入第二颗树:\n");
    // getchar();
    // create_bitree(&T1);
    // printf("层序遍历：\n");
    // seq_order_traversal(T1);
    // printf("\n");
    // seq_order_traversal(T1);
    // printf("\n");

    // printf("递归先序遍历：\n");
    // pre_order_traversal(T);
    // printf("\n");
    // pre_order_traversal(T1);
    // printf("\n");
    // printf("递归中序遍历：\n");
    // in_order_traversal(T);
    // printf("\n");
    // in_order_traversal(T1);
    // printf("\n");
    // printf("递归后序遍历：\n");
    // sub_order_traversal(T);
    // printf("\n");
    // sub_order_traversal(T1);
    // printf("\n");

    // printf("是否相似？  %d\n", Equal(T, T1));
    // printf("层序遍历：\t");
    // seq_order_traversal(T);
    // printf("\n");
    // printf("非递归先序遍历：");
    // pre_order_traversal2(T);
    // printf("\n");
    // printf("非递归中序遍历：");
    // in_order_traversal2(T);
    // printf("\n");
    // printf("非递归后序遍历：");
    // sub_order_traversal2(T);
    // printf("\n");
    system("pause");
    return 0;
}

C语言——二叉树的基本遍历方法

原文：https://www.cnblogs.com/toughtful/p/14105845.html