将BST转换为有序的双向链表!
在二叉树中,每个结点都有两个指向子结点的指针. 在双向链表中, 每个结点也有两个指针,它们分别指向前一个结点和后一个结点.由于这两种结构的相似性, 同时二叉搜索树也是一种排过序的数据结构, 因此在理论上有可能实现二叉搜索树和排序的双向链表之间的转换.
下面的文件BST_to_DL.cpp将BST转换为排序过的双向链表,请参加代码:
#include "binary_tree.h"void ConvertNode(BinaryTreeNode* pNode, BinaryTreeNode** pLastNodeInList){if(pNode == NULL)return;BinaryTreeNode* pCurrent = pNode;//首先处理左子树if(pCurrent->pLeft)ConvertNode(pNode->pLeft, pLastNodeInList);//完成pCurrent与pLastNodeInList的拼接和更替pCurrent->pLeft = *pLastNodeInList;if(*pLastNodeInList != NULL)(*pLastNodeInList)->pRight = pCurrent;*pLastNodeInList = pCurrent;//遍历到右子树if(pCurrent->pRight)ConvertNode(pCurrent->pRight,pLastNodeInList);
}BinaryTreeNode* Convert(BinaryTreeNode* pRoot){BinaryTreeNode* pLastNodeInList = NULL;ConvertNode(pRoot, &pLastNodeInList);//pLastNodeInList指向双向链表的尾结点，我们逆序返回它的头结点BinaryTreeNode* pHeadOfList = pLastNodeInList;while(pHeadOfList != NULL && pHeadOfList->pLeft != NULL)pHeadOfList = pHeadOfList->pLeft;return pHeadOfList;
}//========================测试代码 =============================
void PrintDoubleLinkedList(BinaryTreeNode* pHeadOfList){BinaryTreeNode* pNode = pHeadOfList;printf("The nodes from left to right are:\n");while(pNode != NULL){printf("%d\t", pNode->value);if(pNode->pRight == NULL)break;pNode = pNode->pRight;}printf("\nThe nodes from right to left are:\n");while(pNode != NULL){printf("%d\t", pNode->value);if(pNode->pLeft == NULL)break;pNode = pNode->pLeft;}printf("\n");
}void DestroyList(BinaryTreeNode* pHeadOfList){BinaryTreeNode* pNode = pHeadOfList;while(pNode != NULL){BinaryTreeNode* pNext = pNode->pRight;delete pNode;pNode = pNext;}
}void Test(const char* testName, BinaryTreeNode* pRoot){if(testName != NULL)printf("%s begins: \n", testName);PrintTree(pRoot);BinaryTreeNode* pHeadOfList = Convert(pRoot);PrintDoubleLinkedList(pHeadOfList);
}// 10
// / \
// 6 14
// /\ /\
// 4 8 12 16
void Test1(){BinaryTreeNode* pNode10 = CreateBinaryTreeNode(10);BinaryTreeNode* pNode6 = CreateBinaryTreeNode(6);BinaryTreeNode* pNode14 = CreateBinaryTreeNode(14);BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);BinaryTreeNode* pNode8 = CreateBinaryTreeNode(8);BinaryTreeNode* pNode12 = CreateBinaryTreeNode(12);BinaryTreeNode* pNode16 = CreateBinaryTreeNode(16);ConnectTreeNodes(pNode10, pNode6, pNode14);ConnectTreeNodes(pNode6, pNode4, pNode8);ConnectTreeNodes(pNode14, pNode12, pNode16);Test("Test1", pNode10);DestroyList(pNode4);
}// 5
// /
// 4
// /
// 3
// /
// 2
// /
// 1
void Test2(){BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);ConnectTreeNodes(pNode5, pNode4, NULL);ConnectTreeNodes(pNode4, pNode3, NULL);ConnectTreeNodes(pNode3, pNode2, NULL);ConnectTreeNodes(pNode2, pNode1, NULL);Test("Test2", pNode5);DestroyList(pNode1);
}// 1
// \
// 2
// \
// 3
// \
// 4
// \
// 5
void Test3(){BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);BinaryTreeNode* pNode2 = CreateBinaryTreeNode(2);BinaryTreeNode* pNode3 = CreateBinaryTreeNode(3);BinaryTreeNode* pNode4 = CreateBinaryTreeNode(4);BinaryTreeNode* pNode5 = CreateBinaryTreeNode(5);ConnectTreeNodes(pNode1,NULL,pNode2);ConnectTreeNodes(pNode2,NULL,pNode3);ConnectTreeNodes(pNode3,NULL,pNode4);ConnectTreeNodes(pNode4,NULL,pNode5);Test("Test3",pNode1);DestroyList(pNode1);
}//树中只有1个结点
void Test4(){BinaryTreeNode* pNode1 = CreateBinaryTreeNode(1);Test("Test4", pNode1);DestroyList(pNode1);
}//树中没有结点
void Test5(){Test("Test5",NULL);
}int main(int argc, char** argv){Test1();Test2();Test3();Test4();Test5();return 0;
}相关文章：
计算机病毒实践汇总五：搭建虚拟网络环境
在尝试学习分析的过程中，判断结论不一定准确，只是一些我自己的思考和探索。敬请批评指正！ 涉及内容： INetSim安装及使用 ApateDNS安装及使用 1. 搭建病毒分析网络环境原因 使用虚拟机作为沙箱能把病毒与外界完全隔离开，…
form表单提交前进行ajax或js验证，校验不通过不提交
在使用form表单进行提交数据前，需要进行数据的校验->表单的校验（如：两次密码输入是否相同）后台数据的校验（如：账号是否存在），这个时候，如果哪步校验不通过，…
中体骏彩C++面试题
下面是我凭记忆想到的几个题目,有需要的同学就拿去吧,我也算做了点善事. 中体骏彩C笔试题 2013-11-18 1.指针的含义是:B A.名字 B.地址 C.名称 D.符号 2.给出下面的程序输出: #include <iostream> #include <cstdlib> #include <cstring> #include <l…
Fibonacci数列的java实现
关于Fibonacci应该都比较熟悉，0,1,1,2,3.。。。。 基本公式为f(n) f(n-1) f(n-2); f(0) 0; f(1) 1; 方法1：可以运用迭代的方法实现： public static int f1(int n){if(n<1)return n;return f1(n-1) f1(n-2); }实现方法简单。 方法2&am…
stream流对象的理解及使用
我的理解：用stream流式处理数据，将数据用一个一个方法去 . （点，即调用） 得到新的数据结果，可以一步达成。 有多种方式生成 Stream Source： 从 Collection 和数组 Collection.stream()Collecti…
永成科技C++笔试题
最后几个题有点难度,在这里说一下: 永成科技C笔试题 2013-11-19 1.将1亿以内的质数存到一个超级大的数组中,用算法如何实现? 使用"筛法"求解1亿以内的质数的程序的思路: 先动态分配1亿个bit(总计12500000字节),用字节中的每一位代表每一个整数,首先将代表奇数的那…
事务库事务隔离级别
为了快速同步数据的需要，我分段执行了两次python脚本，即开启了两个进程同步数据，结果服务器不时报出数据库死锁异常，通过排查代码和数据库日志发现，是由长事务并发引起的。代码中有入账和出账两个方法，里面…
十大算法，描述+代码+演示+分析+改进（赶紧收藏！）
十大算法 1.冒泡排序 （1）算法描述 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是…
webkit入门准备
《webkit入门准备》1. Ca) Webkit代码风格b) Inlinec) Constd) 构造与析构e) 重载f) 继承2. 泛式编程a) Vector/List/HashTableb) Iteratorc) 智能指针3. 面向对象编程a) 对象概念b) …
oracle操作
一、导入dmp文件： 1.创建表空间create tablespace 表空间 datafile 路径\文件名.dbf size 1500M autoextend on next 5M maxsize 3000M;注：路径必须为已创建2.创建用户create user 用户名 identified by 密码 default tablespace 表空间;3.更改用户的表空…
一个form表单，多个提交按钮（实现不同功能和地址的提交）
直接上代码 表单部分： <form action"" name"find" method"post" enctype"multipart/form-data"><input type"text" name"name"/><br/><button οnclick"f1()"/>找…
chrome 硬件渲染(GPU Accelerated Compositing in Chrome)
原文链接 http://www.chromium.org/developers/design-documents/gpu-accelerated-compositing-in-chrome chrome 中集成了webkit,这篇文章对webkit 硬件渲染过程有详细的介绍，很好。 简介 这篇文档讲解chrome硬件加速合成的实现细节和背景。 介绍 通常来讲&#…
CCS Font 知识整理总结
总是搞不懂 CCS 中如何正确的使用字体，这下明白了。 1、什么是 font-face font-face 顾名思义，就是文字的脸。字体是文字的外在形式，就是文字的风格，是文字的外衣。比如行书、楷书、草书，都是一种字体。同样一个字每个…
Maven安装与配置（最实用！！！）eclipse中配置maven
Maven安装与配置 一、需要准备的东西 JDKEclipse（本章主要是在eclipse中进行配置maven）Maven程序包 二、下载与安装 1. 前往maven下载最新版的Maven程序： 2. 将文件解压到D:\Program Files\Apache\maven目录下（这样子放目录结…
在Ubuntu 12.04 64bit上配置,安装和运行go程序
注意:下面的安装配置均遵从官网或是教材《Go语言程序设计》中的部分内容. 顺便说下，这是一本很难得的Go语言的入门教程，非常基础和全面。起初我因为这本书的封面比较讨厌它，闲置几年之后，一次偶尔要用时静心翻阅之后，发…
Linux下三个密码生成工具
http://code.csdn.net/news/2820879 想出一个难破解且容易记的密码对不是一件简单的事情。在我为电脑设定一个新密码，或者在线注册了一个新的账号，需要输入密码的时候，脑袋就一片空白。不过，Linux下有几个密码生成工具可以使用&am…
javabean实体类与实体类之间的快速转换
一、Dozer是什么？ dozer是一个能把实体和实体之间进行转换的工具.只要建立好映射关系.就像是ORM的数据库和实体映射一样. 使用方法示例如下: // article(PO) -> articleVOArticleVO articleVO dozerMapper.map(article, ArticleVO.class);这段示例代码。将从数…
ATS程序功能和使用方法详解
转载自https://blog.zymlinux.net/index.php/archives/374 Apache Traffic Server的程序文件，与传统的服务器系统有大不同，这里我们将会对这些文件进行详细的解读，并尽可能的对程序的功能和基本用法、参数等进一步说明，以利于新入…
java 读取txt,java读取大文件
java 读取txt,java读取大文件 package com.bbcmart.util; import java.io.File;import java.io.RandomAccessFile;import java.nio.MappedByteBuffer;import java.nio.channels.FileChannel; public class Test { public static void main(String[] args) throws Exception …
Spring Boot整合Spring Data JPA操作数据
一、 Sping Data JPA 简介 Spring Data JPA 是 Spring 基于 ORM 框架、JPA 规范的基础上封装的一套 JPA 应用框架，底层使用了 Hibernate 的 JPA 技术实现，可使开发者用极简的代码即可实现对数据的访问和操作。它提供了包括增删改查等在内的常用功能&…
常用Linux命令总结
常用Linux命令总结 2013-12-08 压缩为gz格式 gzip error_2018082217.log 解压gz格式 gzip -d error_2018082217.log.gz 不解压来搜索gz格式的文件中的匹配行内容 gunzip -c 不真正解压.gz文件，而是检查该文件，不会生成多余的文件 gunzip -c error_20…
调试uIP出现死机问题
在调试uIP，加入http功能时，调试出现死循环 原因是所加入的http文件中含有printf等输出函数，遇到这种情况，有2种解决方法： 1.Keil中勾选“Use MicroLIB” 2. //加入以下代码，支持printf函数，而…
html+spring boot简单的ajax数据传输实现
本篇讲解在前后端不分离情况下的htmlspring boot的项目数据传输实现 首先，后台我写了三个接口 package com.demo.ajax.controller;import com.demo.ajax.Entity.Person; import lombok.extern.slf4j.Slf4j; import org.jboss.logging.Param; import org.springfram…
Tafficserver旁路接入方案综述
转载自 https://blog.zymlinux.net/index.php/archives/821 随着宽带技术的加速普及，目前，几款高性能开源CDN方案在广大开源爱好团队的充分的测试、企业服务应用验证中破壳而出。实际这个地球的互联网用户都在知情与不知情之间使用了ATS的环保服务。这方…
url中去掉index.php,方便redirect()
01 配置文件 return Array( URL_MODEL > 2,); 02 index.php入口文件下面加入文件 .htaccess -->使用editplus-->另存为 <IfModule mod_rewrite.c>RewriteEngine onRewriteCond %{REQUEST_FILENAME} !-dRewriteCond %{REQUEST_FILENAME} !-fRewriteRule ^(.*)$ i…
js校验复选框（多选按钮）是否被选中的方法
js校验复选框是否被选中的方法 方法一：（使用下标进行标记） if ($("#checkbox-id")get(0).checked) {// do something }方法二：（对被选中的进行操作） if($(#checkbox-id).is(:checked)) {// do…
ATS插件开发基础
转载自 https://blog.zymlinux.net/index.php/archives/540 ATS插件开发需要提前了解ATS的插件的一些设计思想，以及系统提供的一些不同方向。我们将会介绍ATS的基础开发知识，以利于后续的插件开发课程讲解。 ATS的SDK文档，是了解ATS的核心设…
NET基础（3）：is 和 as 操作符
在C#语言中进行类型转换的另外一种方式是使用is和as操作符。is检查对象是否兼容于指定类型，返回Boolean值true或false。注意，is操作符永远不抛出异常，例如以下代码： Object o new Object();Boolean b1 (o is Object); //返回…
制作大白菜PE盘
大白菜是一款功能非常强大的U盘启动盘制作工具，通过大白菜我们可以把U盘做成可以引导电脑启动的启动盘，同时可以用于装系统或维护系统，虽然制作方法非常简单，不过还是有很多人不懂如何制作大白菜U盘启动盘，这两天我刚好…
为方便ATS管理建立的一些命令别名
转载自https://blog.zymlinux.net/index.php/archives/129 玩ats经常需要切换目录什么感觉敲得麻烦了就建立了一些命令别名，就方便多了。 在用户目录下的.bashrc文件中加入以下内容： alias alogcd /usr/local/var/log/trafficserver;pwd alias atscd /us…