二叉树的建立并求出叶子节点数目.docVIP

1二叉树采用链表存储结构，实现建立、遍历（先序、中序、后序）、求结点总数、叶子数、度为1.2的结点数。 前几天写的，输入二叉树的广义表形式，建立二叉树的链式存储。输出的是中序。有注释。例如输入：a(b,c(d,e(f)),g,h(i)) #includestdio.h #includestdlib.h int n=0; //全局变量 struct tree //二叉树结构体 { char data; struct tree *lc; struct tree *rc; }; tree *creat(char a[]) //创建树的二叉树 { tree *h; h=(tree *)malloc(sizeof(tree)); h-lc=NULL; h-rc=NULL; if(a[n]!=)a[n]!=(a[n]!=,) //当a[n]为字母存入a[] { h-data=a[n]; n++; } if(a[n]==() //a[n]为左括弧对h-lc递归操作 { n++; h-lc=creat(a); } if(a[n]==,) //a[n]为逗号对h-rc递归操作 { n++; h-rc=creat(a); return h; } if(a[n]==)) //a[n]为右括弧返回h { n++; return h; } else return h; } void print(tree *h) //二叉树中序输出 { if(h!=NULL) { print(h-lc); printf(%c,h-data); print(h-rc); } } int high(char a[]) //判断树的高度 { int i=0,max=0,p=0; while(a[i]!=0) { if(a[i]==() { p++; if(maxi) max=p; } if(a[i]==)) p--; i++; } if(p!=0) { printf(左右括弧数不等,输入错误\n); //判断左右括弧数是否相等 exit(1); } return max+1; } void main() //主函数 { int i=0; tree *h; char a[50]={0}; gets(a); while(a[i]!=0) //判断各种可能出现的输入错误 { if(i==0(a[i]==(||a[i]==)||a[i]==,)) //判断数组首元素是否为字母 { printf(首节点错误\n); exit(1); } if(a[i]==() //左括弧之前一定是字母 { if(a[i-1]==(||a[i-1]==)||a[i-1]==,) { printf(输入错误\n); exit(1); } } if(a[i]!=(a[i]!=)a[i]!=,) //两个字母不能在一起 { if(a[i+1]!=(a[i+1]!=)a[i+1]!=,) { printf(输入错误,两个字母不能在一起\n); exit(1); } } i++; } h=creat(a); //创建树 printf(该树的高度为:%d\n,high(a)); printf(该二叉树的中序输出为:); print(h); printf(\n); } 2一棵二叉树中共有70个叶子结点与80个度为1的结点，则该二叉树中的总结点数为？给出的答案是219 求高手解析 假设n表示二叉树的所有结点数，n0表示度为0的结点(叶子结点)，n1表示度为1的结点，n2表示度为2的结点，由二叉树的性质有： n0 = n2 + 1 已知n0 = 70， 则n2 = n0 -1 = 69 而 n = n0 + n1 + n2 = 70 + 80 + 69 = 219 创建一棵二叉树，以二叉链表作存储结构，实现先根遍历算法 2、创建一棵二叉树，实现先根遍历算法、中根 你需要的东西这里面都包含了，你自己看哪里用得上就摘一段下来吧。 // 数据结构.cpp : 定义控制台应用程序的入口点。 // #include stdafx.h int _tmain(int argc, _TCHAR* argv[]) { return 0; } #includestdio.h #includestdlib.h #define MAX 20 #define NULL 0 typedef char ElemType; typedef int Status; typedef enum{lin