当前位置：首页 > 编程日记 > 正文

【数据结构】二叉树的应用。

编程日记 2024-10-17 06:50:00

1、分别采用递归和非递归的方式编写两个函数，求一棵给定二叉树中叶子节点的个数

2、返回一棵给定二叉树在中序遍历下的最后一个结点

3、假设二叉树采用链式方式存储，root为其根节点，p和q分别指向二叉树中任意两个结点，编写一个函数，返回p和q最近的共同祖先。

在第三小题中采用递归：

思想：

1.判断root是不是NULL如果root为NULL，那么就无所谓祖先节点，直接返回NULL就好了

2.如果p在左子树中，q在右子树中，那么root肯定就是最近祖先

3.如果pq都在root的左子树，那么就需要递归root的左子树，右子树同理

（在找公共祖先上，find_ancestor函数有bug，暂勿复制！！！）

#include <stdio.h>
#include <stdlib.h>
typedef struct node{char data;struct node *lchild,*rchild;
}bintnode;bintnode *node,*p;
int count;typedef struct stack{bintnode *data[100];int tag[100];int top;
}seqstack;void push(seqstack *s,bintnode *t)
{s->data[s->top]=t;s->top++;
}bintnode* pop(seqstack *s)
{if(s->top!=0){s->top--;return (s->data[s->top]);}else{return  NULL;}
}
bintnode *createbintree()
{char ch;bintnode *t;if((ch=getchar())=='#'){t=NULL;}else{t=(bintnode *)malloc(sizeof(bintnode));t->data=ch;t->lchild=createbintree();t->rchild=createbintree();}return t;
}//递归前序遍历，返回叶子节点数 
void digui_preorder(bintnode *t)
{if(t){if(!t->lchild && !t->rchild)	{count++; return ;}digui_preorder(t->lchild);digui_preorder(t->rchild);}else	return ;
}//非递归前序遍历，返回叶子节点数 
void preorder(bintnode *t)
{seqstack s;s.top=0;while((t)||(s.top!=0)){if(t){if(!t->lchild && !t->rchild)	{count++;}push(&s,t);t=t->lchild;}else{t=pop(&s);t=t->rchild;}} 
}//返回非递归中序遍历的最后一个结点 
void inorder(bintnode *t)
{seqstack s;s.top=0;while((t!=NULL) || (s.top!=0)){if(t){push(&s,t);t=t->lchild;}else{t=pop(&s);p=t;t=t->rchild;if(t==NULL && s.top==0){printf("非递归中序遍历情况下，最后一个结点是：%c\n",p->data); }}}
}bintnode *find(bintnode *t, char str)
{bintnode *p1;if(!t)	return NULL;if(t->data==str)	return t;else{p1=find(t->lchild,str);if(p1)	return p1;else	p1=find(t->rchild,str);}
}bintnode *find_ancestor(bintnode *t,bintnode *p,bintnode *q)
{if (!t) return NULL;if (t == p || t == q) return t;bintnode *left = find_ancestor(t->lchild, p, q);bintnode *right = find_ancestor(t->rchild, p, q);if (left && right) return t;  if(left)	return left;if(right)	return right;
}int main ()
{count=0;node = createbintree();getchar();digui_preorder(node);printf("递归求解:一共有%d个叶子节点\n",count);count = 0;preorder(node);printf("非递归求解:一共有%d个叶子节点\n",count);inorder(node);char p,q;printf("请输入要查找的两个节点的值:");scanf("%c%c",&p,&q);getchar();bintnode *p1,*q1;p1=find(node,p);q1=find(node,q);bintnode *t1;	t1=find_ancestor(node,p1,q1);printf("最近的共同祖先为：%c",t1->data);return 0;
}

https://www.dkcj.cn/info/23402.html

我为我Windows Home Server 预热

这两天在下载Windows Home Server,所以找一些资料来看. 微软宣布Windows Home Server（WHS）正式推出，WHS是一个帮助家庭保护，连接并共享他们的数字媒体与文档的新解决方案。用户可以从各大在线商店进行预订，之后会在本月…

编程日记2024/10/17 06:40:00

转自：https://blog.csdn.net/boring_wednesday/article/details/78756696 宏定义语法 #define name Stuff #define PI 3.14 //定义一个M，值为3.14 #define DO_FOREVER for(;;) //定义一个死循环 #define REG register //定义REG来作为register的别…

编程日记2024/10/17 06:30:00

Linux学习笔记—— 权限及权限管理

权限及权限管理权限管理：r：w：x：三类用户：u：属主g：属组o：其他用户chown：改变文件属主（只有管理员可以使用此命令）# chown USERNAME file,...-R&…

编程日记2024/10/17 06:20:00

【ACM】签到题

#include <stdio.h> int main () {int T,a,b,c,x,ji,ya,e;scanf("%d",&T);while(T--){scanf("%d%d%d%d",&a,&b,&c,&x);ya(a*x)/(c-b);e(a*b*x)/(a*c-a*b);jiex;printf("%d %d %d\n",ji,ya,e);}return 0; }

编程日记2024/10/17 06:10:00

图解eclipse+myeclipse完全绿色版制作过程

现在在Java开发中，使用的开发工具大部分都是Eclipse，并且和Eclipse关系紧密的要数MyEclipse了，但是 MyEclipse是一个EXE可执行程序，对于没有安装Eclipse与MyEclilpse的电脑来说，首先得先解压Eclipse，然后再…

编程日记2024/10/17 06:00:00

linux proc/xx/maps文件分析

转载：https://blog.csdn.net/lijzheng/article/details/23618365 Proc/pid/maps显示进程映射了的内存区域和访问权限。对应内核中的操作集为proc_pid_maps_op，具体的导出函数为show_map。内核中进程的一段地址空间用一个vm_area_struct结构体表示&#…

编程日记2024/10/17 05:50:00

【ACM】熊孩子的乐趣

题目链接：http://acm.nuc.edu.cn/OJ/contest/show/43/1000 【问题描述】 Alice跟Bob是学校里出了名的两个熊孩子，会在任何事情上争个高低，彼此都不服输。幼儿园的老师每次分糖果的时候看到这两个熊孩子也很头疼，两个人都想占便宜…

编程日记2024/10/17 05:40:00

mysql insertOrUpdate 方法

为什么80%的码农都做不了架构师？>>> 自己对这个方法又有点小心得分享下 https://my.oschina.net/hccake/blog/777225 mysql "ON DUPLICATE KEY UPDATE" 语法如果在INSERT语句末尾指定了ON DUPLICATE KEY UPDATE，并且插入行后会导…

编程日记2024/10/17 05:30:00

软件破解工具整理收集

1.调试工具softice 2.调试工具Trw2000 3.反汇编工具Wdasm8.93 4.Hiew 5.Visual Basic程序调试工具Smartcheck 6.十六进制编辑器（如：Ultraedit、WinHex、Hex Workshop 等） 7.注册表监视工具RegShot、regmon或RegSnap 8.侦测文件类型工具…

编程日记2024/10/17 05:20:00

Linux 下 UltraEdit 版本： 16.1.0.18 破解 30 天试用限制

rm -rfd ~/.idm/uex rm -rf ~/.idm/*.spl rm -rf /tmp/*.spl

编程日记2024/10/17 05:10:00

【ACM】杭电OJ 2149

Public Sale 【问题描述】虽然不想，但是现实总归是现实，Lele始终没有逃过退学的命运，因为他没有拿到奖学金。现在等待他的，就是像FarmJohn一样的农田生涯。要种田得有田才行，Lele听说街上正在举行一场别开生面的拍…

编程日记2024/10/17 05:00:00

PV UV IP

UV （网站独立访客） 编辑UV是unique visitor的简写，是指通过互联网访问、浏览这个网页的自然人。独立IP：是指独立用户/独立访客。指访问某个站点或点击某条新闻的不同IP地址的人数，在同一天的00:00-24:00内，…

编程日记2024/10/17 04:50:00

VBA中级班课时3小结

本课内容：工作簿和工作表对象主讲：rover18 学习时间：2010年11月本节课将学习工作簿对象Workbooks、Workbook与工作表对象Worksheets、Worksheet。在我们了解了VBA的四大要素——对象、属性、方法和事件后，会发现VBA的程序是对对…

编程日记2024/10/17 04:40:00

解决firefox ubuntu无法打开页面的问题

firefox备份用户配置信息 https://support.mozilla.org/zh-CN/kb/%E5%A4%87%E4%BB%BD%E4%BD%A0%E7%9A%84%E4%BF%A1%E6%81%AF 把xxxxxxxx.default 覆盖掉xxxxxxxx.default-release里面的内容

编程日记2024/10/17 04:30:00

js构造函数式编程

1.函数式编程 //创建和初始化地图函数：function initMap(){createMap();//创建地图setMapEvent();//设置地图事件addMapControl();//向地图添加控件}//创建地图函数：function createMap(){var map new BMap.Map("dituContent");//在百度地图容…

编程日记2024/10/17 04:20:00

【ACM】绝地求生

题目链接：http://acm.nuc.edu.cn/OJ/contest/show/43/1009 【问题描述】 zbt最近喜欢上了《绝地求生》（pubg）游戏，pubg这个游戏有一种跑毒机制，每次会产生一个圆形的安全区,玩家需要从他的当前位置在一定时间内进入安…

编程日记2024/10/17 04:10:00

【oracle】dblink创建

目的：oracle中跨数据库查询两台数据库服务器db_A(本地)和db_B(远程192.168.1.100)，db_A下用户user_a 需要访问到db_B下user_b的数据解决：查询得知使用dblink(即database link 数据库链)实现过程：1、确定用户user_a有没有创建 db…

编程日记2024/10/17 04:00:00

ASan(Linux)，gcc4.8以上版本自带的内存检查工具

转自：http://shafeng.github.io/2017/05/10/asan/ 最近线上的程序总是莫名其妙崩溃,因为我们的项目使用了分布负载的机制,对于玩家的影响其实很小,但是我肯定是忍不了的…程序崩溃的core文件里面完全找不到问题所在,初步分析应该是野指针导致,仔细分析程序之后并没有…

编程日记2024/10/17 03:50:00

详解使用DockerHub官方的mysql镜像生成容器

为什么80%的码农都做不了架构师？>>> 写在前面：看到网上关于利用DockerHub官方的mysql镜像生成容器此类的文档比较少，故结合自身实践分享给大家，还望多多指教。我的需求：利用docker 镜像快速建立一个mysql…

编程日记2024/10/17 03:40:00

【ACM】奇怪的回文数

题目链接：http://acm.nuc.edu.cn/OJ/contest/show/43/1008 【问题描述】 “回文”是指正读反读都能读通的句子，它是古今中外都有的一种修辞方式和文字游戏，如“我为人人，人人为我”等。在数学中也有这样一类数字有这样的特征…

编程日记2024/10/17 03:30:00

java I/O之装饰者模式

装饰者： Decorator模式（别名Wrapper）：动态将职责附加到对象上，若要扩展功能，装饰者提供了比继承更具弹性的代替方案。装饰者模式意图： 动态的给一个对象添加额外的职责。Decorator比生产子类灵…

编程日记2024/10/17 03:20:00

ubuntu下wireshark添加root权限

wireshark要监控eth0，但是必须要root权限才行。但是，直接用root运行程序是相当危险，也是非常不方便的。解决方法如下： 1.添加wireshark用户组sudo groupadd wireshark 2.将dumpcap更改为wireshark用户组sudo chgrp wireshark /…

编程日记2024/10/17 03:10:00