二叉树 （王道数据结构 C语言版）

2004.11.04

• 计算一颗给定二叉树的所有双分支节点个数
• 编写把一个树的所有左右子树进行交换的函数
• 求先序遍历中第k个结点的值 (1 <= k <= 二叉树中的结点个数)

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;

typedef struct Bitnode{
	int data;
	struct Bitnode *lc,*rc;
}Bitnode,*Bitree;
//-------------------------------------------------------------------------

//王道数据结构  P158  T07  
//计算一颗给定二叉树的所有双分支节点个数

int getnum(Bitree T)
{
	if(T==NULL) return 0; //若b为空则贡献0
	else if(T->lc && T->rc) return getnum(T->lc)+getnum(T->rc)+1;//有左右节点，贡献给上一层+1
	else return getnum(T->rc)+getnum(T->lc);  //只有一个节点则归到上一层 数量不变
}

//----------------------------------------------------------------------------------

//王道数据结构 P158 T07
//编写把一个树的所有左右子树进行交换的函数

void swaptree(Bitree T)
{
	if(T==NULL) return;
	else if(T->lc && T->rc) {
		swaptree(T->lc); //递归进左子树
		swaptree(T->rc);//递归进右子树
		swap(T->lc,T->rc);
	}
}
//-------------------------------------------------------------------------

//王道数据结构 P158 T09
//求先序遍历中第k个结点的值 (1 <= k <= 二叉树中的结点个数)

//---------------------版本1（自写版）------------------
int  idx=1;
void getknode (Bitree T,int k)
{
	if(T==NULL ) return ;
	if(idx==k) {
		cout<<T->data;
		return ;
	}
	idx++;
	
	getknode(T->lc,k);
	getknode(T->rc,k);
	
}
//---------------------王道答案版--------------------
int i=1;
ElemType  prenode(Bitree T,int k)
{
	if(T==NULL) return '#' ; //空结点 返回特殊字符
	if(i==k) return T->data;
	i++;
	
	char ch=prenode(T->lc,int k);//进左子树查找
	if(ch!='#') return ch; //如果空结点返回的元素值没有意义 
	
	char ch=prenode(T->rc,int k);
	if(ch!='#') return ch;
	
}

2024.11.08

• 二叉树以二叉链表存储 求非空二叉树的宽度

#include<bits/stdc++.h>

#define endl '\n'
using namespace std;
#define Maxsize 150
typedef struct Bitnode {
	int data;
	struct Bitnode *lc,*rc;
} Bitnode,*Bitree;

//王道数据结构   P159  T13

//-----------二叉树以二叉链表存储 求非空二叉树的宽度------------

typedef struct {
	int front, rear;
	int level[Maxsize];//存层次的序号
	Bitree data[Maxsize];//存元素
} Queue;

int getwidth(Bitree T, Queue Q) {
	Bitree p;//工作指针
	int k;//用来更新层次下标
	Q.front = Q.rear = -1;

	Q.rear++;//元素入队
	Q.data[Q.rear] = T; //根节点入队
	Q.level[Q.rear] = 1;

	while (Q.front < Q.rear) {
		//取出队头
		Q.front++;
		p = Q.data[Q.front];
		k = Q.level[Q.front];

		if (p->lc) { //左孩子入队
			Q.rear++;
			Q.data[Q.rear] = p->lc;
			Q.level[Q.rear] = k + 1; //更改对应的层次
		}//注意 不可以写成else if

		if (p->rc) { //右孩子入队
			Q.rear++;
			Q.data[Q.rear] = p->rc;
			Q.level[Q.rear] = k + 1;;
		}
	}

	int Max=0;//统计最大宽度
	int i=0;//移动指针
	int tmp=0;//统计对应层次序号的数量
	k=1;
	
	//遍历统计最大值
	while(i<=Q.rear)
	{
		tmp=0;
		while(i<=Q.rear && Q.level[i]==k)
		{
			tmp++;
			i++;
		}
		k=Q.level[i];
		if(tmp>Max) Max=tmp;
	}
	return Max;
	
}
//--------------------------------------------------------------

• 将给定的表达式树 转换为等价的中缀表达式并输出

叶子结点肯定是操作数，非叶子结点就是运算符

#include<bits/stdc++.h>

#define endl '\n'
using namespace std;

//王道数据结构 P159 T18 
//将给定的表达式树 转换为等价的中缀表达式并输出


//注意表达式树的叶子结点 肯定是操作数
//根节点和叶子结点不加括号， 其余记得添加括号
typedef struct node{
	char data[10];
	struct  node *left ,*right;
}BTree;



void getin(BTree *T,int dep)
{
	if(T==NULL) return ;
	else if(!T->left && !T->right) //叶子结点 输出操作数
	{
		cout<<T->data;
	}else {
		if(dep>1)	cout<<"(";//若有子表达式 则加一层括号
		getin(T->left,dep+1);
		cout<<T->data; //输出操作符
		getin(T->right,dep+1);
		if(dep>1) cout<<")";//若有子表达式加一层括号
	}
}

void BtreeToe(BTree *T)
{
	getin(T,1);//从根节点进入
}


signed main() {

}