关于二叉树（创建、遍历、画图）（个人学习使用，非专业）

2023-11-09 00:40
文章标签 二叉树 遍历 学习 使用 创建 个人 画图 非专业

本文主要是介绍关于二叉树（创建、遍历、画图）（个人学习使用，非专业），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目要求

主要内容：

设计一个与二叉树基本操作相关的程序。

程序基本要求如下：

①以树状形式输出；

②以先序、中序、后序三种方式输出；

③统计输出二叉树的结点总数、叶子总数、树高。

目录

题目要求

一、源代码

二、分析

三、基础函数：

1、构造二叉树

2、三个遍历

3、计算结点总数、叶子结点树、树高

基础函数的运行举例

 4、画图部分（有需要的小伙伴可以画图分析就很好理解了）

这里有误解！！！

修改之后 

再次修改：此次修改是为了不让两个元素贴在一起，但是外观还是有瑕疵

一、源代码

#include <bits/stdc++.h>
using namespace std;
#define Max 200typedef struct Node{char date;  //结点数据域struct Node *lchild,*rchild;    //左右孩子指针int x,y;    //横纵坐标
}Node,*tree;char t[Max][Max];//我们规定画布大小为：Max * Max
int minX=Max,maxX=0;//函数声明
void index();
void creatTree(tree &T ,int x,int y);
void paintTree(tree T);
void DLR(tree &T);
void LDR(tree T);
void LRD(tree T);
int countNode(tree T);
int countLeaf(tree T);
int treeHigh(tree T);int main() {index();tree T;while (1){cout << "请选择要执行的操作： ";int choose;cin >> choose;switch (choose) {case 0://创建case 1: {//调试用例：ab#df##g##cx##e##cout << "请按先序输入，以#为结束： ";creatTree(T, 0, 0);break;}//画树case 2 : {int h=treeHigh(T);cout << "画树如下：" <<endl;memset(t,' ',sizeof(t));paintTree(T);for(int i=0;i<2*h;i++){for(int j=minX;j<=maxX;j++){cout << t[j][i];}cout << endl;}break;}//三序遍历case 3:{cout << "先序遍历的结果为： ";DLR(T);cout << endl;cout << "中序遍历的结果为： ";LDR(T);cout << endl;cout << "后序遍历的结果为： ";LRD(T);cout << endl;break;}//树的属性case 4:{cout << "结点总数： "<< countNode(T) << endl;cout << "叶子总数： "<< countLeaf(T) << endl;cout << "树的高度： "<< treeHigh(T) << endl;break;}default :cout << "请选择合法的操作" <<endl;}}
}//菜单
void index()
{cout << "********** 功能如下 **********" << endl;cout << "\t" << "0 ----> 退出程序" << endl;cout << "\t" << "1 ----> 先序建立一个树" << endl;cout << "\t" << "2 ----> 画二叉树" << endl;cout << "\t" << "3 ----> 三序遍历" << endl;cout << "\t" << "4 ----> 树的属性" << endl;
}//画图
void paintTree(tree T)
{if(T){// Max/2的使用目的是：由于原坐标是关于y轴对称的，因此我们要将整个图像沿x轴平移if(' '== t[T->x + Max/2][2 * T->y]) t[T->x + Max/2][2 * T->y]=T->date;//修改之后else t[T->x + Max/2+1][2 * T->y]=T->date;    //若有字符，后移//修改之前：// else t[T->x + Max/2][2 * T->y]='!'; //重复就显示'！'if(T->lchild){t[T->x + Max/2 -1][2 * T->y +1]='/';paintTree(T->lchild);}if(T->rchild){t[T->x + Max/2 +1][2 * T->y +1]='\\';paintTree(T->rchild);}}
}//先序建立二叉树，并且给出坐标
void creatTree(tree &T ,int x,int y)
{char c;cin >> c;if(c == '#') T=NULL;else{   //传值T=new Node;T->date=c;	T->x=x;T->y=y;creatTree(T->lchild,x-2,y+1); //左子树坐标，次数横坐标偏移量为2是为了方便在中间插入'/'creatTree(T->rchild,x+2,y+1); //右子树坐标//更新最小最大横坐标maxX=max(maxX,x+Max/2+1);	minX=min(minX,x+Max/2-1);}
}
//先序遍历
void DLR(tree  &T)
{if(T){cout << T->date << " ";DLR(T->lchild);DLR(T->rchild);}
}
//中序遍历
void LDR(tree T)
{if(T){LDR(T->lchild);cout << T->date << " ";LDR(T->rchild);}
}
//后序遍历
void LRD(tree T)
{if(T){LRD(T->lchild);LRD(T->rchild);cout << T->date << " ";}
}
//结点总数
int countNode(tree T)
{int l,r;//左右子树的结点数if(!T) return  0;if(!T->rchild && T->rchild) return 1;else{l= countNode(T->lchild);r= countNode(T->rchild);return l+r+1;}
}
//叶子总数
int countLeaf(tree T)
{int leaf;if(!T) return  0;if(!T->rchild && !T->rchild) return 1;else leaf= countLeaf(T->lchild)+ countLeaf(T->rchild);return  leaf;
}
//树高
int treeHigh(tree T)
{int lh,rh;if(!T) return 0;else{lh= treeHigh(T->lchild);rh= treeHigh(T->rchild);return lh>rh ? lh+1 : rh+1;}
}

二、分析

由于我们题目要求画图，这里我打算使用坐标，故而我们将结构体定义如下：

typedef struct Node{char date;  //结点数据域struct Node *lchild,*rchild;    //左右孩子指针int x,y;    //横纵坐标
}Node,*tree;

这里我选择用一个二维数组作为画布：

char t[Max][Max];//我们规定画布大小为：Max * Max

三、基础函数：

1、构造二叉树

//先序建立二叉树，并且给出坐标
void creatTree(tree &T ,int x,int y)
{char c;cin >> c;if(c == '#') T=NULL;else{   //传值T=new Node;T->date=c;	T->x=x;T->y=y;creatTree(T->lchild,x-2,y+1); //左子树坐标，次数横坐标偏移量为2是为了方便在中间插入'/'creatTree(T->rchild,x+2,y+1); //右子树坐标}
}

2、三个遍历

//先序遍历
void DLR(tree  &T)
{if(T){cout << T->date << " ";DLR(T->lchild);DLR(T->rchild);}
}
//中序遍历
void LDR(tree T)
{if(T){LDR(T->lchild);cout << T->date << " ";LDR(T->rchild);}
}
//后序遍历
void LRD(tree T)
{if(T){LRD(T->lchild);LRD(T->rchild);cout << T->date << " ";}
}

3、计算结点总数、叶子结点树、树高

//结点总数
int countNode(tree T)
{int l,r;//左右子树的结点数if(!T) return  0;if(!T->rchild && T->rchild) return 1;else{l= countNode(T->lchild);r= countNode(T->rchild);return l+r+1;}
}
//叶子总数
int countLeaf(tree T)
{int leaf;if(!T) return  0;if(!T->rchild && !T->rchild) return 1;else leaf= countLeaf(T->lchild)+ countLeaf(T->rchild);return  leaf;
}
//树高
int treeHigh(tree T)
{int lh,rh;if(!T) return 0;else{lh= treeHigh(T->lchild);rh= treeHigh(T->rchild);return lh>rh ? lh+1 : rh+1;}
}

基础函数的运行举例

本次用到的输入样例：AB#DF##G##C#E##

图示如下：

 结果如下：（黄色部分）

 

 4、画图部分（有需要的小伙伴可以画图分析就很好理解了）

原版：

//画图1（此函数以美观为主）
void paintTree(tree T)
{if(T){// Max/2的使用目的是：由于原坐标是关于y轴对称的，因此我们要将整个图像沿x轴平移if(' '== t[T->x + Max/2][2 * T->y]) t[T->x + Max/2][2 * T->y]=T->date;else t[T->x + Max/2][2 * T->y]='!'; //重复就显示'！'if(T->lchild){t[T->x + Max/2 -1][2 * T->y +1]='/';paintTree(T->lchild);}if(T->rchild){t[T->x + Max/2 +1][2 * T->y +1]='\\';paintTree(T->rchild);}}
}

结果如下：

 

这里有误解！！！

我们更换一个测试用例：124##5##36##7##

用例结构如下：

 运行结果如下：

修改之后 

在次我们可以看到，这个办法会隐藏一部分的数据，当然我们也可以加以修改：

//画图1（此函数以美观为主）
void paintTree(tree T)
{if(T){// Max/2的使用目的是：由于原坐标是关于y轴对称的，因此我们要将整个图像沿x轴平移if(' '== t[T->x + Max/2][2 * T->y]) t[T->x + Max/2][2 * T->y]=T->date;//修改之后：else t[T->x + Max/2+1][2 * T->y]=T->date;//修改之前：// else t[T->x + Max/2][2 * T->y]='!'; //重复就显示'！'if(T->lchild){t[T->x + Max/2 -1][2 * T->y +1]='/';paintTree(T->lchild);}if(T->rchild){t[T->x + Max/2 +1][2 * T->y +1]='\\';paintTree(T->rchild);}}
}

运行结果如下：

再次修改：此次修改是为了不让两个元素贴在一起，但是外观还是有瑕疵

测试用例：aaaa##a##aa##a##aaa##a##aa##a##

void paintTreeplus(tree T,int l,int r)
{int mid=(l+r)/2;if(T){t[mid][2 * T->y]=T->date;if(T->lchild){for(int i=(mid+l)/2;i<mid;i++) t[i][2 * T->y+1] ='/';paintTreeplus(T->lchild,l,mid);}if(T->rchild){for(int i=mid+1;i<=(mid+r)/2;i++) t[i][2 * T->y+1] ='\\';paintTreeplus(T->rchild,mid,r);}}
}
int main()
{int minX=0,maxX=pow(2,h)+1;paintTreeplus(T,minX,maxX);for(int i=0;i<2*h;i++){for(int j=minX;j<=maxX;j++){cout << t[j][i];}cout << endl;}
}

运行结果如下：

你悟解了吗

本篇为个人学习阶段所写，请各位大佬多多斧正。

这篇关于关于二叉树（创建、遍历、画图）（个人学习使用，非专业）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/373281。

相关文章

HarmonyOS学习(七)——UI（五）常用布局总结

HarmonyOS学习(七)——UI（五）常用布局总结

自适应布局 1.1、线性布局（LinearLayout） 通过线性容器Row和Column实现线性布局。Column容器内的子组件按照垂直方向排列，Row组件中的子组件按照水平方向排列。 属性说明space通过space参数设置主轴上子组件的间距，达到各子组件在排列上的等间距效果alignItems设置子组件在交叉轴上的对齐方式，且在各类尺寸屏幕上表现一致，其中交叉轴为垂直时，取值为Vert
阅读更多...
Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya-AI分享的他在OpenAI学习到的15个提示工程技巧

Ilya（不是本人，claude AI）在社交媒体上分享了他在OpenAI学习到的15个Prompt撰写技巧。 以下是详细的内容： 提示精确化:在编写提示时,力求表达清晰准确。清楚地阐述任务需求和概念定义至关重要。例:不用"分析文本",而用"判断这段话的情感倾向:积极、消极还是中性"。 快速迭代:善于快速连续调整提示。熟练的提示工程师能够灵活地进行多轮优化。例:从"总结文章"到"用
阅读更多...
中文分词jieba库的使用与实景应用（一）

中文分词jieba库的使用与实景应用（一）

知识星球：https://articles.zsxq.com/id_fxvgc803qmr2.html 目录 一.定义： 精确模式（默认模式）： 全模式： 搜索引擎模式： paddle 模式（基于深度学习的分词模式）： 二 自定义词典 三.文本解析   调整词出现的频率 四. 关键词提取 A. 基于TF-IDF算法的关键词提取 B. 基于TextRank算法的关键词提取
阅读更多...
使用SecondaryNameNode恢复NameNode的数据

使用SecondaryNameNode恢复NameNode的数据

1）需求： NameNode进程挂了并且存储的数据也丢失了，如何恢复NameNode 此种方式恢复的数据可能存在小部分数据的丢失。 2）故障模拟 （1）kill -9 NameNode进程 [lytfly@hadoop102 current]$ kill -9 19886 （2）删除NameNode存储的数据（/opt/module/hadoop-3.1.4/data/tmp/dfs/na
阅读更多...
Hadoop数据压缩使用介绍

Hadoop数据压缩使用介绍

一、压缩原则 （1）运算密集型的Job，少用压缩 （2）IO密集型的Job，多用压缩 二、压缩算法比较 三、压缩位置选择 四、压缩参数配置 1）为了支持多种压缩/解压缩算法，Hadoop引入了编码/解码器 2）要在Hadoop中启用压缩，可以配置如下参数
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
Makefile简明使用教程

Makefile简明使用教程

文章目录 规则makefile文件的基本语法：加在命令前的特殊符号：.PHONY伪目标: Makefilev1 直观写法v2 加上中间过程v3 伪目标v4 变量 make 选项-f-n-C Make 是一种流行的构建工具，常用于将源代码转换成可执行文件或者其他形式的输出文件(如库文件、文档等)。Make 可以自动化地执行编译、链接等一系列操作。 规则 makefile文件
阅读更多...
学习hash总结

学习hash总结

2014/1/29/   最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；
阅读更多...
使用opencv优化图片（画面变清晰）

使用opencv优化图片（画面变清晰）

文章目录 需求影响照片清晰度的因素 实现降噪测试代码 锐化空间锐化Unsharp Masking频率域锐化对比测试 对比度增强常用算法对比测试 需求 对图像进行优化，使其看起来更清晰，同时保持尺寸不变，通常涉及到图像处理技术如锐化、降噪、对比度增强等 影响照片清晰度的因素 影响照片清晰度的因素有很多，主要可以从以下几个方面来分析 1. 拍摄设备 相机传感器：相机传
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2