C语言二叉树实现：创建、遍历、打印树形

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

//结构体定义 typedef struct Node { char data; struct Node *LChild; struct Node *RChild; }BinNode,*BinTree;

//函数声明 int menu_select(); void CreateBinTree(BinTree *bt); void PreOrder(BinTree bt); void InOrder(BinTree bt); void PrintTree(BinTree bt,int nLayer);

// main()函数 int main() { BinTree bt = NULL; int nLayer=0;

for (;;) {
	switch(menu_select()) {
	case 1:
		printf("1、建立二叉树\n");
		CreateBinTree(&bt);
		break;
	case 2:
		printf("2、先序遍历\n");
		PreOrder(bt);
		break;
	case 3:
		printf("3、中序遍历\n");
		InOrder(bt);
		break;
	case 4:
		printf("4、打印树形\n");
		PrintTree(bt,nLayer);
		break;
	case 0:
		printf("再见！！\n");
		free(bt);
		return 0;
	}
}

}

//菜单驱动程序 int menu_select() { int sn; printf("=========功能菜单============\n"); printf(" 1、建立二叉树\n"); printf(" 2、先序遍历\n"); printf(" 3、中序遍历\n"); printf(" 4、打印树形\n"); printf(" 0、退出程序\n"); printf("==============================\n"); printf(" 请选择0--4：");

for (;;) {
	scanf("%d", &sn);
	getchar();
	if (sn < 0 || sn > 4)
		printf("\n输入选择错误，请重新选择 0--4：");
	else
		break;
}
return sn;

}

/* TODO： 功能描述：创建二叉树操作 1、按扩展的先序次序输入二叉树中结点的值， #字符表示空子树，创建二叉链表表示的二叉树 (BinTree) malloc(sizeof(BinNode))， 将字符赋给节点中的data， 将二叉树的左右子树置为NULL 例： 输入格式：AB##C## 二叉树： A B C 参数：(BinTree *bt) 树的指针的指针 返回值：void */ void CreateBinTree(BinTree *bt) { char ch; scanf("%c","&ch); getchar(); if(ch == '#') *bt = NULL; else { *bt = (BinTree)malloc(sizeof(BinNode)); (*bt)->data = ch; CreateBinTree(&((*bt)->LChild)); CreateBinTree(&((*bt)->RChild)); } }

void Visit(BinTree bt) { if (bt!=NULL) printf("%2c",bt->data); }

/* TODO： 功能描述：先序遍历二叉树操作 1、先序访问根节点，遍历左子树，遍历右子树 2、打印数据调用函数 void Visit(BinTree bt) 参数：(BinTree bt) 树的指针 返回值：void */ void PreOrder(BinTree bt) { if(bt != NULL) { Visit(bt); PreOrder(bt->LChild); PreOrder(bt->RChild); } }

/* TODO： 功能描述：中序遍历二叉树操作 1、中序遍历左子树，根节点，遍历右子树 2、打印数据调用函数 void Visit(BinTree bt) 参数：(BinTree bt) 树的指针 返回值：void */ void InOrder(BinTree bt) { if(bt != NULL) { InOrder(bt->LChild); Visit(bt); InOrder(bt->RChild); } }

void Printdata(BinTree bt) { if (bt!=NULL) printf("%2c\n",bt->data); } void levelspace(int nLayer) { int i; for(i=0;i<nLayer;i++) printf(" "); }

/* TODO： 功能描述：横向打印树形操作 1、遍历右子树，根节点，遍历左子树 2、非同层节点调用 void levelspace(int nLayer) 3、打印数据调用函数 void Printdata(BinTree bt) 参数：(BinTree bt,int nLayer) 树的指针与节点层次 返回值：void */ void PrintTree(BinTree bt,int nLayer) { if(bt == NULL) return; PrintTree(bt->RChild,nLayer+1); levelspace(nLayer); Printdata(bt); PrintTree(bt->LChild,nLayer+1); }

//以下为辅助函数

void Visit(BinTree bt) { if (bt!=NULL) printf("%2c",bt->data); }

void Printdata(BinTree bt) { if (bt!=NULL) printf("%2c\n",bt->data); }

void levelspace(int nLayer) { int i; for(i=0;i<nLayer;i++) printf(" "); }