二叉树操作输出深度结点数叶结点数递归.doc

实验三 二叉树的操作及应用 一、实验目的 1、掌握二叉树的特点，以及二叉链表的结构 2、熟练掌握二叉树的各种操作，如建立、遍历、查找和输出 3、利用己经掌握的进行实际应用 二、实验要求 1、 编写程序实现二叉树的各种运算，并在此基础上设计主函数，使其完成如下功能： （1）按先序建立二叉树，如“ABC□□DE□G□□F□□□”，（□表示空格）。 （2）建立二叉树后，判断二叉树空否，同时输出二叉树的深度。 （3）建立二叉树后，判断二叉树空否，同时输出二叉树的结点数。 （4）建立二叉树后，判断二叉树空否，同时输出二叉树的叶子点数。 2、编写一个子函数，用非递归算法中序遍历二叉树。 三、程序运算结果截图 四、程序源代码 1. #include stdio.h #include stdlib.h struct BinTreeNode; typedef struct BinTreeNode *PBinTreeNode; struct BinTreeNode { char info; PBinTreeNode llink; PBinTreeNode rlink; }; typedef struct BinTreeNode *BinTree; BinTree CreateBiTree() { char ch; BinTree t; scanf(%c,ch); if(ch== ) t=NULL; else { t=(BinTree)malloc(sizeof(struct BinTreeNode)); t-info=ch; t-llink=CreateBiTree(); t-rlink=CreateBiTree(); } return t; } int IsEmptyTree(BinTree t) //创建二叉树 { if(t==NULL) return 0; else return 1; } int GetDepth(BinTree t) //返回二叉树的深度 { int l,r,c; l=r=c=0; if(t) { l=GetDepth(t-llink); r=GetDepth(t-rlink); c=(lr?l:r); return c+1; } else return 0; } int Node(BinTree t) //返回二叉树的结点数 { if(t) return Node(t-llink)+Node (t-rlink)+1; else return 0; } int Leaf(BinTree t) //返回二叉树的叶子点数 { if(t) { if ((t-llink==NULL)(t-rlink==NULL) ) return 1; else return Leaf(t-llink)+Leaf(t-rlink); } else return 0; } main() { BinTree t; printf(please input:\n); t=CreateBiTree(); if(IsEmptyTree==0) printf(二叉树为空); else printf(二叉树不为空\n); printf(二叉树的深度是:\n); printf(%d:\n,GetDepth(t)); printf(二叉树的结点数是:\n); printf(%d:\n,Node(t)); printf(二叉树的叶子点数是:\n); printf(%d:\n,Leaf(t)); } 2. #include stdio.h #include stdlib.h struct BinTreeNode; typedef struct BinTreeNode *PBinTreeNode; struct BinTreeNode { char info; PBinTreeNode llink; PBinTreeNode rlink; }; struct BinTreeNode BinTreeNode; typedef struct BinTreeNode *BinTree; #inclu