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) { PrintTree(bt->RChild, nLayer + 1); levelspace(nLayer); Printdata(bt); PrintTree(bt->LChild, nLayer + 1); } }