【数据结构】树与二叉树遍历算法的应用(求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子)

目录

  • 求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子
    • 应用一:统计二叉树中叶子结点个数的算法
      • 写法一:使用静态变量
      • 写法二:传入 count 作为参数
      • 写法三:不使用额外变量
    • 应用二:二叉树存放表达式
    • 应用三:求二叉树的高
    • 应用四:复制二叉树
    • 应用五:二叉树的建立
    • 应用六:交换二叉树每个结点的左右孩子
      • Swap 函数(先序遍历):
      • Swap 函数(中序遍历)××× 不可行:
      • Swap 函数(后序遍历):
  • 求叶子节点个数、求树高、复制二叉树、创建二叉树完整代码示例

求叶子节点个数、求树高、复制二叉树、创建二叉树、二叉树存放表达式、交换二叉树每个结点的左右孩子

  1. 遍历二叉树的应用都是基于递归法实现的,递归的知识点以及例题可以参考文章: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题)
  2. 树与二叉树知识点可参考:【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)

注:本文二叉树的结构体定义为(采用二叉链表的定义):
在这里插入图片描述

//采用二叉链表的定义
typedef struct TreeNode{
	int data;//数据域
	TreeNode *rchild;//右孩子指针
	TreeNode *lchild;//左孩子指针
}TreeNode, *BiTree;
//注意结构体名称别写错!!!

应用一:统计二叉树中叶子结点个数的算法

写法一:使用静态变量

  • 函数使用了一个静态局部变量 count 来统计叶子节点的数量。
  • 每次调用函数时,count 的值都会保持,并且在遇到叶子节点时自增。
int LeafCount(BiTree T){
	static int count=0; // 静态局部变量,保持在函数调用之间的值
	if(T){
		if((T->lchild==NULL)&&(T->rchild==NULL)){
			count++; // 每当遇到叶子节点,count自增
		}
		else{
			LeafCount(T->lchild);
			LeafCount(T->rchild);
		}
	}
	return count; // 返回叶子节点数
}

写法二:传入 count 作为参数

  • 函数将 count 作为参数传递,并通过引用进行修改。
int LeafCount(BiTree T, int &count) {
    if (T) {
        if (T->lchild == NULL && T->rchild == NULL)
            count++;
        else {
            LeafCount(T->lchild, count);
            LeafCount(T->rchild, count);
        }
    }
    return count;
}

写法三:不使用额外变量

  • 函数直接通过递归计算叶子节点的数量,不使用额外的变量。
  • 当遇到空树,返回 0;当遇到叶子节点,返回 1;否则,递归计算左右子树的叶子节点数,并返回它们的和。
int LeafCount3(BiTree T){  
	if (!T) return 0;	// 空树叶子结点个数为0
  	if (!T->lchild && !T->rchild) return 1; // 找到一个叶节点
  	return LeafCount3(T->lchild) + LeafCount3(T->rchild);	// 否则为左右叶子结点个数之和
}

应用二:二叉树存放表达式

二叉树存放表达式 :

波兰式: +*dj/e+hi
中缀表示: d*j+e/(h+i)
逆波兰式: dj*ehi+/+

在这里插入图片描述

应用三:求二叉树的高

求二叉树深度算法(后序遍历)
m a x { 左子树深度 + 1 ,右子树深度 + 1 } max\{左子树深度+1,右子树深度+1\} max{左子树深度+1,右子树深度+1}

算法实现原理:

  1. 函数 Get_Height 接收一个指向树节点的指针 node 作为参数,表示要计算高度的二叉树的根节点。

  2. 首先,检查传入的节点是否为空。如果是空节点(即 node == NULL),那么树的高度为 0,因此函数直接返回 0。

  3. 如果节点不为空,则进入递归过程。它通过分别递归调用 Get_Height 函数来计算左子树和右子树的高度。

  4. 递归的终止条件就是当遇到叶子节点时,即左子节点和右子节点都为 NULL,这时高度为 0。

  5. 在每一层递归中,通过比较左子树的高度和右子树的高度,选择其中较大的一个,然后加上根节点,就得到了以当前节点为根的子树的高度。

  6. 最终,根据左右子树的高度计算出的最大高度加上根节点,就是整棵树的高度。

  7. 然后,返回return Tree_Height这个树的高度。

//求二叉树的高
int Get_Height(TreeNode* node) {
    if (node == NULL) return 0;//终止条件:如果为空节点,返回0,表示高度为0
    int Left_Height = Get_Height(node->lchild);//递归求左子树高度
    int Right_Hegiht = Get_Height(node->rchild);//递归求右子树高度
    int Tree_Height = 1 + (Left_Height > Right_Height?Left_Height:Right_Height);//计算树高
    return Tree_Height;
}

应用四:复制二叉树

复制二叉树采用后序遍历的方法来实现的,具体实现原理如下:

  1. 结点生成GetTreeNode函数):

    • GetTreeNode函数用于创建一个二叉树的结点。
    • 它接收三个参数:
      • item:表示结点的数据值。
      • lptr:表示左子树的指针。
      • rptr:表示右子树的指针。
    • 在函数内部,它首先分配一个新的结点(Q)的内存空间。
    • 然后,将传入的数据值、左子树指针和右子树指针分别赋值给新结点的对应字段。
    • 最后,返回新创建的结点。
  2. 后序遍历CopyTree函数):

    • CopyTree函数用于复制一个二叉树。
    • 如果需要复制的二叉树的结点为空,直接返回NULL
    • 否则,递归地复制左子树和右子树:
      • 如果左子树非空,调用CopyTree函数复制左子树。
      • 如果右子树非空,调用CopyTree函数复制右子树。
    • 创建一个新的结点,将原结点的数据值、复制的左子树和复制的右子树分别赋值给新结点的对应字段。
    • 返回复制后的新二叉树。

代码示例:

// 生成一个二叉树的结点
TreeNode* GetTreeNode(int item, TreeNode *lptr , TreeNode *rptr ){
	BiTree Q;
    if ( !(Q = (TreeNode*)malloc(sizeof(TreeNode))) ) {
    	exit(1);
    }
    Q-> data = item;
    Q-> lchild = lptr;    
    Q-> rchild = rptr;
    return Q;
}

//后序遍历 
TreeNode *CopyTree(TreeNode *T) {  
	//如果需要复制的二叉树的结点为空 就直接退出 
	BiTree newlptr=NULL;
	BiTree newrptr=NULL;
	BiTree newT=NULL;
	
    if (!T)    return NULL;
    if (T->lchild ) 
        newlptr = CopyTree(T->lchild);//复制左子树
    if (T->rchild ) 
		newrptr = CopyTree(T->rchild);//复制右子树
    
    newT = GetTreeNode(T->data, newlptr, newrptr);
    return newT;
} // CopyTree

注意:在给定的代码中,CopyTree 函数用于复制一个二叉树。它会递归地复制二叉树的每个节点,并且生成一个新的二叉树。在这个过程中,新的二叉树和原始二叉树的节点是独立的,它们的内存地址不同。这是因为 CopyTree 函数中调用 GetTreeNode 函数,该函数每次都会动态分配内存以创建新的节点。

所以,复制后的二叉树和原始二叉树之间的节点地址没有任何关系,它们是相互独立的。修改复制后的二叉树的节点不会影响原始二叉树。

应用五:二叉树的建立

以先序序列定义一棵二叉树:输入所要建立的二叉树的先序序列,建立二叉链表。
在输入的二叉树的先序序列中,加入空树明确表示"#"

在这里插入图片描述

按先序遍历序列建立二叉树的二叉链表
已知先序 序列为:ABC##DE##F###

二叉树的建立的算法:

typedef struct TreeNode{
	int data;//数据域
	TreeNode *rchild;//右孩子指针
	TreeNode *lchild;//左孩子指针
}TreeNode, *BiTree;

//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(BiTree &T) {
	char ch; 
    scanf("%c",&ch);
    if (ch=='#') T = NULL;
    else {
        T = (TreeNode *)malloc(sizeof(TreeNode)); 
        T->data = ch;      // 生成根结点
        CreateBiTree(T->lchild); // 构造左子树
        CreateBiTree(T->rchild); // 构造右子树
    }
}

应用六:交换二叉树每个结点的左右孩子

以上代码实现了交换二叉树每个节点的左右孩子的功能,分别使用了先序、中序和后序遍历的方式。

遍历二叉树算法的变式:

  1. Swap 函数(先序遍历):

    • 从根节点开始,先交换当前节点的左右孩子。
    • 然后递归地对左子树和右子树执行相同的操作。
  2. Swap2 函数(中序遍历):

    • 与先序遍历不同,中序遍历中需要先对左子树进行操作,然后交换当前节点的左右孩子,最后对右子树进行操作。
    • 但是这个实现方式是错误的,因为在交换左子树之后,对右子树进行操作时,右子树的结构已经发生了变化,导致结果错误。
  3. Swap3 函数(后序遍历):

    • 与先序遍历类似,但是是在遍历完左右子树之后再交换当前节点的左右孩子。
    • 这样可以保证在交换左右孩子时,左右子树的结构不会被改变。

通过上述分析,正确的交换方式是采用先序或后序遍历,中序遍历方式不适合这个场景。

Swap 函数(先序遍历):

//前序
void Swap(BiTree& T){
	//(先序遍历) 
	if(T){
	//根节点 
		if(T->lchild||T->rchild){
			BiTree p;
			p= T->lchild;
			T->lchild = T->rchild;
			T->rchild = p;
		}
		Swap(T->lchild);
		Swap(T->rchild);
	}
}

Swap 函数(中序遍历)××× 不可行:

//中序的不行 
void Swap2(BiTree& T){
	//(中序遍历) 
	
	if(T){
	//根节点 
		Swap2(T->lchild);
		if(T->lchild||T->rchild){
			BiTree p;
			p= T->lchild;
			T->lchild = T->rchild;
			T->rchild = p;
		}
		Swap2(T->rchild);
		
	}
}

Swap 函数(后序遍历):

//后序
void Swap3(BiTree& T){
	//(后序遍历) 
	
	if(T){
	//根节点 
		Swap3(T->lchild);
		Swap3(T->rchild);
		if(T->lchild||T->rchild){
			BiTree p;
			p= T->lchild;
			T->lchild = T->rchild;
			T->rchild = p;
		}
	}
	
	
}

求叶子节点个数、求树高、复制二叉树、创建二叉树完整代码示例

输入示例:ABC##DE##F###

#include<iostream>
using namespace std;


typedef struct TreeNode{
	int data;//数据域
	TreeNode *rchild;//右孩子指针
	TreeNode *lchild;//左孩子指针
}TreeNode, *BiTree;


//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(BiTree &T) {
	char ch; 
    scanf("%c",&ch);
    if (ch=='#') T = NULL;
    else {
        T = (TreeNode*)malloc(sizeof(TreeNode));
        T->data = ch;      // 生成根结点
        CreateBiTree(T->lchild); // 构造左子树
        CreateBiTree(T->rchild); // 构造右子树
    }
}

//求叶子结点 
int LeafCount(BiTree T){
	static int count=0;//或者定义成全局变量 
	/*这里使用局部静态变量*/
	if(T){
		
		if((T->lchild==NULL)&&(T->rchild==NULL)){
			//判断T是否为叶子结点
			count++;
			//每次递归调用
			//当T为叶子时,count自加
		}
		else{
			//递归:求T左、右子树上的叶子结点数

			LeafCount(T->lchild);
			LeafCount(T->rchild);
		}
		
	}
	return count;
}

//求叶子节点的写法三 
int LeafCount3(BiTree T){  
	if (!T) return 0;	
      //空树叶子结点个数为0
  	if (!T->lchild && !T->rchild) return 1; 
      //若根节点没有左右孩子叶子结点个数为1
  	return LeafCount3(T->lchild) + LeafCount3(T->rchild);	
      //否则为左右叶子结点个数之和
}



//求树高 
int Get_Height(BiTree node){//递归 求树高 
	if(node==NULL) return 0;
	else{
		int Left_Height = Get_Height(node->lchild);
		int Right_Height = Get_Height(node->rchild);
		int Tree_Height = 1 + (Left_Height > Right_Height?Left_Height:Right_Height);//计算树高
    	return Tree_Height;
	}
	
}
//先序遍历 
void xxbl(BiTree T){
    if(T){//递归调用的结束条件
        printf("%c",T->data);//访问结点
        xxbl(T->lchild);//遍历左子树
        xxbl(T->rchild);//遍历右子树
    }
    
}
//中序遍历 
void zxbl(BiTree T){
    if (T) {
        zxbl(T->lchild); 
        printf("%c",T->data); 
        zxbl(T->rchild);
    }
}
//后序遍历 
void hxbl(BiTree T){
    if(T){
        hxbl(T->lchild); 
        hxbl(T->rchild); 
        printf("%c",T->data);
    }
}

// 
// 生成一个二叉树的结点
TreeNode* GetTreeNode(int item, TreeNode *lptr , TreeNode *rptr ){
	BiTree Q;
    if ( !(Q = (TreeNode*)malloc(sizeof(TreeNode))) ) {
    	exit(1);
    }
    Q-> data = item;
    Q-> lchild = lptr;    
    Q-> rchild = rptr;
    return Q;
}

//后序遍历 
TreeNode *CopyTree(TreeNode *T) {  
	//如果需要复制的二叉树的结点为空 就直接退出 
	BiTree newlptr=NULL;
	BiTree newrptr=NULL;
	BiTree newT=NULL;
	
    if (!T)    return NULL;
    if (T->lchild ) { 
        newlptr = CopyTree(T->lchild);//复制左子树
	} 
	if (T->rchild ){ 
		newrptr = CopyTree(T->rchild);//复制右子树
    } 
    newT = GetTreeNode(T->data, newlptr, newrptr);
    return newT;
} // CopyTree


int main(){
	 
	BiTree T;
	//例如输入:ABC##DE##F### 来创建二叉树 
	CreateBiTree(T);
	cout<<"先序:"; 
	xxbl(T);
	cout<<endl;
	cout<<"中序:"; 
	zxbl(T);
	cout<<endl;
	cout<<"后序:"; 
	hxbl(T);
	cout<<endl;
	cout<<"树高为:" ;
	cout<<Get_Height(T)<<endl;
	cout<<"叶子节点的个数为:";
	cout<<LeafCount3(T)<<endl; 
	
	
	
	//复制二叉树
	BiTree Q;
	Q=CopyTree(T); 
	cout<<"复制后的二叉树 以先序输出:"; 
	xxbl(Q);
	cout<<endl;
	//修改一下Q 左子树根节点的数据 观察原本T 是否改变 
	Q->lchild->data='Z';
	cout<<"修改的二叉树 Q以先序输出:"; 
	xxbl(Q);
	cout<<endl;
	
	cout<<"T先序:"; 
	xxbl(T);
	cout<<endl;
	return 0; 
} 

感谢您的阅读!

  1. 遍历二叉树的应用都是基于递归法实现的,递归的知识点以及例题可以参考文章: 【数据结构与算法】递推法和递归法解题(递归递推算法典型例题)
  2. 树与二叉树知识点可参考:【数据结构】树与二叉树(递归法先序、中序、后序、层次遍历二叉树、二叉树的建立以及求树高的方法)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/531641.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【Linux】socket编程2

欢迎来到Cefler的博客&#x1f601; &#x1f54c;博客主页&#xff1a;折纸花满衣 &#x1f3e0;个人专栏&#xff1a;题目解析 目录 &#x1f449;&#x1f3fb;客户端代码Makefile(生成目标文件)UdpClient.cc(客户端代码)服务端代码部分优化1&#xff08;接受客户端时显示客…

基于51单片机低中高音7键电子琴音乐播放器

基于51单片机电子琴音乐播放器 &#xff08;仿真&#xff0b;程序&#xff0b;原理图&#xff0b;PCB&#xff0b;设计报告&#xff09; 功能介绍 具体功能&#xff1a; 1.可以使用按键切换音乐播放模式和弹奏模式&#xff1b; 2.LED灯显示在使用哪种模式&#xff1b; 3.音乐…

Redis部署之主从

使用两台云服务器&#xff0c;在 Docker 下部署。 Redis版本为&#xff1a;7.2.4 下载并配置redis 配置文件 下载 wget -c http://download.redis.io/redis-stable/redis.conf配置 master节点配置 bind 0.0.0.0 # 使得Redis服务器可以跨网络访问,生产环境请考虑…

第十四届蓝桥杯C/C++大学B组题解(二)

6、岛屿个数 #include <bits/stdc.h> using namespace std; const int M51; int T,m,n; int vis[M][M],used[M][M]; int dx[]{1,-1,0,0,1,1,-1,-1}; int dy[]{0,0,1,-1,1,-1,1,-1}; string mp[M]; struct node{//记录一点坐标 int x,y; }; void bfs_col(int x,int y){ qu…

C++ | Leetcode C++题解之第14题最长公共前缀

题目&#xff1a; 题解&#xff1a; class Solution { public:string longestCommonPrefix(vector<string>& strs) {if (!strs.size()) {return "";}int minLength min_element(strs.begin(), strs.end(), [](const string& s, const string& t)…

同步压缩理论

参考 在频率方向进行能量重新分配&#xff08;分配到中心&#xff09; 时频重排

实验4 DHCP基础配置

实验4 DHCP基础配置 一、 原理描述二、 实验目的三、 实验内容四、 实验配置五、 实验步骤1.基本配置2.配置DHCPServer功能3.配置DHCP Client 一、 原理描述 动态主机配置协议 DHCP是一个局域网的网络协议&#xff0c;使用UDP协议工作&#xff0c;主要有两个用途&#xff1a;用…

大话设计模式——16.命令模式(Command Pattern)

简介 请求以命令的形式包裹在对象中&#xff0c;并传给调用对象。调用对象寻找可以处理该命令的对象进行执行。命令模式是一种特殊的策略模式&#xff0c;体现多个策略执行的问题&#xff0c;而不是选择的问题 UML图 应用场景 界面选择、键盘、按钮、事件操作都类似命令模式 …

前端工程化理解 (2024 面试题)

最好介绍远古世界最好随性一点&#xff0c;不要太刻板 &#xff0c;不然像背书 什么是前端工程化&#xff1f; - 知乎 前端工程化的历史 互联网初期&#xff0c;09 年以前&#xff0c;页面只需要展示一些列表、表格、文章内容以及简单图片即可&#xff0c;其目的是为了传送信…

身份证正面打印、反面打印与打印在同一页

1 打印身份证正面 将身份证正面朝下放置&#xff0c;按打印机键盘上的数字【3】&#xff0c;再按【Start】键&#xff0c;选择A4大小打印&#xff0c;如图(1)所示&#xff1a; 图(1) A4纸复印 2 打印身份证反面 将身份证反面朝下放置&#xff0c;按打印机键盘上的数字【3】&…

KVM 高级功能部署

目录 一、案例分析 1.1、案例概述 1.2、案例前置知识点 1&#xff09;KVM 虚拟机迁移 2&#xff09;KSM 内核同页合并 1.3、案例环境 1&#xff09;本案例环境 2&#xff09;案例需求 3&#xff09;案例实现思路 二、案例实施 2.1、静态迁移 1&#xff09;在…

springboot+vue药店药品进销存采购管理系统0z10z

本系统采用intellij idea支持eclipse 项目架构&#xff1a;B/S架构web 开发语言&#xff1a;java 前端技术&#xff1a;vue.jsElementUi 后端框架&#xff1a;django、mybatis、Springmvc 运行环境&#xff1a;win10/win11、jdk1.8 可行性论证 社会可行性 开发本系统&#xff…

XC6206稳压芯片

mark 662k XC6206 的基本特性。这是一个 SOT23封装的 3.3V 稳压器。它输出最大工作电流为 100mA 最大特点便宜 参考链接 XC6206稳压芯片 (qq.com)https://mp.weixin.qq.com/s?__bizMzA5NjQyNjc2NQ&mid2452268489&idx1&sn90e920c596e3c2a382f81929c6313977&c…

Linux--进程的概念(一)

目录 一、冯诺依曼体系结构二、操作系统2.1 什么是操作系统2.2 操作系统的意义 三、进程3.1 进程的基本概念3.2 描述进程——PCB3.3 进程和程序的区别3.4 task_struct-PCB的一种3.5 task_struct的内容分类 四、如何查看进程4.1 通过系统文件查看进程4.2 通过ps指令查看进程 五、…

《公安机关互联网安全监督检查规定》系列之“解决方案”

随着中国互联网和信息网络飞速发展&#xff0c;无线网络普及到国内各个家庭和公共场所&#xff0c;成为人们日常办公和生活娱乐不可或缺的一部分。无线网络在创造商业价值、带来工作和生活便捷的同时&#xff0c;也同样让犯罪份子有了可乘之机&#xff0c;越来越多的网络违法活…

如何通过数据验证防止 Web API 攻击 - Web API 安全指南

充分的数据保护和用户保密是网页开发者的主要责任。因此&#xff0c;在构建 API 终端时&#xff0c;确保最高可能的安全性至关重要。 应用程序安全是客户端和服务器开发者共同的责任&#xff0c;一方的疏忽可能会造成灾难性后果。统计数据显示&#xff0c;2023 年的数据泄露导…

windows安装Redis,Mongo,ES并快速基本掌握开发流程

前言 这里只是一些安装后的基础操作&#xff0c;后期会学习更加深入的操作 基础操作 前言RedisRedis启动idea集成Redisjedis技术 Mongodbwindows版Mongodb的安装idea整合Mongodb ES(Elasticsearch)ESwindows下载ES文档操作idea整合ES低级别ES整合高级别ES整合 Redis Redis是…

HarmonyOS 开发-Grid和List内拖拽交换子组件位置

介绍 本示例分别通过onItemDrop()和onDrop()回调&#xff0c;实现子组件在Grid和List中的子组件位置交换。 效果图预览 使用说明&#xff1a; 拖拽Grid中子组件&#xff0c;到目标Grid子组件位置&#xff0c;进行两者位置互换。拖拽List中子组件&#xff0c;到目标List子组件…

【进阶六】Python实现SDVRPTW常见求解算法——自适应大邻域算法(ALNS)

基于python语言&#xff0c;采用经典自适应大邻域算法&#xff08;ALNS&#xff09;对 带硬时间窗的需求拆分车辆路径规划问题&#xff08;SDVRPTW&#xff09; 进行求解。 目录 往期优质资源1. 适用场景2. 代码调整2.1 需求拆分2.2 需求拆分后的服务时长取值问题 3. 求解结果4…

CADMap3D2024 2023下载地址及安装教程

CAD Map 3D是由Autodesk开发的一款专业的地图制作和GIS&#xff08;地理信息系统&#xff09;软件。它是AutoCAD系列软件的一个扩展&#xff0c;提供了一系列特定于地理数据的工具和功能。 CAD Map 3D主要用于处理和管理与地理空间相关的数据&#xff0c;在地图制作、城市规划…