实验报告(程序+截图)

上机实验课（树+图）实验目的：1．掌握二叉树的定义，存储结构的特征；2．掌握二叉树的基本操作，如建立、前序遍历、中序遍历和后序遍历（三者中至少一种熟练掌握）、特殊节点（只有左子树或右子树，只有叶子节点）个数的统计等；实验内容：用递归的方法实现以下算法：1．以二叉链表表示二叉树，建立一棵二叉树，树结构如图2．输出二叉树的前序遍历结果；3．输出二叉树的中序遍历结果（递归+非递归）；4．输出二叉树的后序遍历结果（递归+非递归（兴趣附加题））；5．统计二叉树的叶结点个数；6．统计二叉树的结点个数；7.统计二叉树所有只有左子树的节点个数7．计算二叉树的深度。8．交换二叉树每个结点的左孩子和右孩子（兴趣附加题）；程序：#includestdio.h#includestdlib.htypedefstructnode{structnode*lchild;structnode*rchild;chardata;}bitreenode,*bitree;bitreecreatebitree(){chara;bitreet;scanf(%c,&a);if(a=='#')t=NULL;else{t=(bitree)malloc(sizeof(bitreenode));t-data=a;t-lchild=createbitree();t-rchild=createbitree();}returnt;}voidpreordertraverse(bitreet){if(t){printf(%c,t-data);preordertraverse(t-lchild);preordertraverse(t-rchild);}}voidinordertraverse(bitreet){if(t){inordertraverse(t-lchild);printf(%c,t-data);inordertraverse(t-rchild);}}voidpostordertraverse(bitreet){if(t){postordertraverse(t-lchild);postordertraverse(t-rchild);printf(%c,t-data);}}intcountnode(bitreet){if(t==NULL)return0;return1+countnode(t-lchild)+countnode(t-rchild);}intleafnode(bitreet){intl1,l2;if(t==NULL)return0;elseif(t-lchild==NULL&&t-rchild==NULL)return1;else{l1=leafnode(t-lchild);l2=leafnode(t-rchild);returnl1+l2;}}intonlyleftnode(bitreet){if(t==NULL)return0;else{if(t-lchild==NULL&&t-rchild==NULL)return0;else{if(t-lchild!=NULL&&t-rchild==NULL)return1+onlyleftnode(t-lchild);else{if(t-lchild==NULL&&t-rchild!=NULL)return0+onlyleftnode(t-rchild);elsereturnonlyleftnode(t-lchild)+onlyleftnode(t-rchild);}}}}intheight(bitreet){intu,v;if(t==NULL)return0;u=height(t-lchild);v=height(t-rchild);if(uv)returnu+1;returnv+1;}voidmain(){intm,n,p,q;bitreet;t=createbitree();printf(二叉树建立完成\n);preordertraverse(t);printf(\n);printf(二叉树前序遍历完成\n);inordertraverse(t);printf(\n);printf(二叉树中序遍历完成\n);postordertraverse(t);printf(\n);printf(二叉树后序遍历完成\n);m=countnode(t);printf(树的结点个数为：%d,m);printf(\n);n=leafnode(t);printf(树的叶子结点个数为：%d,n);printf(\n);p=onlyleftnode(t);printf(只有左子树的结点个数为：%d,p);printf(\n);q=height(t);printf(二叉树的深度为：%d,q);printf(\n);}截图：