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

实验四 二叉树的建立与遍历【实验目的】l 掌握二叉树的定义、性质及存储方式，各种遍历算法。【实验内容】采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序遍历的递归操作。分别求所有叶子结点及结点总数的操作。 提示：设计一颗二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针），如ABD#CE#F#，建立二叉树，求出先序、中序和后序遍历序列，求所有叶子及结点总数。【程序源代码】#include#includetypedef char TElemType;typedef int Status;#define OK 1#define 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);int 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) case 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: 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(%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);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);【运行结果分析】【实验收获与心得】 在本次实验中，我对