【王道数据结构编程题】- 二叉树编程练习

目录

1.写出在中序线索二叉树中查找指定节点在后序的前驱节点的算法。

2.二叉树的带权路径长度(WPL)是二叉树中所有叶节点的带权路径长度之和，给定一颗二叉树T，采用二叉链表存储，节点结构为

left weight right

其中叶节点的weight域保存该节点的非负权值，设root为指向T的根节点的指针。设计求T的WPL的算法。

3.设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式。

4.编写程序求以孩子兄弟表示法存储的森林的叶子节点数 

5. 以孩子兄弟链表为存储结构 设计递归算法求树的深度

6.已知一棵树的层次序列以及每个节点的度 编写算法构造此树的孩子-兄弟链表

---

1.写出在中序线索二叉树中查找指定节点在后序的前驱节点的算法。

//在中序线索二叉树中查找指定节点在后序的前驱节点的算法
#include<iostream>
using namespace std;
//线索二叉树节点的结构体
typedef struct treenode{
    //节点的值
	char data;
	//节点的左右孩子指针
	struct treenode *lchild,*rchild;
	//ltag rtag
	int ltag,rtag;
}treenode,*tree;
 
//建树 赋值节点
void buildtree(tree &t)
{
	char ch;
	cin>>ch;
	if(ch=='#') t=NULL;
	else
	{
		//对节点进行内存分配
		t=(treenode *)malloc(sizeof(treenode));
		//对节点进行赋值
		t->data=ch;
		//初始化 左右孩子节点为空
		t->lchild=NULL;
		t->rchild=NULL;
		t->ltag=t->rtag=0;
		//递归去赋值左右子树
		buildtree(t->lchild);
		buildtree(t->rchild);
	}
}
 
tree pre;
 
//遍历二叉树的保留的前驱节点
//中序线索化
void zx(tree &t)
{
	//递归的条件
	if(t)
	{
		//向左延申 找叶子节点
		zx(t->lchild);
		if(t->lchild==NULL)//左孩子为空
		{
			t->ltag=1;
			t->lchild=pre;
		}
		else t->ltag=0;
		if(pre!=NULL&&pre->rchild==NULL)//没有右孩子
		{
			pre->rtag=1;//前驱节点有后继节点
			pre->rchild=t;//后继节点指向当前
		}
		pre=t;//更新前驱节点
		zx(t->rchild);
	}
}
 
//找后继的前驱节点
tree Inpostpre(tree t,treenode *p)
{
	//结果指针
	treenode *q;
	//该节点有右孩子 结果就是右孩子
	if(p->rtag==0) q=p->rchild;
	//该节点没有右孩子的情况下 有左孩子 结果就是左孩子
	else if(p->ltag==NULL) q=NULL;
	//其他
	else
	{
		//不断沿着线索找到祖先节点
		while(p->ltag==1&&p->lchild!=NULL)
			p=p->lchild;
		if(p->ltag==0) q=p->lchild;
		//若找到祖先节点 且有左孩子 结果就是左孩子
		else q=NULL;
		//最后就是没有后序前驱
	}
	return q;
}
 
//主函数 测试
int main()
{
	tree t;
	buildtree(t);
    zx(t);
	cout<<Inpostpre(t,t->rchild)->data<<endl;
	return 0;
}
 
/*
            A
	      B   C
		D  E  F  G
*/
//ABD##E##CF##G##

2.二叉树的带权路径长度(WPL)是二叉树中所有叶节点的带权路径长度之和，给定一颗二叉树T，采用二叉链表存储，节点结构为

left weight right

其中叶节点的weight域保存该节点的非负权值，设root为指向T的根节点的指针。设计求T的WPL的算法。

//带权路径长度之和
#include<iostream>
using namespace std;
//结构体
typedef struct treenode{
    //节点的值
	char weight;
	//节点的左右孩子指针
	struct treenode *lchild,*rchild;
}treenode,*tree;
 
//建树 
void buildtree(tree &t)
{
	char ch;
	cin>>ch;
	if(ch=='#') t=NULL;
	else
	{
		//对节点进行内存分配
		t=(treenode *)malloc(sizeof(treenode));
		//对节点进行赋值
		t->weight=ch;
		//初始化 左右孩子节点为空
		t->lchild=NULL;
		t->rchild=NULL;
		//递归去赋值左右子树
		buildtree(t->lchild);
		buildtree(t->rchild);
	}
}
 
//计算wpl
int wplpre(tree t,int deep)
{
	//静态变量 存储结果值并函数末尾返回
	static int ans =0;
	//若是叶子节点 累加值
	if(t->lchild==NULL&&t->rchild==NULL)
		ans+=(deep*((t->weight)-'0'));
	if(t->lchild!=NULL)
		wplpre(t->lchild,deep+1);
	//若不是叶子节点 递归遍历左子树找到叶子节点同时层数+1
	if(t->rchild!=NULL)
		wplpre(t->rchild,deep+1);
	//若不是叶子节点 递归遍历左子树找到叶子节点同时层数+1
	return ans;
}
 
//主函数 测试
int main()
{
	tree t;
	buildtree(t);
	cout<<wplpre(t,0)<<endl;
	return 0;
}
 
/*
            1
		2       3
	 4    5   6   7
	 124##5##36##7##
	 ans = (4+5+6+7)*2=44
*/

3.设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式。

//表达式树转换为中缀表达式
#include<iostream>
using namespace std;
//结构体
typedef struct treenode{
    //节点的值
	char data;
	//节点的左右孩子指针
	struct treenode *lchild,*rchild;
}treenode,*tree;
 
//建树 
void buildtree(tree &t)
{
	char ch;
	cin>>ch;
	if(ch=='#') t=NULL;
	else
	{
		//对节点进行内存分配
		t=(treenode *)malloc(sizeof(treenode));
		//对节点进行赋值
		t->data=ch;
		//初始化 左右孩子节点为空
		t->lchild=NULL;
		t->rchild=NULL;
		//递归去赋值左右子树
		buildtree(t->lchild);
		buildtree(t->rchild);
	}
}
 
//转换函数
void toexp(tree t,int deep)
{
	if(t==NULL) return;
	else if(t->lchild==NULL&&t->rchild==NULL)
	{
		cout<<t->data;
	}
	else
	{
		if(deep>1) cout<<"(";
		toexp(t->lchild,deep+1);
		cout<<t->data;
		toexp(t->rchild,deep+1);
		if(deep>1) cout<<")";
	}
}
 
//主函数 测试
int main()
{
	tree t;
	buildtree(t);
	toexp(t,1);
	return 0;
}
 
/*
       *
	+     *
  a   b  c  -
  *+a##b##*c##-#d##
       +
	*     -
  a   b      -
           c   d
  +*a##b##-#-c##d##
      +
	a   b
	+a##b##
*/

 

4.编写程序求以孩子兄弟表示法存储的森林的叶子节点数 

//求以孩子兄弟表示法存储的森林的叶子节点数
#include<iostream>
using namespace std;
//结构体
typedef struct treenode{
    //节点的值
	char data;
	//左孩子域 右兄弟域 指向
	struct treenode *child,*rbro;
}treenode,*tree;
 
//建树 
void buildtree(tree &t)
{
	char ch;
	cin>>ch;
	if(ch=='#') t=NULL;
	else
	{
		//对节点进行内存分配
		t=(treenode *)malloc(sizeof(treenode));
		//对节点进行赋值
		t->data=ch;
		//初始化 左右孩子节点为空
		t->child=NULL;
		t->rbro=NULL;
		//递归去赋值左右子树
		buildtree(t->child);
		buildtree(t->rbro);
	}
}
 
//递归找叶子节点
int leaves(tree t)
{
	//空节点 返回0
	if(t==NULL) return 0;
	//孩子为空 即左孩子域为空 为叶子节点 结果+1还要加上右兄弟子树的叶子节点
	if(t->child==NULL) return 1+leaves(t->rbro);
	//有孩子 结果为左孩子子树和右兄弟子树的叶子节点个数之和
	else return leaves(t->child)+leaves(t->rbro);
}
 
//主函数 测试
int main()
{
	tree t;
	buildtree(t);
	cout<<leaves(t)<<endl;
	return 0;
}
 
/*
       A
	B    F
  D   C G
   E
   ABD#E##C##FG###
*/

 

5. 以孩子兄弟链表为存储结构 设计递归算法求树的深度

//以孩子兄弟链表为存储结构 设计递归算法求树的深度
#include<iostream>
using namespace std;
//结构体
typedef struct treenode{
    //节点的值
	char data;
	//左孩子域 右兄弟域 指向
	struct treenode *child,*rbro;
}treenode,*tree;
 
//建树 
void buildtree(tree &t)
{
	char ch;
	cin>>ch;
	if(ch=='#') t=NULL;
	else
	{
		//对节点进行内存分配
		t=(treenode *)malloc(sizeof(treenode));
		//对节点进行赋值
		t->data=ch;
		//初始化 左右孩子节点为空
		t->child=NULL;
		t->rbro=NULL;
		//递归去赋值左右子树
		buildtree(t->child);
		buildtree(t->rbro);
	}
}
 
int max(int a,int b)
{
	if (a<b) return b;
	else return a;
}
	
//递归计算深度
int height(tree t)
{
	if(t==NULL) return 0;
	else
	{
		//递归计算左孩子子树高度
		int l=height(t->child);
		//递归计算右兄弟子树高度
		int r=height(t->rbro);
		return max(l+1,r);
	}
}
 
//主函数 测试
int main()
{
	tree t;
	buildtree(t);
	cout<<height(t)<<endl;
	return 0;
}
 
/*
       A
	B    
  D   C 
   E F
   ABD#E##CF####
*/

6.已知一棵树的层次序列以及每个节点的度 编写算法构造此树的孩子-兄弟链表

//已知一棵树的层次序列以及每个节点的度 编写算法构造此树的孩子-兄弟链表
#include<iostream>
using namespace std;
//结构体
typedef struct treenode{
    //节点的值
	char data;
	//左孩子域 右兄弟域 指向
	struct treenode *child,*rbro;
}treenode,*tree;
 
//构建链表
void creat(tree &t,char e[],int degree[],int n)
{
	//动态申请节点数组
	tree *point=new tree[10];
	int i;
	for(i=0;i<n;i++)
	{
	    //给每个节点动态申请内存
		point[i]=(treenode *)malloc(sizeof(treenode));
	    //给每个节点初始化 初始值为给的字母和对应的左右指针初始化为空
		point[i]->data=e[i];
		point[i]->child=point[i]->rbro=NULL;
	}
 
	//孩子节点序号
	int k=0;
	//按照给的节点顺序访问节点
	for(i=0;i<n;i++)
	{
    //获取该节点的度
		int d=degree[i];
	//如果有度，说明有孩子节点
		if(d)
        {
			//孩子序号递增
			k++;
	        //将第一个孩子作为自己的左孩子节点
			point[i]->child=point[k];
	        //剩余的孩子 每个节点依次为前一个节点的兄弟节点
			for(int j=2;j<=d;j++)
			{
					//孩子序号递增
				    k++;
	                //前一个节点的右兄弟指针指向现在孩子序号的节点
					point[k-1]->rbro=point[k];
			}
		}
	}
	t=point[0];
 
	//链表的头为第一个节点
	delete [] point;
	//动态申请的内存要进行一个释放 防止内存泄露
}
 
//输出最后孩子兄弟表示的树的先序序列进行验证
void disp(tree t)
{
	if(t)
	{
		cout<<t->data<<" ";
		disp(t->child);
		disp(t->rbro);
	}
}
 
//主函数 测试
int main()
{
	tree t;
	//层次遍历序列
	char e[8]="ABCDEFG";
	//每个节点度数数组
	int degree[8]={3,2,1,0,0,0,0};
	//构造这样的函数
	creat(t,e,degree,7);
	//输出这样的二叉树验证
	disp(t);
	return 0;
}
 
/*
       A
	B  C  D
  E  F G
       A
	 B
  E    C
   F  G D
ABCDEFG
3,2,1,0,0,0,0
先序：A B E F C G D
*/