技术标签: c语言 数据结构 visual studio
(1)n个结点的集合,如果n=0, S是空树;
(2)结点的度:一个节点含有的子树的个数;
(3)树的度:树中节点的度的最大值;
(4)树的高度(深度):树的层数。
(1)每个节点最多只能有两棵子树,也就是说二叉树不存在度大于2的节点;
(2)二叉树的子树有左右之分,左右子树的次序不能颠倒;
(3)二叉树有五种形态:①空树、②只有一个根节点、③一个根节点和一个左子树、④一个根节点和一个右子树、⑤一个根节点和左右子树。
(4)满二叉树:一个二叉树,如果每一层的节点数都达到了最大值2;
(5)完全二叉树:从上到下,从左到右,按照每个节点有两个分支进行编号,中间只要没有断开的,就是完全二叉树。
(1)先序遍历:根左右,创建二叉树,先遍历根节点,再遍历左子树,最后遍历右子树。
(2)中序遍历:左根右,创建二叉树,先遍历左子树,再遍历根节点,最后遍历右子树。
(3)后续遍历:左右根,创建二叉树,先遍历左子树,再遍历右子树,最后遍历根节点。
(4)层遍历——借助队列,从上到下,从左到右依次遍历。
算法思想:
1.将根节点入队;
2.判断队列是否为空,如果不空,则获取对头元素front,访问并出队;
3.判断front是否有左右孩子,如果有,按照先入左,再入右的顺序将孩子入队;
4.循环2.3,直到队列为空,则遍历完毕。
参考代码如下:
#include<iostream>
using namespace std;
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//节点的结构
typedef struct node
{
char value;//当前节点本身的值
struct node* left;//当前节点指向左子树的指针
struct node* right;//当前节点指向右子树的指针
}Node;
//树的结构
typedef struct tree
{
Node* root;//指向树的根节点的指针
}Tree;
//递归
void InitTree(Tree* t);//初始化树,其实就是将树的root初始化为NULL
Node* Create(char*& str);//创建二叉树,创建成功后,将根节点返回
void PreOrder(Node* root);//先序遍历以根为root的二叉树 根左右
void InOrder(Node* root);//中序遍历以根为root的二叉树 左根右
void PostOrder(Node* root);//后序遍历以根为root的二叉树 左右根
void LevOrder(Node* root);//层遍历
//根据先序遍历创建二叉树,先创建根,在创建根的左子树,最后 创建根的右子树
Node* Create(char*& str)
{
if (*str == '*')
return NULL;
else
{
Node* newnode = (Node*)malloc(sizeof(Node));//先开辟一个节点空间
newnode->value = *str;//将当前不是*的字符赋给当前节点,创建根
newnode->left = Create(++str);//创建当前节点的左子树,调用创建函数
newnode->right = Create(++str);//创建当前结点的右子树
return newnode;
}
}
//初始化
void InitTree(Tree* t)
{
t->root = NULL;
}
//递归算法——先序遍历二叉树
void PreOrder(Node* root)
{
if (root != NULL)
{
//cout << root->value << " ";//先遍历root
printf("%c ", root->value);//先遍历root
PreOrder(root->left);//遍历当前根的左子树
PreOrder(root->right);//遍历当前根的右子树
}
}
//递归算法——中序遍历二叉树
void InOrder(Node* root)
{
if (root != NULL)
{
InOrder(root->left);//先遍历左子树
printf("%c ", root->value);//遍历根
InOrder(root->right);//遍历右子树
}
}
//递归算法——后序遍历二叉树
void PostOrder(Node* root)
{
if (root != NULL)
{
PostOrder(root->left);//递归遍历左子树
PostOrder(root->right);//递归遍历右子树
printf("%c ", root->value);//遍历根
}
}
//层次遍历二叉树
void LevOrder(Node* root)
{
queue<Node*>qq;//定义队列qq,存储指向每个节点的指针
if (root == NULL)
return;
Node* front = NULL;//指向队头的指针
qq.push(root);//将根入队
while (!qq.empty())
{
front = qq.front();//获取队头
qq.pop();
printf("%c ", front->value);
//将当前front的左右孩子(下一层)入队
if (front->left != NULL)
qq.push(front->left);
if (front->right != NULL)
qq.push(front->right);
}
printf("\n");
}
int main()
{
Tree t;
InitTree(&t);//空树
char* str =(char*) "ABDG**HI****CE*J**F**";//变量强转
t.root = Create(str);
printf("先序遍历二叉树\n");
PreOrder(t.root);
printf("\n");
printf("中序遍历二叉树:\n");
InOrder(t.root);
printf("\n");
printf("后序遍历二叉树:\n");
PostOrder(t.root);
printf("\n");
printf("层遍历二叉树:\n");
LevOrder(t.root);
printf("\n");
}
非递归算法——借助栈
(1)先序遍历
算法思想:根左右
(2)中序遍历
算法思想:左根右,要将当前左子树分支上的所有节点都入栈,要么找不到
(3)后序遍历
算法思想:左右根,需要一个指针记住已经遍历过的节点
#include<iostream>
using namespace std;
#include<stack>
#include<queue>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
//节点的结构
typedef struct node
{
char value;//当前节点本身的值
struct node* left;//当前节点指向左子树的指针
struct node* right;//当前节点指向右子树的指针
}Node;
//树的结构
typedef struct tree
{
Node* root;//指向树的根节点的指针
}Tree;
//非递归
void InitTree(Tree* t);//初始化树,其实就是将树的root初始化为ULL
Node* Create(char*& str);//创建二叉树,创建成功后,将根节点返回
void PreOrder1(Node* root);//前序遍历
void InOrder1(Node* root);//中序遍历
void PostOrder1(Node* root);//后序遍历
//根据先序遍历创建二叉树,先创建根,在创建根的左子树,最后 创建根的右子树
Node* Create(char*& str)
{
if (*str == '*')
return NULL;
else
{
Node* newnode = (Node*)malloc(sizeof(Node));//先开辟一个节点空间
newnode->value = *str;//将当前不是*的字符赋给当前节点,创建根
newnode->left = Create(++str);//创建当前节点的左子树,调用创建函数
newnode->right = Create(++str);//创建当前结点的右子树
return newnode;
}
}
//初始化
void InitTree(Tree* t)
{
t->root = NULL;
}
void PreOrder1(Node* root)//非递归先序遍历
{
stack<Node*>ss;//定义栈,存储指向结点的指针
if (root == NULL)
return;
ss.push(root);
Node* top = NULL;//top指向栈顶元素
while (!ss.empty())
{
top = ss.top();
printf("%c ", top->value);
ss.pop();//出栈
//将当前节点的toop的孩子入栈,按照右左的顺序入栈
if (top->right != NULL)
ss.push(top->right);
if (top->left != NULL)
ss.push(top->left);
}
printf("\n");
}
void InOrder1(Node* root)//非递归中序遍历
{
if (root == NULL)
return;
Node* p = root, * top = NULL;
stack<Node*>ss;
while (p != NULL || !ss.empty())
{
//从p开始,将所有左分支入栈
while (p!=NULL)
{
ss.push(p);
p = p->left;
}
if (!ss.empty())
{
top = ss.top();
ss.pop();
printf("%c ", top->value);
//过程到当前节点的右分支
p = top->right;
}
}
printf("\n");
}
void PostOrder1(Node* root)//非递归后序遍历
{
if (root == NULL)
return;
stack<Node*>ss;
Node* top = NULL, * pre = NULL;
ss.push(root);
while (!ss.empty())
{
top = ss.top();//获得栈顶
//出栈,要么没孩子,要么孩子已经出栈
if (top->left == NULL && top->right == NULL ||pre!=NULL&& pre == top->left ||pre!=NULL&& pre == top->right)
{
printf("%c ", top->value);
ss.pop();
pre = top;//pre指针记住当前节点,为了下一次查看是否已经出栈
}
else//右孩子,则按照右左顺序入栈
{
if (top->right != NULL)
ss.push(top->right);
if (top->left != NULL)
ss.push(top->left);
}
}
printf("\n");
}
int main()
{
Tree t;
InitTree(&t);//空树
char* str =(char*) "ABDG**HI****CE*J**F**";//变量强转
t.root = Create(str);
printf("非递归先序遍历二叉树:\n");
PreOrder1(t.root);
printf("\n");
printf("非递归中序遍历二叉树:\n");
InOrder1(t.root);
printf("\n");
printf("非递归后序遍历二叉树:\n");
PostOrder1(t.root);
printf("\n");
}
如有错误,敬请指正!
您的点赞与收藏是对我最大的鼓励与支持。
文章浏览阅读1.6w次,点赞8次,收藏41次。生活中我们无时不刻不都要在网站搜索资源,但就是缺少一个趁手的资源搜索网站,如果有一个比较好的资源搜索网站可以帮助我们节省一大半时间!今天小编在这里为大家分享5款超厉害的资源搜索网站,每一款都可以让你的资源丰富精彩!网盘传奇一款最有效的网盘资源搜索网站你还在为找网站里面的资源而烦恼找不到什么合适的工具而烦恼吗?这款网站传奇网站汇聚了4853w个资源,并且它每一天都会持续更新资源;..._最全资源搜索引擎
文章浏览阅读4.5k次,点赞5次,收藏18次。阅读测试程序,设计一个Book类。函数接口定义:class Book{}该类有 四个私有属性 分别是 书籍名称、 价格、 作者、 出版年份,以及相应的set 与get方法;该类有一个含有四个参数的构造方法,这四个参数依次是 书籍名称、 价格、 作者、 出版年份 。裁判测试程序样例:import java.util.*;public class Main { public static void main(String[] args) { List <Book>_6-1 book类的设计java
文章浏览阅读613次,点赞28次,收藏27次。相比于以前的传统手工管理方式,智能化的管理方式可以大幅降低学校的运营人员成本,实现了校园导航的标准化、制度化、程序化的管理,有效地防止了校园导航的随意管理,提高了信息的处理速度和精确度,能够及时、准确地查询和修正建筑速看等信息。课题主要采用微信小程序、SpringBoot架构技术,前端以小程序页面呈现给学生,结合后台java语言使页面更加完善,后台使用MySQL数据库进行数据存储。微信小程序主要包括学生信息、校园简介、建筑速看、系统信息等功能,从而实现智能化的管理方式,提高工作效率。
传统上用户登陆状态会以 Session 的形式保存在服务器上,而 Session ID 则保存在前端的 Cookie 中;而使用 JWT 以后,用户的认证信息将会以 Token 的形式保存在前端,服务器不需要保存任何的用户状态,这也就是为什么 JWT 被称为无状态登陆的原因,无状态登陆最大的优势就是完美支持分布式部署,可以使用一个 Token 发送给不同的服务器,而所有的服务器都会返回同样的结果。有状态和无状态最大的区别就是服务端会不会保存客户端的信息。
文章浏览阅读784次。发表于10小时前| 2674次阅读| 来源TechCrunch| 19 条评论| 作者Jon EvansiOSAndroid应用开发产品编程语言JavaObjective-C摘要:即便Android市场份额已经超过80%,对于开发者来说,使用哪一个平台做开发仍然很难选择。本文从开发环境、配置、UX设计、语言、API、网络、分享、碎片化、发布等九个方面把Android和iOS_ios 开发角度
搜索引擎的发展历史可以追溯到20世纪90年代初,随着互联网的快速发展和信息量的急剧增加,人们开始感受到了获取和管理信息的挑战。这些阶段展示了搜索引擎在技术和商业模式上的不断演进,以满足用户对信息获取的不断增长的需求。
文章浏览阅读990次。对象特性是指控制对象的输出参数和输入参数之间的相互作用规律。放大系数K描述控制对象特性的静态特性参数。它的意义是:输出量的变化量和输入量的变化量之比。时间常数T当输入量发生变化后,所引起输出量变化的快慢。(动态参数) ..._控制对象特性
文章浏览阅读5.7w次,点赞50次,收藏276次。FRP搭建内网穿透1.概述:frp可以通过有公网IP的的服务器将内网的主机暴露给互联网,从而实现通过外网能直接访问到内网主机;frp有服务端和客户端,服务端需要装在有公网ip的服务器上,客户端装在内网主机上。2.简单的图解:3.准备工作:1.一个域名(www.test.xyz)2.一台有公网IP的服务器(阿里云、腾讯云等都行)3.一台内网主机4.下载frp,选择适合的版本下载解压如下:我这里服务器端和客户端都放在了/usr/local/frp/目录下4.执行命令# 服务器端给执_locyanfrp
文章浏览阅读687次。题目:http://acm.hust.edu.cn/vjudge/contest/view.action?cid=93745#problem/A题意:给出r*c的01矩阵,可以翻转格子使得0表成1,1变成0,求出最小的步数使得每一行中1的个数相等,每一列中1的个数相等。思路:网络流。容量可以保证每一行和每一列的1的个数相等,费用可以算出最小步数。行向列建边,如果该格子是_uva12534
文章浏览阅读504次。1、Let's Encrypt 90天,支持泛域名2、Buypass:https://www.buypass.com/ssl/resources/go-ssl-technical-specification6个月,单域名3、AlwaysOnSLL:https://alwaysonssl.com/ 1年,单域名 可参考蜗牛(wn789)4、TrustAsia5、Alpha..._csdn alphassl免费申请
文章浏览阅读1.6k次。测试算法的性能 很多时候我们需要对算法的性能进行测试,最简单的方式是看算法在特定的数据集上的执行时间,简单的测试算法性能的函数实现见testSort()。【思想】:用clock_t计算某排序算法所需的时间,(endTime - startTime)/ CLOCKS_PER_SEC来表示执行了多少秒。【关于宏CLOCKS_PER_SEC】:以下摘自百度百科,“CLOCKS_PE_算法性能测试
文章浏览阅读1.2k次。fromhttps://towardsdatascience.com/finding-lane-lines-simple-pipeline-for-lane-detection-d02b62e7572bIdentifying lanes of the road is very common task that human driver performs. This is important ..._lanedetectionlite