C 关于二叉查找树的记忆,并简述结构接口设计

 

前言

谨以此文献给仍庸庸碌碌,却渴望成功的Me!,码农路漫漫,须求有一颗坚定的心

   最经想改写C用的安排读取接口,
准备使用hash或二叉树提到原先用的链表,进步查找功效.
就纪念一下二叉树,那里享用一下二叉查找树,代码很简单的,
适合学习使用二叉树查找.

本文转发自左耳朵耗子的博文,地址:http://coolshell.cn/articles/4990.html

亟待根基

月光博客十一月三日刊登了《写给新手程序员的一封信》,翻译自《An
open letter to those who want to start
programming
》,作者的朋友(他在本站的id是Mailper)告诉自个儿,他梦想在酷壳上看看一篇更具操作性的稿子。因为她也是喜欢编程和技术的实物,于是,作者让他把他的有的学学Python和Web编程的有的点滴统计一下。于是他给作者发来了部分他的体验和经验,小编在把她的体会做了不多的增改,并基于自己的经历增添了“进阶”一节。那是一篇由新手和自作者那个老家伙依照大家的经历成功的作品

1.具备C基础知识

本身的那么些朋友把那篇小说取名叫Build Your
Programming Technical Skills,小编骨子里不知底用中文怎么翻译,但自我在写的历程中,自身觉得那很像二个打网游做任务升级的三个历程,所以取名叫“技术练级攻略”,题目有点大,呵呵,那几个题目纯粹是为了有趣那里只有是在享用Mailper和本人个人的上学经历。(注:省去了作者看成3个初学者曾经学习过的有的技艺(前几日眼看过时了),如:Delphi/Power
builder,也节省了自我学过的一对自小编觉得乏味的技艺Lotus
Notes/ActiveX/COM/ADO/ATL/.NET ……)

2.理解数据结构,最好通晓一点二叉树结构

前言

您是不是觉得温馨从全校结业的时候只做过小玩具一样的顺序?走入职场后就算没有何经验也得以把以下那一个课外操练走三遍(朋友的抱怨:高校课程总是从理论出发,作业项目都看不出有哪些实际效益,不如从办事中的必要出发)

建议:

  • 毫不乱买书,不要乱追新技巧新名词,基础的事物通过不短日子累积而且还会在今后至少10年通用。
  • 抚今追昔一下历史,看看历史上时间线上技术的开拓进取,你才能知道明日会是何等。
  • 必然要起头,例子不管多么不难,提出至少自身手敲几遍看看是还是不是知道了里头的琐碎。
  • 必然要学会思考,思考为何要这么,而不是那么。还要举一反三地思索。

:你恐怕会很意外为啥上边的东西很偏Unix/Linux,那是因为小编以为Windows下的编程或然会在将来很没有前途,原因如下:

 

  • 当今的用户界面大致被八个东西主宰了,1)Web,2)移动装备iOS或Android。Windows的图形界面不吃香了。
  • 更加多的合营社在用开销低质量高的Linux和各类开源技术来构架其系统,Windows的本金太高了。
  • 微软的事物变得太快了,很不持久,他们完全是在调戏程序员。详情参见《Windows编程革命史

由此,作者个人觉得未来的趋向是前者是Web+移动,后端是Linux+开源。开发那边基本上没Windows什么事。

可见学到

启蒙入门

① 、 学习一门脚本语言,例如Python/Ruby

可以让你摆脱对底层语言的恐惧感,脚本语言可以让您快速开发出能用得上的小程序。实践项目:

  • 拍卖文件文件,可能csv (关键词 python csv, python open, python sys)
    读五个地点文件,逐行处理(例如 word count,只怕处理log)
  • 遍历本半夏件系统 (sys, os,
    path),例如写一个主次统计1个目录下拥有文件大小并按种种标准排序并保留结果
  • 跟数据库打交道 (python sqlite),写一个小脚本计算数据库里条目数量
  • 学会用种种print之类简单严酷的办法开展调节
  • 学会用Google (phrase, domain, use reader to follow tech blogs)

怎么要学脚本语言,因为她们实在是太便宜了,很多时候我们须要写点小工具或是脚本来帮大家缓解难题,你就会意识正规的编程语言太难用了。

二 、 用熟一种程序员的编辑器(不是IDE) 和部分着力工具

  • Vim / Emacs / Notepad++,学会如何安插代码补全,外观,外部命令等。
  • Source Insight (或 ctag)

采纳那些事物不是为着Cool,而是那些编辑器在查阅、修改代码/配置文章/日志会更快更有功效。

叁 、 了解Unix/Linux Shell和广大的命令行

  • 借使您用windows,至少学会用虚拟机里的linux, vmware
    player是免费的,装个Ubuntu吧
  • 美高梅娱乐4858.com,自然要少用少用图形界面。
  • 学会运用man来查看支持
  • 文件系统结构和焦点操作
    ls/chmod/chown/rm/find/ln/cat/mount/mkdir/tar/gzip …
  • 学会运用部分文本操作命令 sed/awk/grep/tail/less/more …
  • 学会使用部分管理命令 ps/top/lsof/netstat/kill/tcpdump/iptables/dd…
  • 问询/etc目录下的各个配置小说,学会查看/var/log下的系统日志,以及/proc下的种类运行音讯
  • 刺探正则表明式,使用正则表达式来查找文件。

对于程序员来说Unix/Linux比Windows不难多了。(参看作者四年前CSDN的博文《其实Unix很简单》)学会运用Unix/Linux你会发现图形界面在少数时候其实是太难用了,格外地万分地降落工作效能。

④ 、 学习Web基础(HTML/CSS/JS) + 服务器端技术 (LAMP)

今后必定是Web的世界,学习WEB基础的超级网站是W3School

  • 上学HTML基本语法
  • 读书CSS怎样选中HTML元素并应用有的主导样式(关键词:box model)
  • 学会用  Firefox + Firebug 或 chrome
    查看你觉得很炫的网页结构,并动态修改。
  • 学学运用Javascript操纵HTML元件。明白DOM和动态网页(http://oreilly.com/catalog/9780596527402)
    网上有免费的章节,丰富用了。或参阅 DOM 。
  • 学会用  Firefox + Firebug 或 chrome
    调试Javascript代码(设置断点,查看变量,品质,控制台等)
  • 在一台机械上配备Apache 或 Nginx
  • 学习PHP,让后台PHP和前台HTML举办数量交互,对服务器相应浏览器请求形成起初认识。完毕贰个表单提交和反显的成效。
  • 把PHP连接本地可能远程数据库 MySQL(MySQL 和 SQL现学现用够了)
  • 跟完二个名校的互联网编程课程(例如:http://www.stanford.edu/~ouster/cgi-bin/cs142-fall10/index.php )
    不要认为要求多于一学期时间,大学生是全职一学期选3-5门课,你业余时间一定可以跟上
  • 学学3个javascript库(例如jQuery 或 ExtJS)+  Ajax
    (异步读入3个劳动器端图片或许数据库内容)+JSON数据格式。
  • HTTP: The Definitive Guide
    读完前4章你就清楚你每天上网用浏览器的时候爆发的政工了(proxy,
    gateway, browsers)
  • 做个小网站(例如:1个小的留言板,帮忙用户登录,Cookie/Session,增、删、改、查,上传图片附件,分页突显)
  • 买个域名,租个空中,做个协调的网站。

1.做实二叉查找树

进阶加深

一 、 C语言和操作系统调用

重新学C语言,通晓指针和内存模型,用C语言落成一下种种经典的算法和数据结构。推荐《计算机程序设计艺术》、《算法导论》和《编程珠玑》。

学习(南洋理工免费课程)总括机科学和编程导论

学习(洛桑联邦理工免费课程)C语言内存管理

上学Unix/Linux系统调用(Unix高级环境编程),,了然系统层面的事物。

  • 用这几个种类知识操作一下文件系统,用户(落成一个足以拷贝目录树的小程序)
  • 用fork/wait/waitpid写三个多进度的先后,用pthread写几个三十二线程带同步或互斥的次序。多进程多进度购票的次序。
  • 用signal/kill/raise/alarm/pause/sigprocmask已毕二个多进程间的信号量通讯的主次。
  • 学会运用gcc和gdb来编程和调试程序(参看笔者的《用gdb调试程序》)
  • 学会运用makefile来编译程序。(参看作者的《跟自己一块儿写makefile》)
  • IPC和Socket的东西得以松手高级中来施行。

学习Windows SDK编程(Windows
程序设计 
MFC程序设计

  • 写3个窗口,了解WinMain/WinProcedure,以及Windows的新闻机制。
  • 写一些主次来操作Windows
    SDK中的能源文件大概各类图片控件,以及作图的编程。
  • 学学怎样运用MSDN查占星关的SDK函数,各类WM_音讯以及部分例程。
  • 那本书中有许多例程,在实践中请不要照抄,试着团结写一个融洽的例程。
  • 决不太多于了然这个事物,因为GUI正在被Web取代,主假设了然一下Windows
    图形界面的编程。@virushuo 说:“ 作者觉得GUI确实不那么吃香了,但即使知情GUI工作规律是很重点的。包涵运动装备花费,假如没有基础知识依旧很困难。或许说移动设备支出必须驾驭GUI工作,或许在win那边学,大概在mac/iOS上学”。

2、学习Java

  • Java 的学习重大是看经典的Core Java 《Java
    焦点技术编程
    》和《Java编程思想》(有两卷,我仅链了第①卷,丰裕了,因为Java的图形界面领悟就足以了)
  • 学学JDK,学会查阅Java API
    Doc http://download.oracle.com/javase/6/docs/api/
  • 问询一下Java那种虚拟机语言和C和Python语言在编译和推行上的异样。从C、Java、Python思考一下“跨平台”那种技术。
  • 学会使用IDE Eclipse,使用Eclipse 编译,调试和付出Java程序。
  • 建3个Tomcat的网站,尝试一下JSP/Servlet/JDBC/MySQL的Web开发。把前边所说的不胜PHP的小品种试着用JSP和Servlet达成一下。

三 、Web的伊春与架构

读书HTML5,网上有那多少个广大课程,此前酷壳也介绍过很多,小编在此处就不列支了。

学习Web开发的平安题材(参考新浪乐乎被攻击的这一个事,以及Ruby的这篇文章

上学HTTP
Server的rewrite机制,Nginx的反向代理体制,fast-cgi(如:PHP-FPM

学习Web的静态页面缓存技术。

学学Web的异步工作流处理,数据Cache,数据分区,负载均衡,水平伸张的构架。

实施职责:

  • 使用HTML5的canvas 制作一些Web动画。
  • 尝试在前头开发过的要命Web应用中举办SQL注入,JS注入,以及XSS攻击。
  • 把后边开发过的十一分Web应用改成构造在Nginx + PHP-FPM +
    静态页面缓存的网站

④ 、学习关系型数据库

  • 您可以设置MSSQLServer或MySQL来读书数据库。
  • 学习读本里数据库设计的那一个范式,1NF,2NF,3NF,……
  • 学学数据库的存过,触发器,视图,建索引,游标等。
  • 学学SQL语句,通晓表连接的各个概念(参看《SQL
     Join的图示
    》)
  • 学学怎么样优化数据库查询(参看《MySQL的优化》)
  • 推行职分:设计3个论坛的数据库,至少知足3NF,使用SQL语句询问本周,本月的风靡篇章,评论最多的篇章,最活跃用户。

伍 、一些开发工具

  • 学会使用SVN或Git来保管程序版本。
  • 学会运用JUnit来对Java举办单元测试。
  • 上学C语言和Java语言的coding standard 或 coding
    guideline。(小编N年前写过一篇关C语言分外简单的稿子——《编程修养》,那样的事物你可以上网查一下,一大堆)。
  • 推荐阅读《代码大全》《重构》《代码整洁之道

2.C可观编码格式习惯

高级长远

① 、C++ / Java 和面向对象

本人个人觉得学好C++,Java也等于探囊取物。但是C++的学习曲线12分的陡。然则,我以为C++是最急需学好的语言了。参看两篇趣文“C++学习信心图
和“21天学好C++

学习(西弗吉尼亚教堂山分校免费课程)C++面向对象编程

读我的
如何学好C++”中所推荐的这些书至少三次以上(即使你对C++的驾驭可以一箭中的到像自家所写的《C++虚函数表解析》或是《C++对象内存存局)()》,或是《C/C++重返内部静态成员的陷阱》那就很是正确了)

下一场反思为啥C++要干成那样,Java则不是?你肯定要学会比较C++和Java的两样。比如,Java中的开端化,垃圾回收,接口,非常,虚函数,等等。

实践义务:

  • 用C++完结三个BigInt,协理12柒位的整形的加减乘除的操作。
  • 用C++封装1个数据结构的体积,比如hash table。
  • 用C++封装并落到实处八个智能指针(一定要利用模板)。

设计形式》必需一读,一回以上,思考一下,那二十五个形式的应用场景。紧假如两点:1)深爱组合而不是继承,2)深爱接口而不是落实。(也引进《起先设计格局》)

推行任务:

  • 利用工厂格局落成1个内存池。
  • 动用政策形式制做壹个类其得以把公文文件举办左对齐,右对齐和中对齐。
  • 选取命令方式完成三个命令行计算器,并扶助undo和redo。
  • 接纳修饰形式完成二个饭馆的屋子价格订价策略——旺季,服务,VIP、旅行团、等影响价格的因素。

上学STL的用法和其安插概念  –
容器,算法,迭代器,函数子。假使大概,请读一下其源码。

实践职责:品味利用面向对象、STL,设计格局、和WindowsSDK图形编程的各类技术

  • 做五个贪吃蛇或是俄国四方的游戏。帮助不一致的级别和难度。
  • 做三个文本浏览器,能够浏览目录下的文件,并得以对两样的文书有两样的操作,文本文件可以打开编辑,执行文书则实施之,mp4或avi文件可以播放,图片文件可以显得图片。

学习C++的部分类库的安排,如:
MFC(看看候捷先生的《浅显MFC》)
,Boost, ACE,  CPPUnit,STL
(STL只怕会太难了,不过一旦你能了然其中的设计格局和安顿性那就太好了,尽管你能深刻到自个儿写的《STL
string类的写时拷贝技术
》那就不行不利了,ACE须要很强在的系统知识,参见前边的“抓好对系统的打听”)

Java是实在的面向对象的语言,Java的设计方式多得不可能再多,也是用来上学面向对象的设计形式的极品语言了(参看Java中的设计形式)。

引进阅读《Effective Java》 and
Java解惑

学学Java的框架,Java的框架也是多,如Spring, Hibernate,Struts
等等,首倘诺学习Java的设计,如IoC等。

Java的技能也是烂多,重点学习J2EE架构以及JMS, SportageMI,
等音信传递和长途调用的技术。

学习使用Java做Web Service(法定教程在那边

施行职责: 品尝在Spring或Hibernate框架下创设一个有网络的Web
Service的长距离调用程序,并可以在七个Service中经过JMS传递音讯。

C++和Java都不是能在长时间内能学好的,C++玩是的深,Java玩的是广,作者提出双方选一个。小编个人的求学经历是:

  • 追究C++(我深究C/C++了十来年了)
  • 学学Java的各个设计情势。

贰 、坚实系统驾驭

主要阅读上面的几本书:

Unix编程艺术》精晓Unix系统领域中的设计和付出农学、思想文化系统、原则与经验。你肯定会有一种醍醐灌顶的感觉到。

Unix网络编程卷1,套接字》这是一本看完你就驾驭网络编程的书。首要注意TCP、UDP,以及多路复用的连串调用select/poll/epoll的不一样。

TCP/IP详解 卷1:协议》-
这是一本看完后你就可以当互连网黑客的书。驾驭以太网的的周转规律,通晓TCP/IP的说道,运作规律以及哪些TCP的调优。

施行职责:

  • 知晓什么是阻塞(同步IO),非阻塞(异步IO),多路复用(select, poll,
    epoll)的IO技术。
  • 写五个互连网聊天程序,有聊天服务器和三个聊天客户端(服务端用UDP对有个别或有所的的谈天客户端进Multicast或Broadcast)。
  • 写多少个简便的HTTP服务器。

Unix网络编程卷2,进程间通讯》信号量,管道,共享内存,新闻等种种IPC……
那些技巧好像有些老掉牙了,可是依然值得询问。

实践义务:

  • 关键实施种种IPC进程序通讯的章程。
  • 尝试写多个管道程序,父子进程经过管道交流数据。
  • 品尝写三个共享内存的顺序,五个经过经过共享内存交流二个C的结构体数组。

学习《Windows大旨编程》一书。把CreateProcess,Windows线程、线程调度、线程同步(伊芙nt,
 信号量,互斥量)、异步I/O,内存管理,DLL,这几大块搞掌握。

施行职务:应用CreateProcess运维多少个记事本或IE,并监督该程序的周转。把前边写过的拾分简单的HTTP服务用线程池达成一下。写三个DLL的钩子程序监控钦命窗口的关门事件,或是记录有些窗口的按键。

有了多线程、多进度通讯,TCP/IP,套接字,C++和设计情势的中坚,你能够商讨一下ACE了。使用ACE重写上述的聊天程序和HTTP服务器(带线程池)

执行任务:因而上述的兼具知识,尝试

  • 写3个服务端给客户端传大文件,必要把100M的带宽用到八成上述。(注意,磁盘I/O和网络I/O只怕会很有标题,想一想怎么化解,其它,请小心互联网传输最大单元MTU)
  • 问询BT下载的工作规律,用多进度的办法模拟BT下载的法则。

③ 、系统架构

  • 负载均衡。HASH式的,纯动态式的。(可以到谷歌(Google)学术里搜一些至于负载均衡的稿子读读)
  • 多层分布式系统 –
    客户端服务结点层、统计结点层、数据cache层,数据层。J2EE是经典的多层构造。
  • CDN系统 –
    就近访问,内容边缘化。
  • P2P式系统,研讨一下BT和电驴的算法。比如:DHT算法
  • 服务器备份,双机备份系统(Live-Standby和Live-Live系统),两台机械如何通过心跳监测对方?集群主结点备份。
  • 虚拟化技术,使用那些技术,可以把操作系统当应用程序一下切换或重新配置和安排。
  • 学习Thrift,二进制的高质量的广播发布中间件,支持数据(对象)体系化和八系列型的RAV4PC服务。
  • 学习Hadoop。Hadoop框架中最宗旨的筹划就是:MapReduce和HDFS。MapReduce的思念是由谷歌的一篇诗歌所提及而被盛传的,简单的一句话解释MapReduce就是“职责的解释与结果的集聚”。HDFS是Hadoop分布式文件系统(Hadoop
    Distributed File System)的缩写,为分布式总括存储提供了底部接济。
  • 了解NoSQL数据库(有人说只怕是贰个接通炒作的技艺),不过因为超大规模以及高并发的纯动态型网站日渐变成主流,而SNS类网站在数码存取进度中具备实时性等刚性须要,那使得近年来NoSQL数据库逐步成了芸芸众生所关切的枢纽,并大有成为取代关系型数据库而变成未来主流数据存储情势的势头。当前NoSQL数据库很多,大部分都以开源的,其中相比较出名的有:MemcacheDB、Redis、Tokyo
    Cabinet(升级版为Kyoto
    Cabinet)、Flare、MongoDB、CouchDB、Cassandra、Voldemort等。

写了那么多,回看一下,觉得温馨一定的有成就感。希望我们不用吓着,我要好那十来年也在持续地学习,明日自作者也在上学中,人生本来就是一个不辍学习和练级的进度。只是,一定有漏的,也有狼狈的,还愿意我们补充和改进。(作者会依照大家的反馈随时更新此文)欢迎大家通过本人的天涯论坛(@左耳朵耗子)和twitter(@haoel)和自身交流。

—– 更新  2011/07/19 —–

1)有心上人奇怪为何本身在那篇作品开头说了web+移动,却尚未在前边提到iOS/Android的前端开发。因为作者心头有一种感觉,移动装备上的UI最后也会被Javascript取代。我们可以用Samsung或Android看看google+,你就会知晓了。

2)有朋友说自家那边的事物太多了,不大概为了求学而学习,笔者可怜同意。作者在小说的眼下也说了要想想。此外,千万不要觉得自身说的那几个事物是部分新的技艺,那份攻略里95%之上的全是基础。而且都以洗炼的根基技术。即是能够让您一通百通的技能,也是可以让你找到一份不错工作的技艺。

3)有情侣说学那么些事物学完都40了,还不如考虑怎么去赚钱。作者想告知我们,一是本人2019年还不曾肆拾1虚岁,二是学无止境啊,三是本身不认为赚钱有多难,难的是怎么让您值那么多钱?无论是打工仍旧创业,是什么事物让你自个儿的市值,让您集团的价值更高昂?其余地方作者不敢说,对于互连网或IT公司来说,技术实力相对是里面之一。

4)有心上人说技术都以工具,不该那样着迷那句话没有错,有时候大家必要更多的是抬初步来看看技术以外的政工,可能是说作者们在作技术的时候不去思维为啥会有其一技能,为什么不是其他,难题不在于技术,难点在于大家死读书,读死书,成了技术的书呆子。

5)
对于NoSQL,方今比较火,但作者对其某些保守,所以,作者只是说通晓就足以。对于Hadoop,作者觉着其在分布式系统上有巨大的潜力,所以必要上学。 对于关系型数据库,的确是很关键的事物,那点是小编的不经意,在原文里补充。

3.tree 数据结构两种流行套路(设计)

 

参照

1.二叉查找树简单分析
http://www.cppblog.com/cxiaojia/archive/2012/08/09/186752.html

(上边十一分博文, 图形讲解的恨透,可是那种tree数据结构,不要参照)

 

正文

1 间接奔大旨 说二叉查找树难题

1.1 不难说一下二叉查找树原理和突破

  二叉树也是个经典的数据结构,可是工作中用的光景不多,不过大家常用过,例如map,自带排序的k-v结构.

二叉树相比双向链表在变更了插入和删除格局,使查找代价变小.因而适用领域在火速搜索的领域.对于那种飞速删除,

很快插入的领域并不适合. 

  大家今天重点回看的是二叉查找(搜索)树. 首先看望数据结构如下

/*
*  这里简单的温故一下 , 二叉查找树
*一切从简单的来吧
*/
typedef int node_t;
typedef struct tree {
    node_t v; //这里简单测试一下吧,从简单做起

    struct tree* lc;
    struct tree* rc;
} *tree_t;

地点相比较简陋,不是很通用,方便了然原理设计,最终会带我们规划有些通用的二叉树结构. 那里扯一点,

布局会影响算法,算法信赖特定的结构.蛋和鸡的题材,先有2个不佳的蛋,孵化3个不好的鸡,后来鸡下了恒河沙数蛋,其中一个蛋很好,

孵化了一个很好的鸡,最终蛋鸡优异循环现身了.

对此二叉查找树,除了剔除比较复杂一点,其它的依然很日产的代码,那里从怎么样找到1个结点的父节点出发.看上面代码

/*
*  查找这个结点的父结点
* root    : 头结点
* v    : 查找的结点
*         : 返回这个v值的父亲结点,找不见返回NULL,可以返回孩子结点
*/
tree_t
tree_parent(tree_t root, node_t v, tree_t* pn)
{
    tree_t p = NULL;
    while (root) {
        if (root->v == v)
            break;
        p = root;
        if (root->v > v)
            root = root->lc;
        else
            root = root->rc;
    }

    if (pn) //返回它孩子结点
        *pn = root;

    return p;
}

真相思路是,营造三个指针p保存上一个结点.那一个函数比较其他函数 tree_parent 那里多重返当前的男女结点.一个函数顺带做了两件事.

这是壹个突破.推荐学习,同等代价做的事多了,价值也就升级了.

下边说一下 二叉查找树 删除原理(从地点参照文中截得,那些比较详细,可是代码写的水)

美高梅娱乐4858.com 1

代码已毕如下,有点简单,多看三次,大概调试五回了然更便于写.

/*
*  删除结点
* proot : 指向头结点的结点
* v     : 待删除的值
*/
void
tree_delete(tree_t* proot, node_t v)
{
    tree_t root, n, p, t;//n表示v结点,p表示父亲结点
    if ((!proot) || !(root = *proot)) 
        return;
    //这里就找见 v结点 n和它的父亲结点p
    p = tree_parent(root, v, &n);
    if (!n) //第零情况 没有找见这个结点直接返回
        return;

    //第一种情况,删除叶子结点,直接删除就可以此时t=NULL; 第二情况 只有一个叶子结点
    if (!n->lc || !n->rc) {
        if (!(t = n->lc)) //找见当前结点n的唯一孩子结点
            t = n->rc;
        if (!p)
            *proot = NULL;
        else {
            if (p->lc == n) //让当前结点的父亲收养这个它唯一的孩子
                p->lc = t;
            else
                p->rc = t;
        }
        //删除当前结点并返回,C要是支持 return void; 语法就好了
        free(n); 
        return;
    }

    //第三种情况, 删除的结点有两个孩子
    //将当前结点 右子树中最小值替代为它,继承王位,它没有左儿子
    for (t = n->rc; t->lc; t = t->lc)
        ;
    n->v = t->v;//用nr替代n了,高效,并让n指向找到t的唯一右子树,
    tree_delete(&n->rc, t->v);//递归删除n右子树中最小值, 从t开始,很高效
}

第二步找见那个结点和它二伯结点,没找见它平素回到,二叔结点为了重新配置继承关系.

对于 要删除 叶子结点或只有男女的结点, 删除 走 if(!n->lc ||
!n->rc) 分支不一样是t

当只为叶子结点 t = NULL, 当有一个男女结点, t
= 后继结点,将这一个和一了,是3个突破.

最后 删除 有七个男女的结点, 大家的做法,将 它 右子树中最小值找到,让其代表自个儿, 前边在右子树中剔除 那一个结点.

1.2 不难扩大一下 递归的不成文规则

  递归超过半数流水线如下

//数据打印函数,全部输出,不会打印回车,中序递归
void
tree_print(tree_t root)
{
    if (root) { //简单中序找到最左结点,打印
        tree_print(root->lc);
        printf("%d ", root->v);
        tree_print(root->rc);
    }
}

诸如此类的递归的措施 是

 tree_print_0 => tree_print_1
=> tree_print_2 => tree_print_3 => tree_print_2 =>
tree_print_1 => tree_print_0

先入函数栈后出函数栈,递归深度太长会爆栈.上面就是大部分递归的格局.

递归中有一种特有的尾递归.不需求借助递归再次来到结果.一般递归代码在函数最尾端.例如上 删除代码,结构如下

 tree_delete_0 => tree_delete_0 => tree_delete_1 =>  tree_delete_1 =>  tree_delete_2 =>  tree_delete_2 =>  tree_delete_3 =>

那边代码就是入栈出栈,跳转到新的递归中.属于编译器关于递归的优化,不依赖递归再次回到的结果,最终一行,一般都优化为尾递归很安全.

入不一样行开发,不成文规则依旧比较多的.扯一点,
一天夜里出租车再次来到和的哥瞎扯淡, 他说有一天带壹个出品人,这个制片人打电话给3个女孩四叔,

告知她,他孙女今日夜间来他房间,痛斥一顿让她走了,前边就联系女孩大爷,女孩四叔神回复,制片人你该潜你就潜. 估量立即特别出品人心里就有

两千0个草泥马奔过,怎么就有这么一对活宝父女.

人生活宝多才欢娱,欢喜才会笑着带着’class’.

1.3 说一下接口和测试代码

  一般可以安全的编程喜欢是,先写接口,再写总的测试代码,前边代码接口打桩挨个测试. 那里总的接口和测试代码如下

/*
* 在二叉查找树中插入结点
* proot : 头结点的指针
* v     : 待插入变量值,会自动分配内存
*/
void tree_insert(tree_t* proot, node_t v);

//数据打印函数,全部输出,不会打印回车,中序递归
void tree_print(tree_t root);

/*
*  在这个二叉查找树中查找 值为v的结点,找不见返回NULL
* root    : 头结点
* v    : 查找结点值
*         : 返回值为查找到的结点,找不见返回NULL
*/
tree_t tree_search(tree_t root, node_t v);

/*
*  查找这个结点的父结点
* root    : 头结点
* v    : 查找的结点
*         : 返回这个v值的父亲结点,找不见返回NULL,可以返回孩子结点
*/
tree_t tree_parent(tree_t root, node_t v, tree_t* pn);

/*
*  删除结点
* proot : 指向头结点的结点
* v     : 待删除的值
*/
void tree_delete(tree_t* proot, node_t v);

/*
*  删除这个二叉查找树,并把根结点置空
* proot : 指向根结点的指针
*/
void tree_destroy(tree_t* proot);

//简单输出帮助宏
#define TREE_PRINT(root) \
    puts("当前二叉查找树的中序数据如下:"), tree_print(root), putchar('\n')

//简单的主函数逻辑
int main(int argc, char* argv[])
{
    tree_t root = NULL;
    //先创建一个二叉树 试试    
    node_t a[] = { 8,4,5,11,2,3,7,-1,9,0,1,13,12,10 };
    //中间临时变量
    tree_t tmp;
    node_t n;

    int i = -1;
    //插入数据    
    while (++i<sizeof(a) / sizeof(*a))
        tree_insert(&root, a[i]);

    //简单输出数据
    TREE_PRINT(root);

    //这里查找数据,删除数据打印数据
    n = 5;
    tmp = tree_search(root, n);
    if (tmp == NULL)
        printf("root is no find %d!\n", n);
    else
        printf("root is find %d, is %p,%d!\n", n, tmp, tmp->v);

    //查找父亲结点
    n = 12;
    tmp = tree_parent(root, n, NULL);
    if (tmp == NULL)
        printf("root is no find %d!\n", n);
    else
        printf("root is find parent %d, is %p,%d!\n", n, tmp, tmp->v);

    //删除测试
    n = 8;
    tree_delete(&root, n);
    TREE_PRINT(root);

    n = 9;
    tree_delete(&root, n);
    TREE_PRINT(root);

    //释放资源
    tree_destroy(&root);

    system("pause");
    return 0;
}

测试代码就是把表明的接口挨个测试一次.对于代码打桩意思就是总结的贯彻接口,让其能编译通过.如下

/*
*  在这个二叉查找树中查找 值为v的结点,找不见返回NULL
* root    : 头结点
* v    : 查找结点值
*         : 返回值为查找到的结点,找不见返回NULL
*/
tree_t
tree_search(tree_t root, node_t v)
{

    return NULL;
}

哪怕打桩. 到此地基本都万事具备了.设计思路有了,原理也精晓了,上面上三个完完全全案例看结果.

 

2.汇总代码, 看运行结果

  首先看运营结果截图

美高梅娱乐4858.com 2

追寻,删除,打印都来了一次, 具体的完成代码如下

#include <stdio.h>
#include <stdlib.h>
#include <errno.h>
#include <string.h>

//控制台打印错误信息, fmt必须是双引号括起来的宏
#ifndef CERR
#define CERR(fmt, ...) \
    fprintf(stderr,"[%s:%s:%d][error %d:%s]" fmt "\r\n",\
         __FILE__, __func__, __LINE__, errno, strerror(errno), ##__VA_ARGS__)

//检测并退出的宏
#define CERR_EXIT(fmt, ...) \
    CERR(fmt, ##__VA_ARGS__), exit(EXIT_FAILURE)

#endif/* !CERR */

/*
*  这里简单的温故一下 , 二叉查找树
*一切从简单的来吧
*/
typedef int node_t;
typedef struct tree {
    node_t v; //这里简单测试一下吧,从简单做起

    struct tree* lc;
    struct tree* rc;
} *tree_t;

/*
* 在二叉查找树中插入结点
* proot : 头结点的指针
* v     : 待插入变量值,会自动分配内存
*/
void tree_insert(tree_t* proot, node_t v);

//数据打印函数,全部输出,不会打印回车,中序递归
void tree_print(tree_t root);

/*
*  在这个二叉查找树中查找 值为v的结点,找不见返回NULL
* root    : 头结点
* v    : 查找结点值
*         : 返回值为查找到的结点,找不见返回NULL
*/
tree_t tree_search(tree_t root, node_t v);

/*
*  查找这个结点的父结点
* root    : 头结点
* v    : 查找的结点
*         : 返回这个v值的父亲结点,找不见返回NULL,可以返回孩子结点
*/
tree_t tree_parent(tree_t root, node_t v, tree_t* pn);

/*
*  删除结点
* proot : 指向头结点的结点
* v     : 待删除的值
*/
void tree_delete(tree_t* proot, node_t v);

/*
*  删除这个二叉查找树,并把根结点置空
* proot : 指向根结点的指针
*/
void tree_destroy(tree_t* proot);

//简单输出帮助宏
#define TREE_PRINT(root) \
    puts("当前二叉查找树的中序数据如下:"), tree_print(root), putchar('\n')

//简单的主函数逻辑
int main(int argc, char* argv[])
{
    tree_t root = NULL;
    //先创建一个二叉树 试试    
    node_t a[] = { 8,4,5,11,2,3,7,-1,9,0,1,13,12,10 };
    //中间临时变量
    tree_t tmp;
    node_t n;

    int i = -1;
    //插入数据    
    while (++i<sizeof(a) / sizeof(*a))
        tree_insert(&root, a[i]);

    //简单输出数据
    TREE_PRINT(root);

    //这里查找数据,删除数据打印数据
    n = 5;
    tmp = tree_search(root, n);
    if (tmp == NULL)
        printf("root is no find %d!\n", n);
    else
        printf("root is find %d, is %p,%d!\n", n, tmp, tmp->v);

    //查找父亲结点
    n = 12;
    tmp = tree_parent(root, n, NULL);
    if (tmp == NULL)
        printf("root is no find %d!\n", n);
    else
        printf("root is find parent %d, is %p,%d!\n", n, tmp, tmp->v);

    //删除测试
    n = 8;
    tree_delete(&root, n);
    TREE_PRINT(root);

    n = 9;
    tree_delete(&root, n);
    TREE_PRINT(root);

    //释放资源
    tree_destroy(&root);

    system("pause");
    return 0;
}
/*
* 在二叉查找树中插入结点
* proot : 头结点的指针
* v     : 待插入变量值,会自动分配内存
*/
void
tree_insert(tree_t* proot, node_t v)
{
    tree_t n, p = NULL, t = *proot;

    while (t) {
        if (t->v == v) //不让它插入重复数据
            return;
        p = t; //记录上一个结点
        t = t->v > v ? t->lc : t->rc;
    }

    //这里创建结点,创建失败直接退出C++都是这种做法
    n = calloc(sizeof(struct tree), 1);
    if (NULL == n)
        CERR_EXIT("calloc struct tree error!");
    n->v = v;

    //这里插入了,开始第一个是头结点
    if (NULL == p) {
        *proot = n;
        return;
    }
    if (p->v > v)
        p->lc = n;
    else
        p->rc = n;
}

//数据打印函数,全部输出,不会打印回车,中序递归
void
tree_print(tree_t root)
{
    if (root) { //简单中序找到最左结点,打印
        tree_print(root->lc);
        printf("%d ", root->v);
        tree_print(root->rc);
    }
}

/*
*  在这个二叉查找树中查找 值为v的结点,找不见返回NULL
* root    : 头结点
* v    : 查找结点值
*         : 返回值为查找到的结点,找不见返回NULL
*/
tree_t
tree_search(tree_t root, node_t v)
{
    while (root) {
        if (root->v == v)
            return root;
        if (root->v > v)
            root = root->lc;
        else
            root = root->rc;
    }

    return NULL;
}

/*
*  查找这个结点的父结点
* root    : 头结点
* v    : 查找的结点
*         : 返回这个v值的父亲结点,找不见返回NULL,可以返回孩子结点
*/
tree_t
tree_parent(tree_t root, node_t v, tree_t* pn)
{
    tree_t p = NULL;
    while (root) {
        if (root->v == v)
            break;
        p = root;
        if (root->v > v)
            root = root->lc;
        else
            root = root->rc;
    }

    if (pn) //返回它孩子结点
        *pn = root;

    return p;
}

/*
*  删除结点
* proot : 指向头结点的结点
* v     : 待删除的值
*/
void
tree_delete(tree_t* proot, node_t v)
{
    tree_t root, n, p, t;//n表示v结点,p表示父亲结点
    if ((!proot) || !(root = *proot)) 
        return;
    //这里就找见 v结点 n和它的父亲结点p
    p = tree_parent(root, v, &n);
    if (!n) //第零情况 没有找见这个结点直接返回
        return;

    //第一种情况,删除叶子结点,直接删除就可以此时t=NULL; 第二情况 只有一个叶子结点
    if (!n->lc || !n->rc) {
        if (!(t = n->lc)) //找见当前结点n的唯一孩子结点
            t = n->rc;
        if (!p)
            *proot = t;
        else {
            if (p->lc == n) //让当前结点的父亲收养这个它唯一的孩子
                p->lc = t;
            else
                p->rc = t;
        }
        //删除当前结点并返回,C要是支持 return void; 语法就好了
        free(n); 
        return;
    }

    //第三种情况, 删除的结点有两个孩子
    //将当前结点 右子树中最小值替代为它,继承王位,它没有左儿子
    for (t = n->rc; t->lc; t = t->lc)
        ;
    n->v = t->v;//用nr替代n了,高效,并让n指向找到t的唯一右子树,
    tree_delete(&n->rc, t->v);//递归删除n右子树中最小值, 从t开始,很高效
}


//采用后序删除
static void __tree_destroy(tree_t root)
{
    if (root) {
        __tree_destroy(root->lc);
        __tree_destroy(root->rc);
        free(root);
    }
}

/*
*  删除这个二叉查找树,并把根结点置空
* proot : 指向根结点的指针
*/
void
tree_destroy(tree_t* proot)
{
    if (proot)
        __tree_destroy(*proot);
    *proot = NULL;
}

大家温馨牵连一下,代码不多,不难学习顺带回想一下数据结构中二叉树结构,关于其中 tree_destroy 编码情势,是私家的编程习惯.

在C中变量注明后并未私自认同初始化, 所以习惯有如此的代码

struct sockaddr_in sddr;
memset(&sddr, 0, sizeof sddr);

本人觉得那样麻烦,小编习惯的写法是

struct sockaddr_in saddr = { AF_INET };

动用了一个C表明起首化不成文规则,上边和下边代码转成汇编后或然都相似.后边写法,暗许编译器帮大家把它背后没初叶化部分置成0.

还有多少个习惯,可以允许多个烂的开首,必必要有1个perfect停止,参照老C++版本的智能指针,也叫破坏指针. 做法就是

char* p = malloc(1);
free(p);
p = NULL;

预防野指针.一种残酷的做法,所以个人习惯在甘休的时候多’浪费’一点时刻纪念一下原先,再将其根本抹除,等同于亚洲飞人平昔删除全体纪念的做法.

编程的达成.最终再吐槽一下,为啥C++很烂,因为看了许多的书,如故不精通它要闹哪样.它就是一本虎爪手,左练右练上练下练都可以,终于练成了

恭喜你,这杨帆张残废证收下.

再扯一点, 为何C++中叫模板,上层语言中叫泛型? 哈哈,可以参考全特化和偏(范)特化.那里卖八个关键,可是本文中最终会有案例解决.

 

3.继往开来,了然部分数据结构设计的情势 

  上边基本都扯的大半了,那里分享C中二种的数据结构设计格局.

第一种 一切解’对象’

/*
 * C中如何封装一个 tree '结构'(结构决定算法)
 */

/*
 * 第一种思路是 一切皆'对象'
 */
struct otree {
    void* obj;
    struct otree* lc;
    struct otree* rc;
};

struct onode {
    int id;
    char* name;
};

// obj => &struct onde的思路,浪费了4字节,方便管理

大家看看这个 void*应当就了解了吧等同于上层语言中Object对象.

第二种 万物皆’泛型’

/*
 * 第二种思路是 万物皆'泛型'
 */
struct tree_node {
    struct tree_node *lc;
    struct tree_node *rc;
};

#define TREE_NODE \
    struct tree_node *__tn

struct ttree {
    TREE_NODE; //必须在第一行,不在第一行需要计算偏移量 offset

    //后面就是结构了
    int id;
    char* name;
};

上面那种相比较下面那种节约4字节.缺点调试难.还有好多种诸如模板流,特定写死流. 那里扩大一下另3个技术

有关C中宏简化结构的代码

/* IPv6 address */
struct in6_addr
{
    union
    {
        uint8_t    __u6_addr8[16];
#if defined __USE_MISC || defined __USE_GNU
        uint16_t __u6_addr16[8];
        uint32_t __u6_addr32[4];
#endif
    } __in6_u;
#define s6_addr            __in6_u.__u6_addr8
#if defined __USE_MISC || defined __USE_GNU
# define s6_addr16        __in6_u.__u6_addr16
# define s6_addr32        __in6_u.__u6_addr32
#endif
};

是还是不是很好奇,不过如此的代码,上层包块库都不推荐用,那几个都是内核层的定义.用的越多越不难出错.

到此地基本就快为止了,上边介绍的三种结构设计思路,咱们必要协调揣摩. 更加有价值.搞驾驭.

再扯一点,很久之前对这么的结构不明了

struct mem_storage{
   union {
       int again;
       void* str; 
   } mem;
   .....
};

地点again 是干吗的,后来才驾驭了,主要职能是设定内存对齐的字节数.有益于移植.使其协会体内存结构是如出一辙,也有利CPU读取.

考虑了无数不过还不晓得, 那就对了,表达您还有追求!

那边再伸张一下, 有时候

/*
 常遇见下面代码
 */
void ss_free(void* arg)
{
   if(....){
     .....
     free(arg);
     return;
   }

    ....  
}

真心 希望 C中提供 return
void; 语法,

这么就足以写成

return free(arg);

//或者
return (void)check(arg);

如此那般代码会更简明, 更雅观. 那里也足以因而宏设计处理

#define return_func(f, ...) \
    f(##__VA_ARGS__); \
    return

属于仿冒吧,希望C委员会提供 return
void; 语法!!

 

后记

  错误是在所难免的,相当指示立时改. 下次有机遇将二叉树讲透,关于安排开发库中用的二叉树结构都来一回,最终分享一下,实际利用的

库案例.拜~,

  有时候在想只要不以经济建设为骨干,是否人会更有意思一点? 有一款小网游叫中国, 挖了无数坑,就希望大CRUISER去充值,diao丝去陪练.哈哈

   

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注