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

说在前面

本文是王道数据结构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++,算法,安卓领域博主