数据结构 二叉树各种基本运算的实现_二叉树的基本运算数据结构

数据结构 二叉树各种基本运算的实现

#include<stdio.h>
#include<stdlib.h>
#define MaxSize 100;
int Width[10] = { 0 };
int yezi = 0;
typedef struct node
{
	char data;
	struct node *lchild;
	struct node *rchild;
}BTNode;

void CreateBTNode(BTNode *&b, char *str)  //创建二叉树
{
	BTNode *St[100], *p;
	int top = -1, k, j = 0;
	char ch;
	b = NULL;              //创建二叉树初始为空
	ch = str[j];
	while (ch != '\0')     //循环扫描str中每个字符
	{
		switch (ch)
		{
		case'(':top++; St[top] = p; k = 1; break;       //开始处理左孩子节点
		case')':top--; break;                           
		case',':k = 2; break;                           //开始处理右孩子节点
		default:p = (BTNode *)malloc(sizeof(BTNode));
			p->data = ch; p->lchild = p->rchild = NULL;
			if (b == NULL)  //若尚未建立根节点
				b = p;      //*p为二叉树的根节点
			else            //若已建立二叉树根节点
			{
				switch (k)
				{
				case 1:St[top]->lchild = p; break;
				case 2:St[top]->rchild = p; break;
				}
			}
		}
		j++;
		ch = str[j];
	}
}
void DispBTNode(BTNode *b)      //输出二叉树
{
	if (b != NULL)
	{
		printf("%C", b->data);
		if (b->lchild != NULL || b->rchild != NULL)
		{   
			printf("(");                            //有孩子节点才输出"("
			DispBTNode(b->lchild);                  //递归处理左子树
			if (b->rchild != NULL) printf(",");     //有右孩子节点才输出","
			DispBTNode(b->rchild);                  //递归处理右子树
			printf(")");                            //有孩子节点才输出")"
		}
	}
}
BTNode *FindNode(BTNode *b, char x)   //查找节点
{
	BTNode *p;
	if (b == NULL)           //若此时的节点为空返回NULL
		return NULL;
	else if (b->data == x)   //若在找到该节点，返回该节点的指针
		return b;
	else
	{
		p = FindNode(b->lchild, x);         //递归处理左子树
		if (p != NULL)                      //若在左子树中找到了
			return p;
		else                                //若未在左子树中找到，递归处理右子树
			return FindNode(b->rchild, x);  
	}
}
int BTNodeHeight(BTNode * b)  //求二叉树的高度（即深度）
{
	int lchildd, rchildd; 
	if (b == NULL)            //空树的高度为0
		return(0);
	else
	{
		lchildd = BTNodeHeight(b->lchild);   //求左子树的高度为lchildh
		rchildd = BTNodeHeight(b->rchild);   //求右子树的高度为rchildh
		return(lchildd > rchildd) ? (lchildd + 1) : (rchildd + 1);   //三目运算符返回更深的子树深度
	}
}
int WidthofBTNode(BTNode * b, int floor)  //求每一层二叉树的宽度
{
	if (b != NULL)
	{
		Width[floor]++;       //若该节点不为空，该层节点数+1
		WidthofBTNode(b->lchild, floor + 1);  //递归处理左子树
		WidthofBTNode(b->rchild, floor + 1);  //递归处理右子树
	}
	else
		return 0;
}
int Elemnumber(BTNode * b)   //求二叉树的节点个数
{
	int lchildd, rchildd;    
	if (b == NULL)      //若该节点为空，返回0
		return 0;
	else
	{
		lchildd = Elemnumber(b->lchild);   //递归处理左子树
		rchildd = Elemnumber(b->rchild);   //递归处理右子树
		return(lchildd + rchildd + 1);     //返回所有的左、右孩子节点个数加根节点个数（即所有节点个数）
	}
}
int Yezinumber(BTNode * b)   //求叶子节点个数
{
	if (b != NULL)
	{
		if ((b->lchild&&b->rchild) != NULL)   //若左右孩子节点都不为空递归处理左右子树叶子节点个数之和
			return (Yezinumber(b->lchild) + Yezinumber(b->rchild)); 
		else                                   //其他情况
			return (Yezinumber((b->lchild > b->rchild) ? (b->lchild) : (b->rchild))); 
	}
	else
		return 1;
}

int main()
{
	int n;         
	int max = 0;
	BTNode *tree;   //设置头节点
	char s[100] = "A(B(D,E(,H(J,K(L,M(,N))))),C(F,G(,I)))";   //二叉树的值
	BTNode *Elem;  //用于从子函数中传递指针
	char *p;    
	p = s;         //设置子函数传递字符指针
	CreateBTNode(tree, p);
	printf("\n二叉树为:\n");
	DispBTNode(tree);
	printf(" \n");
	Elem = FindNode(tree, 'H');
	printf(" \n\n");
	printf("H参数的左右节点的值分别为:%3c%3c\n\n", Elem->lchild->data, Elem->rchild->data);
	n = BTNodeHeight(tree);
	printf("二叉树的深度为:%3d\n\n", n);
	WidthofBTNode(tree, 1);
	for (n = 1; n <= BTNodeHeight(tree); n++)   //循环比较宽度最大的二叉树层即为二叉树的宽度
		if (max<Width[n])
			max = Width[n];
	printf("二叉树的宽度为:%3d\n\n", max);
	n = Elemnumber(tree);
	printf("二叉树的所有节点数:%3d\n\n", n);
	n = Yezinumber(tree);
	printf("所有叶子节点个数:%3d\n\n", n);
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151