实验四 二叉树的建立与遍历

1、实验四 二叉树的建立与遍历【实验目的】l 掌握二叉树的定义、性质及存储方式，各种遍历算法。【实验内容】采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的递归操作。分别求所有叶子结点及结点总数的操作。 提示：设计一颗二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树，求出先序、中序和后序遍历序列，求所有叶子及结点总数。【程序源代码】#include<stdio.h>#include<stdlib.h>typedef char TElemType;typedef int Status;#define OK 1#de

2、fine ERROR 0#define OVERFLOW 0typedef struct BiTNode TElemType data;struct BiTNode *lchild, *rchild;BiTNode , *BiTree;Status CreateBiTree(BiTree &BT);void CountLeaves(BiTree BT, int &count);int NodeCount(BiTree BT);void PreOrder(BiTree BT);void InOrder(BiTree BT);void PostOrder(BiTree BT);in

3、t main()BiTree BT;int choice,cho;int logo = 1;printf("输入二叉树结点，以'#'为空指针n");CreateBiTree(BT);do printf("t 1:遍历二叉树n"); printf("t 2：二叉树总结点数及叶子节点数n"); printf("t 3：退出程序n "); printf("t 输入选项: "); scanf("%2d",&choice); switch(choice) cas

4、e 1: printf("1:先序遍历n"); printf("2:中序遍历n"); printf("3:后序遍历n"); scanf("%2d",&cho); switch(cho) case 1: PreOrder(BT); printf("n"); break;case 2: InOrder(BT); printf("n"); break; case 3: PostOrder( BT); printf("n"); break; default

5、: printf("输入错误!n"); break;case 2: int count; printf("总结点数为:%2dn", NodeCount(BT); CountLeaves(BT, count); printf("叶子结点数为:%2dn", count); break;case 3 :exit(0);break;default:printf("输入错误!n"); while(logo=1);return 0;Status CreateBiTree(BiTree &BT)char ch;scanf

6、("%c", &ch);if (ch = '#') BT = NULL;elseif (!(BT = (BiTree)malloc(sizeof(BiTNode)exit(OVERFLOW);BT->data = ch;CreateBiTree(BT->lchild);CreateBiTree(BT->rchild);return OK;void PreOrder(BiTree BT)if (BT != NULL)printf("%c ", BT->data);PreOrder(BT->lchild)

7、;PreOrder(BT->rchild);void InOrder(BiTree BT)if (BT != NULL)PreOrder(BT->lchild);printf("%c ", BT->data);PreOrder(BT->rchild);void PostOrder(BiTree BT)if (BT != NULL)PreOrder(BT->lchild);PreOrder(BT->rchild);printf("%c ", BT->data);void CountLeaves(BiTree BT,int &count)if (BT)if (!BT->lchild && !BT->rchild)count+;CountLeaves(BT->lchild, count);CountLeaves(BT->rchild, count);int NodeCount(BiTree BT)/统计总结点数 if (BT = NULL)return 0;elsereturn (NodeCount(BT->lchild) + NodeCount(BT->rchild) + 1);【运行结果分析