王道数据结构P191关于二叉树的算法归纳

发表于 更新于 分类于 阅读次数： Waline： 本文字数： 901 阅读时长 ≈ 3 分钟

说在前面

本文是王道数据结构P191的10个算法例题归纳，二叉树的存储结构为二叉链表。

1
2
3
4
5
typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

统计二叉树中度为1的结点个数

1
2
3
4
5
6
7
8
9
10
11
int NodeCount1( BiTree T){
if(T==NULL) 
{
    return 0;
}
if(T->lchild==NULL&&T->rchild!=NULL||T->rchild==NULL&&T->lchild!=NULL)
{
    return 1+NodeCount1(T->lchild)+NodeCount1(T->rchild);
}
return NodeCount1(T->lchild)+NodeCount1(T->rchild);
}

给定一个二叉树，当根仅具有一个孩子时，代表根度为1，统计一次并递归寻找子树度为1的根；当根有两个孩子，不统计递归寻找子树度为1的根。

也可以用非递归方法，使用队列层次遍历。

统计二叉树中度为2的结点个数

1
2
3
4
5
6
7
8
9
10
11
int NodeCount2( BiTree T){
if(T==NULL) 
{
    return 0;
}
if(T->lchild==NULL&&T->rchild!=NULL||T->rchild==NULL&&T->lchild!=NULL)
{
    return NodeCount2(T->lchild)+NodeCount2(T->rchild);
}
return 1+NodeCount2(T->lchild)+NodeCount2(T->rchild);
}

统计二叉树中度为0的结点个数

1
2
3
4
5
6
7
8
9
10
11
int NodeCount0( BiTree T){
if(T==NULL) 
{
    return 0;
}
if(T->lchild==NULL&&T->rchild==NULL)
{
    return 1;
}
return NodeCount0(T->lchild)+NodeCount0(T->rchild);
}

统计二叉树的高度

1
2
3
4
5
6
7
8
9
10
11
int Height(BiTree T)
{
	if (T == NULL)
		return 0;
	int ldep = Height(T->lchild);	//结点左子树高度
	int rdep = Height(T->rchild);	//结点右子树高度
	if (ldep > rdep)	//取二者中更大的+1即树的高度，+1是因为根结点算一层
		return ldep + 1;
	else
		return rdep + 1;
}

统计二叉树的宽度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void LevelWidth(BiTree T, int a[], int h)	//求每一层的宽度
{	//第一次调用为LevelWidth(T,a,1);
	if(T!=NULL)
	{
		a[h] += 1;
		LevelWidth(T->lchild, a, h + 1);
		LevelWidth(T->rchild, a, h + 1);
	}
}
int Width(BiTree T)	
{
	int a[MaxSize + 1], h = 1;
	for (int i = 0; i <= MaxSize; i++)
		a[i] = 0;
	LevelWidth(T, a, h);	//调用求每一层宽度的函数，把宽度保存在数组a[]里
	int wid = a[0];
	for (int i = 1; i <= MaxSize; i++)	//遍历数组a[i]求最大值，即树的宽度
		if (a[i] > wid) 
			wid = a[i];
	return wid;
}

从二叉树中删去所有的叶结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void Del_0(BiTree T)
{
	BiTNode *p = T;
	if((p->lchild ==NULL&& p->rchild ==NULL)|| p ==NULL)
	{
		free(p);
		return;
	}
	else if(p->lchild->lchild ==NULL&& p->lchild->rchlid ==NULL)
	{
		free(p->lchild);
  		p->lchild =NULL;//⽗节点左孩⼦指针置空
	}
	else if(p->rchild->lchild ==NULL&& p->rchild->rchlid ==NULL)
	{
		free(p->rchild);
    	p->rchild =NULL;//⽗节点右孩⼦指针置空
	}
	Del_0(T->lchild);
	Del_0(T->rchild);
}

首先叶子是指左右孩子都没有的结点。

注意此代码为递归，只会向内层深⼊，所以删除完叶⼦结点，使原分⽀结点变为叶⼦结点，但不会再继续删除。

计算指定结点*p所在的层次

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int GetLevel(BiTree T, BiTNode *p)		//计算指定结点*p所在的层次
{
	if (T == NULL)
		return 0;
	if (T == p)
		return 1;	//找到所在层,第一层
	int depl = GetLevel(T->lchild, p);
	int depr = GetLevel(T->rchild, p);
	if (depl || depr)
	{
		if (depl > depr)
			return 1 + depl;
		else
			return 1 + depr;
	}
	return 0;
}

计算二叉树中各结点中最大元素的值

1
2
3
4
5
6
7
8
9
int Get_Max(BiTree T)	
{
	if (T == NULL)
		return 0;
	int maxl = Get_Max(T->lchild);
	int maxr = Get_Max(T->rchild);
	int max = maxl > maxr ? maxl : maxr;	//max为maxl和maxr中更大的一个
	return max > T->data ? max : T->data;	//返回值为max和T->data中更大的一个
}

交换二叉树中每个结点的两个子女

1
2
3
4
5
6
7
8
9
10
11
12
void Exc(BiTree T)
{
	if (T->lchild != NULL)
		Exc(T->lchild);
	if (T->rchild != NULL)
		Exc(T->rchild);
	BiTNode *p;
	p = T->lchild;
	T->lchild = T->rchild;
	T->rchild = p;
}

以先序次序输出一颗二叉树中所有结点

1
2
3
4
5
6
7
8
9
void PreAndLevel(BiTree T, int i)	
{		//第一次调用为PreAndLevel(T, 1);
	if (T != NULL)
	{
		printf("data=%d，level=%d", T->data, i);
		PreAndLevel(T->lchild, i + 1);
		PreAndLevel(T->rchild, i + 1);
	}
}

参考

部分题解答源自 霸道总裁爱上网的博客_CSDN博客-c++,算法,安卓领域博主