首页 > 编程语言 >树算法题

树算法题

时间：2023-11-16 19:34:08浏览次数：27  
标签：lchild 结点 遍历 BiTree 算法 二叉树 rchild

目录

1、计算二叉树中所有结点个数

2、计算二叉树中所有叶子节点的个数

3、计算二叉树中所有双分支的节点个数

4、计算二叉树的深度

5、找出二叉树中最大值的点

6、判断两个二叉树是否相似(指都为空或者都只有一一个根节点，或者左右子树都相似)

7、把二叉树所有节点左右子树交换

8、输出先序遍历第k个结点的值

9、求二叉树中值为x的层号

10、树中元素为x的结点，删除以它为根的子树

11、先序非递归遍历二叉树

12、中序非递归遍历二叉树

13、后序非递归遍历二叉树

14、计算二叉树的带权路径长度

15、找到p和q最近公共祖先结点r

16、层次遍历

17、判断二叉树是否为完全二叉树

1、计算二叉树中所有结点个数

int CntNode(BiTree T){
    int k=0;
    if(T){
        k++;
        k+=CntNode(T->lchild);
        k+=CntNode(T->rchild);
    }
    return k;
}

2、计算二叉树中所有叶子节点的个数

int LeafNode(BiTree T){
    int k=0;
    if(T){
        if(T->lchild==NULL&&T->rchild==NULL)
            k++;
        else{
            k+=LeafNode(T->lchild);		//统计左子树叶子结点
            k+=LeafNode(T->rchild);		//统计右子树叶子结点
        }
    }
    return k;
}

3、计算二叉树中所有双分支的节点个数

int DNodes(BiTree T){
    if(T==NULL)
        return 0;
    else if(T->lchild!=NULL&&T->rchild!=NULL)//双分支结点
        return DNodes(T->lchild)+DNodes(T->rchild)+1;
    else//单分支结点或叶子结点
        return DNodes(T->lchild)+DNodes(T->rchild);
}

4、计算二叉树的深度

int Deepth(BiTree T){
    int hl=0,hr=0;	//hl是左子树高度，hr是右子树高度
    if(T==NULL)
        return 0;
    else{	
        hl=Deepth(T->lchild);	//遍历左子树求高度
        hr=Deepth(T->rchild);	//遍历右子树求高度
        return hl>hr?hl+1:hr+1;	//返回子树高度较高的+根结点
    }
}

5、找出二叉树中最大值的点

//基于中序遍历的非递归算法
ElemType Inorder(BiTree T){
    ElemType max=-1;
    InitStack(S);
    p=T;
    while(p||!StakEmpty(S)){
        if(p){
            p=p->lchild;
            Push(S,p);	//入栈
        }
        else{
            Pop(S,p);	//出栈
            if(p->data>max)
                max=p->data;
            p=p->rchild;
        }
    }
    
    return max; 
}

6、判断两个二叉树是否相似(指都为空或者都只有一一个根节点，或者左右子树都相似)

bool IsSimilar(BiTree T1, BiTree T2){
    if(T1==NULL&&T1==NULL)	//都为空树
        return true;
    else if(T1==NULL||T1==NULL)	//只有一个棵树为空
        return false;
    else	//递归判断子树
        return IsSimilar(T1-lchild,T2->lchild) && IsSimilar(T1-rchild,T2->rchild);
}

7、把二叉树所有节点左右子树交换

/**
	先交换左子树中的结点
	再交换右子树中的结点
	最后交换左右子树，基于后序遍历
**/

void SwaptTree(BiTree T){
    BiTree temp;
    if(T){
        SwaptTree(T->lchild);	//递归交换左子树
        SwaptTree(T->rchild);	//递归交换右子树
        temp=T->lchild;
        T->lchild=T->rchild;
        T->rchild=temp;
    }
}

8、输出先序遍历第k个结点的值

int cnt=0;	//全局变量，统计结点个数
Status pre_k(BiTree T,int k){
    if(T){
        cnt++;
        if(cnt==k){
            print(T->data);	//输出第k个结点的值
            return OK;
        }
        else{
            if(pre_k(T->lchild,k))
                return OK;
            if(pre_k(T->rchild,k))
                return OK;
        }
    }
    return ERROR;
}

9、求二叉树中值为x的层号

int h=1;
void levelnum(BiTree T,ElemType x){
    if(T){
        if(x==T->data)
            cout<<h;	//打印层号
        ++h;
        levelnum(T->lchild,x);
        levelnum(T->rchild,x);
        --h;
    }
}

10、树中元素为x的结点，删除以它为根的子树

void Del_x(BTree T)//基于后序递归遍历删除结点
{
    if(T)
    {
        Del_x(T->lchild);
        Del_x(T->rchild);
        free(T);
    }
}

//基于层序遍历
void Search(BTree T,TElemType x){
    SqQueue Q;//定义顺序队列
    InitQueue(Q);//初始化队列
    BTree p;
    if(T){
        if(T->data==x){
            Del_x(T);
            exit(0);
        }
        EnQueue(Q,T);
        while(!QueueEmpty(Q)){
            DeQueue(Q,p);
            if(p->lchild){
                if(p->lchild->data==x){
                    Del_x(p->lchild);
                    p->lchild=NULL;//恢复树的结构
                }
                else
                    EnQueue(p->lchild);
            }
            if(p->rchild){
                if(p->rchild->data==x){
                    Del_x(p->rchild);
                    p->rchild=NULL;//恢复树的结构
                }
                else
                    EnQueue(p->rchild);
            }
        }
    }
}

11、先序非递归遍历二叉树

void PreOrder(BiTree T){
    InitStack(S);
    p=T;
    while(p||!StackEmpty(S)){
        if(p){
            Visit(p);
            p=p->lchild;
            Push(S,p);
        }
        else{
            Pop(S,p);
            p=p->rchild;
        }
    }
}

12、中序非递归遍历二叉树

void InOrder(BiTree T){
    InitStack(S);
    p=T;
    while(p||!StackEmpty(S)){
        if(p){
            p=p->lchild;
            Push(S,p);
        }
        else{
            Pop(S,p);
            Visit(p);
            p=p->rchild;
        }
    }
}

13、后序非递归遍历二叉树

void PostOrder(BiTree T){
	InitStack(S);	//初始化栈
    p=T;r=NULL;	//r指向上一个被访问的结点
    while(p||!StackEmpty(S){
       	if(p){
            Push(S,p);
            p=p->rchild;	//一直走到最左边
        }
        else{
            GetTOP(S,p);	//查看栈顶元素
            if(p->rchild&&p->rchild!=r)
                p=p->rchild;
            else{
                Pop(S,p);
                Visit(p);
                r=p;	//r记录被访问的结点
                p=NULL;	//清空p结点
            }
        }
    }
}

14、计算二叉树的带权路径长度

typedef struct BTNode{
    int weight;
    struct BTNode *lchild,*rchild;
}BTNode,*BiTree;

int WPL=0;	//全局变量求带权路径长度
int get_wpl(BiTree T, int deep){	//deep初始值为1
    if(T){
        get_wpl(T->lchild,deep+1);	//中序遍历左子树
        if(T->rchild==NULL&&T->lchild==NULL)
            WPL+=(deep-1)*T->weight;
        get_wpl(T->rchild,deep+1);	//中序遍历右子树
    }    
}

15、找到p和q最近公共祖先结点r

/*
以二链表存储的二叉树上找某结点的所有祖先，某两个结点的最近公共祖先，从根结点到某结点的路径，根结点到每个叶子结点以及最远叶子的路径等。均应采取后序非递归遍历。因为后序遍历最后访问根结点，当访问到某结点时，栈中所有元素均为该结点的祖先。
找p和q的最近共同祖先结点r，不失一般性，设p在q的左边。后序遍历必然先遍历到结点p，栈中元素均为p的祖先。将栈复制到另一辅助栈中再继续遍历到结点q时，将中元素从栈顶开始逐个到辅助中去匹配，第一个匹配(即相等)的元素就是结点p和g的最近公共祖先。
*/

typedef struct {
    BiTree t;
    int tag;	//tag=0表示左孩子已被访问，1表示右孩子已被访问
}Stack;

BiTree Ancestor(BiTree T,BiTNode *p,BiTNode *q){
    Stack s[],s1[];	//栈，容量足够大
    top=0,top1=0;	//栈顶指针,top1是s1的栈顶指针
    bt=T;
    while(bt!=NULL||top>0){
        while(bt!=NULL && bt!=p && bt!=q){
            s[++top].t=bt;
            s[top].tag=0;
            bt=bt->lchild;
        }
        if(bt==p){//假定p在q的左侧,遇结点p 时，栈中元素均为p的祖先结点
            for(i=1;i<=top;i++)//将p的祖先结点放到辅助栈s1中
                s1[i]=s[i];
            top1=top;	//修改栈顶指针
        }
        if(bt==q){//找到q结点
            for(i=top;i>0;i--){//将栈中元素到s1去匹配
                pp=s[i].t;
                for(j=top1;j>0;j--){
                    if(s1[j].t==pp){
                        cout<<"共同祖先已找到";
                        return pp;
                    }//if
                }//for
            }//for
        }//if
        while(top!=0&& s[top].tag==1) top--;	//退栈
		if(top!=0){s[top].tag=1;bt=s[top].t->rchild;}	//沿右分支向下遍历
    }
    return NULL;
}

16、层序遍历

void LevelTraverse(BiTree T)
{
	int i, j;
	BiTree p[100];					//树指针数组，用来模拟队列 
	
	i = j = 0;
	
	if(T)
		p[j++] = T;
		
	while(i<j)
	{
		printf("%c ", p[i]->data);
		if(p[i]->lchild)
			p[j++] = p[i]->lchild;
		if(p[i]->rchild)
			p[j++] = p[i]->rchild;
		i++;		
	}
}

void LevelTraverse(BiTree T)
{
	if(T){
        InitQueue(Q);	//初始化队列
 		EnQueue(Q,T);	//入队
        while(!QueueEmpty(Q)){
            DeQueue(Q,p);
            Visit(p);
            if(p->lchild)
                EnQueue(p->lchild);
            if(p->rchild)
                EnQueue(p->rchild);
        }
    }
}

17、判断二叉树是否为完全二叉树

Status Algo_6_49(BiTree T)
{
	int i, j;
	BiTree p[100] = {};					//树指针数组，模拟队列 
	int order[100] = {}; 
	
	i = j = 0;
	
	if(T)								//遍历的同时为各结点编号 
	{
		p[j] = T;	
		order[j] = 1;
		j++;
		
		while(i<j)
		{
			if(i>0 && order[i]>order[i-1]+1)
				return ERROR;			//若结点序号不连续，则非完全二叉树 
				
			if(p[i]->lchild)
			{
				p[j] = p[i]->lchild;
				order[j] = 2*order[i];	//左孩子编号2i
				j++;			
			}

			if(p[i]->rchild)
			{
				p[j] = p[i]->rchild;
				order[j] = 2*order[i]+1;	//右孩子编号2i+1
				j++;
			}
			
			i++;		
		}
	}
	
	return OK;
}

标签：lchild,结点,遍历,BiTree,算法,二叉树,rchild
From： https://www.cnblogs.com/qianxiaohan/p/17837096.html

相关文章

  • 【C++】【图像处理】形态学处理（腐蚀、膨胀）算法解析（以.raw格式的图像为基础进行图像处
    1voiderosion(BYTE*image,intw,inth,BYTE*outImg)2{3intrept;4//腐蚀5memcpy(outImg,image,sizeof(BYTE)*w*h);//将读取的图像赋值给outImg，方便进行腐蚀操作67inti,j,m,n;8BYTEflag;9for(rept=0;rept......
  • 随机产生n个数的排列(Fisher-Yates洗牌算法)
    #include<bits/stdc++.h>usingnamespacestd;constintN=1e5+10;inta[N];//Fisher-Yates洗牌算法voidshuffle(intn){srand(time(NULL));for(inti=n;i>1;i--){intj=rand()%i+1;swap(a[i],a[j]);}......
  • 使用 PPO 算法进行 RLHF 的 N 步实现细节
    当下，RLHF/ChatGPT已经变成了一个非常流行的话题。我们正在致力于更多有关RLHF的研究，这篇博客尝试复现OpenAI在2019年开源的原始RLHF代码库，其仓库位置位于openai/lm-human-preferences。尽管它具有“tensorflow-1.x”的特性，但OpenAI的原始代码库评估和基准测试非常完......
  • 由数据范围反推算法复杂度以及算法内容
    由数据范围反推算法复杂度以及算法内容一般ACM或者笔试题的时间限制是1秒或2秒。在这种情况下，\(\mathrm{C}++\)代码中的操作次数控制在\(10^{7}\sim10^{8}\)为最佳。下面给出在不同数据范围下，代码的时间复杂度和算法该如何选择:\(n\leq30\),指数级别,\(\mathrm{dfs......
  • 文心一言 VS 讯飞星火 VS chatgpt （136）-- 算法导论11.3 2题
    二、用go语言，假设将一个长度为r的字符串散列到m个槽中，并将其视为一个以128为基数的数，要求应用除法散列法。我们可以很容易地把数m表示为一个32位的机器字，但对长度为r的字符串，由于它被当做以128为基数的数来处理，就要占用若干个机器字。假设应用除法散列法来计算一个字符串......
  • 计算机图形：计算法向量
    目录一元向量值函数及其导数一元向量值函数概念一元值函数的导数空间曲线的切线和法平面曲面的切平面与法线示例：求椭球体表面法向量参考一元向量值函数及其导数一元向量值函数概念已知空间曲线Γ（大写的γ）参数方程：\[\tag{1}\begin{cases}x=\varphi(t),\\y=\psi(t),t\in[\al......
  • python机器学习算法原理实现——MCMC算法之gibbs采样
    【算法原理】Gibbs采样是一种用于估计多元分布的联合概率分布的方法。在MCNC（Markov Chain Monte Carlo）中，Gibbs采样是一种常用的方法。通俗理解Gibbs采样，可以想象你在一个多维空间中，你需要找到这个空间的某个特定区域（这个区域代表了你感兴趣的分布）。但是，你不能直接看到整个空间，只......
  • 机器学习算法原理实现——HMM生成序列和维特比算法
    【HMM基本概念】隐马尔可夫模型（Hidden Markov Model，HMM）是一种统计模型，用于描述一个含有未知参数（隐状态）的马尔可夫过程。在HMM中，我们不能直接观察到状态，但可以观察到每个状态产生的一些相关数据（观测值）。HMM的目标是，给定观测序列，估计出最可能的状态序列。HMM的基本假设有两个（见例子......
  • 机器学习算法原理实现——EM算法
    【EM算法简介】EM算法，全称为期望最大化算法（Expectation-Maximization Algorithm），是一种迭代优化算法，主要用于含有隐变量的概率模型参数的估计。EM算法的基本思想是：如果给定模型的参数，那么可以根据模型计算出隐变量的期望值；反过来，如果给定隐变量的值，那么可以通过最大化似然函数来估......
  • 机器学习算法原理实现——朴素贝叶斯
    【先说条件概率】条件概率是指在某个事件发生的条件下，另一个事件发生的概率。以下是一个实际的例子：假设你有一副扑克牌（不包括大小王，共52张牌），你随机抽一张牌。我们设事件A为"抽到的牌是红色的"（红心和方块为红色，共26张），事件B为"抽到的牌是心"（红心共13张）。1.首先，我们可以计算事件A和事......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99