# include <stdio.h>
# include <stdlib.h># include <conio.h># define STACK_MAX_SIZE 20# define NULL 0struct BTreeNode{ char data;struct BTreeNode *left;struct BTreeNode *right;};//
void initBTree(struct BTreeNode* *bt){ *bt = NULL;return ;}//****************************************************////设计算法返回二叉树中值为x的结点所在的层号，若二叉树中没有该结点，则返回0。//***************************************************//int NodeLevel(BTreeNode *bt,char x){ int i,j;if(bt == NULL)return 0;else if(bt ->data == x)return 1;else { i = NodeLevel(bt ->left,x);if(i>=1) i++;j = NodeLevel(bt ->right,x);if(j>=1) j++;if(i>=1 || j>=1)return i > j ? i : j;else return 0;}}//void createBTree(struct BTreeNode* *bt,char *a){ struct BTreeNode *p;struct BTreeNode *s[STACK_MAX_SIZE];int top = -1;int k;int i = 0;*bt = NULL;//while(a[i]!= '\0'){ switch(a[i]){ case' ':break;case'(':if(top == STACK_MAX_SIZE - 1){ printf("栈空间太小!");exit(1);}top++;s[top] = p;k = 1;break;case')':if(top == -1){ printf("二叉树广义表字符串错误!");exit(1);}top--;break;case',':k = 2;break;default:p = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));p ->data = a[i];p ->left = p ->right = NULL;if(*bt == NULL){ *bt = p;}else{ if(k == 1){ s[top] ->left = p;}else{ s[top] ->right = p;}}}i++;}return;}//检查二叉树是否为空 int emptyBTree(struct BTreeNode *bt){ if(bt == NULL){ return 1;}else{ return 0;}}//求二叉树深度
int BTreeDepth(struct BTreeNode *bt){ if(bt == NULL){ return 0;}else{ int dep1 = BTreeDepth(bt ->left);int dep2 = BTreeDepth(bt ->right);if(dep1 < dep2){ return dep1 + 1;}else{ return dep2 + 2;}int NodeNum;NodeNum = NodeNum + 1;}}//在二叉树中查找值为x的结点，若存在则返回元素的存储位置
char *findBTree(struct BTreeNode *bt,char x){ if(bt == NULL){ return NULL;}else{ if(bt ->data == x){ return &(bt ->data);}else{ char *p;if(p = findBTree(bt ->left,x)){ return p;}if(p = findBTree(bt ->right,x)){ return p;}return NULL;}}}//计算叶子结点数int Searchlcaf(struct BTreeNode *bt){ if(bt == NULL)return 0;else{ if(bt ->left == NULL && bt ->right == NULL){ return 1;}else{ return(Searchlcaf(bt ->left) + Searchlcaf(bt ->right));}}}//计算二叉树的结点个数
int Counter(struct BTreeNode *bt){ int n1,n2,num;if(bt == NULL){ return 0;}else{ n1 = Counter(bt ->left);n2 = Counter(bt ->right);num = n1 + n2 +1;return num;}} //先序遍历void PreOrderTraverse(struct BTreeNode *bt)
{ if(bt == NULL)return;printf("%C",bt ->data);PreOrderTraverse(bt ->left);PreOrderTraverse(bt ->right);}//中序遍历void InOrderTraverse(struct BTreeNode *bt)
{ if(bt == NULL)return;InOrderTraverse(bt ->left);printf("%C",bt ->data);InOrderTraverse(bt ->right);}//后序遍历
void PostOrderTraverse(struct BTreeNode *bt)
{ if(bt == NULL)return;PostOrderTraverse(bt ->left);PostOrderTraverse(bt ->right);printf("%C",bt ->data);}//清除二叉树，使之变成一颗空二叉树
void clearBTree(struct BTreeNode *bt)
{ if(bt != NULL){ clearBTree(((bt) ->left));clearBTree(((bt) ->right));free(bt);bt = NULL;}return;}void ShowA(struct BTreeNode *bt)
{ if(bt != NULL){ printf("%c",bt ->data);ShowA(bt ->left);ShowA(bt ->right);}}//
void ShowB(struct BTreeNode *bt){ if(bt != NULL){ ShowB(bt ->left);printf("%c",bt ->data);ShowB(bt ->right);}}void ShowC(struct BTreeNode *bt)
{ if(bt != NULL){ ShowC(bt ->left);ShowC(bt ->right);printf("%c",bt ->data);}}//void Revolute(struct BTreeNode *bt){ BTreeNode *q;if(bt != NULL){ Revolute(bt ->left);Revolute(bt ->right);q = bt ->left;bt ->left = bt ->right;bt ->right = q;}} void main(){ struct BTreeNode *bt;initBTree(&bt);//初始化二叉树char *a = "A(B(C),D(E(F,G),H(,I)))";createBTree(&bt,a);printf("01111653-钱伯江");printf("\n\n");int m;
m = BTreeDepth(bt);printf("二叉树的深度为：");printf("%d\n", m);printf("\n");
printf("前序遍历的结果是：");PreOrderTraverse(bt);printf("\n");printf("中序遍历的结果是：");
InOrderTraverse(bt);printf("\n");printf("后序遍历的结果是：");
PostOrderTraverse(bt);printf("\n\n");int d;
d = Counter(bt);printf("二叉树结点的总个数为：");printf("%d\n", d);printf("\n");int n;//n为叶子结点的个数
n = Searchlcaf(bt);printf("叶子结点(度为0)的个数为：");printf("%d\n", n);//printf("\n");int b;//b为度为2的结点个数
b = n - 1;printf("度为2的个数为：");printf("%d\n", b);//printf("\n");//s为度为1的结点int x;x = Counter(bt);int y;y = Searchlcaf(bt);int l;l = x - y;int s;s = l - b;printf("度为1的个数为：");printf("%d\n", s);printf("\n");printf("二叉树交换左右子树后，遍历结果如下。\n");printf("\n");printf("前序遍历结果：");Revolute(bt);ShowA(bt);printf("\n");printf("中序遍历结果：");ShowB(bt);printf("\n");printf("后序遍历结果：");ShowC(bt);printf("\n");
char t;int h;scanf("%s",&t);NodeLevel(bt,t); h=NodeLevel(bt,t);printf("%d\n",h);
}