c语言六种方法遍历二叉树,C语言——二叉树的基本遍历方法

/*

二叉树的基本遍历方法

*/

#include

#include

#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;

}

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