普通二叉树、二叉查找树、平衡二叉树常见操作汇总
目录
总览表
普通二叉树
二叉查找树
平衡二叉树
总览表
普通二叉树
struct Node{int data;Node* lchild,rchild;
};Node* newNode(int v){Node* node = new Node;//申请变量的地址空间node->lchild = node->rchild = NULL;//新建的结点没有左右孩子node->data = v;//数据域为传进的参数值return node;
}void searchAndModifyCM(Node* root,int value,int nv){//找到所有value,替换为new value if(root==NULL)return;//递归边界if(root->data==value)root->data = nv;searchAndModifyCM(root->lchild,value,nv);//往左子树查找searchAndModifyCM(root->rchild,value,nv);//往右子数查找
}void insertCM(Node* &root,int v){//由于要对二叉树的结构进行修改，所以传入根节点的引用 if(root==NULL){//查找失败的位置，就是要插入的位置 root = newNode(v);return;}if(由具体二叉树的性质，x应插在左子树){insertCM(root->lchild,v);}else{insertCM(root->rchild,v);}
}Node* createCM(int data[],int n){//data是待插入值域的数组，n是数组长度 Node* root = NULL;for(int i=0;i<n;i++){insertCM(root,data[i]);}return root;
}二叉查找树BST
void searchAndModifyBST(Node* root,int value,int nv){//找到所有value,替换为new value if(root==NULL)return;//递归边界if(root->data==value)root->data = nv;else if(value<root->data){//根据二叉树的属性，此时应往左子树查找 searchAndModifyBST(root->lchild,value,nv); }else{searchAndModifyBST(root->rchild,value,nv); }
}void insretBST(Node* &root,int v){//由于要对二叉树的结构进行修改，所以传入根节点的引用if(root==NULL){//查找失败的位置，就是要插入的位置root = newNode(v);return;}if(x==root->data)return;//说明当前值的结点已经在BST上，直接返回else if(x<root->date)insertBST(root->lchild,v);//根据BST的性质，此时往左子树搜索 else insertBST(root->rchild,v);
}Node* createBST(int data[],int n){//data是待插入值域的数组，n是数组长度 Node* root = NULL;for(int i=0;i<n;i++){insertBST(root,data[i]);}return root;
} //以下2个函数用于辅助找到BST的前驱或后继结点
Node* findMax(Node* root){//找最右的孩子 while(root->rchild!=NULL)root=root->rchild;return root;
}Node* findMin(Node* root){//最左的孩子就是前驱 while(root->lchild!=NULL)root=root->lchild;return root;
}void deleteBSTnode(Node* &root,int v){if(root==NULL)return;//当前结点不存在，返回if(root->data == v){//找到了太子，现在找狸猫if(root->lchild==NULL&&root->rchild==NULL){//这是个叶子结点，不用找替身了直接删除root == NULL;//父节点将引用不到他 }else if(root->lchild){//优先用前驱来替代 Node* pre = findMax(root->lchild);//找到前驱结点root->data = pre->data;//用前驱替代当前结点deleteBSTnode(root->lchild,pre->data);//记得把前驱也删除 }else{Node* post = findMin(root->rchild);root->data = post->data;deleteBSTnode(root->rchild,post->data);} }else if(v<root->data)deleteBSTnode(root->lchild,v);//向左子树检索else deleteBSTnode(root->rchild,v);
} 平衡二叉树AVL
struct Node{int data,height;Node *lchild,*rchild;
};Node* newAVLNode(int v){Node* root = new Node;root->height = 1;root->data = v;root->lchild=root->rchild=NULL;return Node;
};int getHei(Node* root){if(root == NULL)return 0;//结点不存在else return root->height;
}int getBF(Node* root){return getHei(root->lchild)-getHei(root->rchild);
}int updateHei(Node* root){return max(getHei(root->lchild),getHei(root->rchild))+1;
}void L(Node* &root){//A是根节点 Node* temp = root->rchild;//B是A的右孩子 root->rchild = temp->lchild;//让B的左子树成为A的右子树temp->lchild = root;//让A成为B的左子树updateHei(root);updateHei(temp);root = temp;//将根节点设定为B
}void R(Node* &root){//B是根节点 Node* temp = root->lchild;//A是B的左孩子root->lchild = temp->rchild;//让A的右子树成为B的右子树temp->rchild = root;//让B成为A的右子树updateHei(root);updateHei(temp);root = temp;//将A设定为根节点
}void insertAVL(Node* &root,int v){if(root==NULL){root = newAVLNode(int v);return;}if(v<root->data){//插入左子树 insertAVL(root->lchild,v);updateHei(root);if(getBF(root)==2){//可能导致平衡因子正向越界 if(getBF(root->lchild)==1){//LLR(root);}else{//LRL(root->lchild);//转化成LL R(root); }}}else{//插入右子树 insertAVL(root->rchild,v);updateHei(root);if(getBF(root)==-1){//可能导致平衡因子反向越界 if(getBF(root->rchild)==-1){//RRL(root);}else{//RLR(root->rchild);//转化成RRL(root); }} }
}Node* createAVL(int data[],int n){Node* root = NULL;for(int i=0;i<n;i++){insertAVL(root,data[i]);} return root;//返回根节点
}相关文章：
Java IO系列之字节流拷贝文件性能比较
Java IO 字节流基类 InputStream--输入流， OutPutStream--输出流， 输入流用于读，输出流用于写. 字节流默认一次只读取或输出一个字节。 package jonavin.io;import java.io.BufferedInputStream; import java.io.BufferedOutputStream; impo…
引用 提高开发水平的几项必备技术
很好的一篇文章!!!（偶遇此文，英雄所见略同！） 本文列出了当今计算机软件开发和应用领域最重要十种关键技术排名，如果你想保证你现在以及未来的几年不失业，那么你最好跟上这些技术的发展。虽然你不必对这十种…
移动磁盘由于IO设备错误，要怎样寻回文件
J盘打不开由于IO设备错误，是因为这个I盘的文件系统内部结构损坏导致的。要恢复里面的数据就必须要注意，这个盘不能格式化，否则数据会进一步损坏。具体的恢复方法看正文 工具/软件：流星数据恢复软件 步骤1：先百度搜索并…
1043 Is It a Binary Search Tree
1. 这是二叉查找树BST那节的习题，要做出来这题，需要具备的基础知识有：BST的创建，涉及函数createBST，insertBST，newNode，二叉树的先序遍历、后序遍历。 2. 需要转过来的弯的有： 给定…
运用比较纯的CSS打造很Web2.0的按钮
警告：如果你在使用IE浏览此文，那么请回避一下吧! 什么，你用的还是IE6？你真奥特曼(推荐你去打小怪兽)！ 先上图，所谓有图有真相。 如果您觉得图片上这些按钮不够2.0，那没办法，请回避吧…
Elasticsearch 参考指南（脚本）
脚本 脚本模块使你可以使用脚本来评估自定义表达式，例如，你可以使用脚本将“脚本字段”作为搜索请求的一部分返回，或者为查询评估自定义分数。 默认脚本语言是Painless，附加的lang插件使你可以运行用其他语言编写的脚本࿰…
eclipse如何卸载adt插件
1、选择 Help Install New Software； 2、在Details 面板中, 点击What is already installed? 链接； 3、在Eclipse Installation Details 对话框中，选择Android DDMS和Android Development Tools ，然后点击Uninstall；…
1099 Build A Binary Search Tree
1. 本题给出了树的样子，给出了用来填充的数列，并且告诉是一棵二叉查找树。 2. 先用静态存储的方式将树的框架建立起。然后对数列进行小到大排序，利用BST中序遍历是升序的性质，通过中序遍历将数值填充的树中。 3. 层序输出的时候…
redis4.0.6集群部署（5.0.2版本更新补充）
Redis集群安装4版本需要ruby 5版本不需要ruby就能集群1集群机器分布192.168.1.133 redis1192.168.1.134 redis2192.168.1.135 redis32 免密登录ssh-keygenssh-copy-id 192.168.1.133ssh-copy-id 192.168.1.134ssh-copy-id 192.168.1.1353 关闭防火墙sy…
PHP多图片上传 并检查 加水印 源码
参数说明:$max_file_size : 上传文件大小限制, 单位BYTE$destination_folder : 上传文件路径$watermark : 是否附加水印(1为加水印,其他为不加水印);使用说明:1. 将PHP.INI文件里面的"extensionphp_gd2.dll"一行前面的;号去掉,因为我们要用到GD库;2. 将extension_dir…
C#中的委托和事件 (4)---事件和委托的编译代码
事件和委托的编译代码 这时候，我们不得不注释掉编译错误的行，然后重新进行编译，再借助Reflactor来对 event的声明语句做一探究，看看为什么会发生这样的错误： public event GreetingDelegate MakeGreet; 可以看到&#…
1066 Root of AVL Tree 需再做
1. 这题如果不知道平衡二叉树怎么平衡的(左旋右旋那一套)应该不可能做出吧，那就输出中位数回点血了。 2. 需要具备的基础知识：怎么将结点插入平衡二叉树。 3. 我犯的一个错误：把更新高度的函数直接返回了高度，而不没有修改高度。…
easyui-menu 解决disableItem不能禁用绑定事件的方法
版本：1.4. menu的disableItem方法不能禁用使用onClick方式绑定的事件。 解决思路如下： 重写disableItem方法和enableItem方法。 /*** menu方法扩展* param {Object} jq* param {Object} itemEl*/ $.extend($.fn.menu.methods, {/*** 激活选项࿰…
hadoop无法访问50070端口怎么办？
转载请注明出处：www.oldboyedu.com Hadoop 50070是hdfs的web管理页面，在搭建Hadoop集群环境时，有些大数据开发技术人员会遇到Hadoop 50070端口打不开的情况，引起该问题的原因很多，想要解决这个问题需要从以下方面进行排…
表情的机器自动识别(有图有真相)
这幅图片是我自己用C#编写的表情的机器自动识别。主要是AdaBoost的实现，训练做了几个不同版本：线性、并行和分布式，训练数据集采用的JAFFE。 有朋友问这东西有什么用处，其实主要是为了玩而已了。这是基于Paul Ekman那本著名的《情…
并查集专题练习：好朋友(未完待续)
有空再把题目补上 输入样例1 4 2 1 4 2 3 样例输出1 2 输入样例2 7 5 1 2 2 3 3 1 1 4 5 6 输出样例2 3 解题思路： 1. 这题放在并查集的专题后面，有查找也有合并，需要具备的基础只是是合并和查找的函数要会写(都很简单)。但是读到每…
android Viewpager取消预加载及Fragment方法的学习
1.在使用ViewPager嵌套Fragment的时候，由于VIewPager的几个Adapter的设置来说，都会有一定的预加载。通过设置setOffscreenPageLimit（int number) 来设置预加载的熟练，在V4包中，默认的预加载是1，即使你设置为…
前端Js框架 UI框架汇总 特性 适用范围 选择
身为一个资深后端工程师，面对层出不穷的前端框架，总让人眼花缭乱，做一个综合解析贴，从全局着眼，让我们明白各种前端框架的应用范围，为如何选择前端框架，从不同的维度提供一些线索，做…
Emptyproject分析
Emptyproject分析(SimpleSample)1，InitApp()WinMain中有一个InitApp()，在sample中存在，但是在emptyproject中没有，该函数是用于设定已经声明的一些一般变量的初始值的。比如某些按钮。2，IsDeviceAcceptable()被WinMain…
1107 Social Clusters
这道题目给出的示例如上图所示，一共有1-8这8个人(圆形)，他们拥有1-10这10个兴趣爱好(方形)，一人可以有多个爱好，拥有共同爱好的人被视为一个社区的。现在给出每个人的爱好情况，求出社区的个数，并按照从大到…
c#直接调用ssis包实现Sql Server的数据导入功能
调用ssis包实现Sql Server的数据导入功能网上已经有很多人讨论过，自己参考后也动手实现了一下，上一次笔者的项目中还用了一下这个功能。思前想后，决定还是贴一下增强记忆，高手请54.1、直接调用ssis包，需要引用Microsof…
从入门到放弃的javaScrip——队列
队列数据结构 队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。 现实中，很常见的例子就是…
css控制不换行
white-space:nowrap; 转载于:https://www.cnblogs.com/w8104254/p/4178198.html
(C++)堆排序的3个关键函数
堆排序：指使用堆结构对一个序列进行排序。所以，首先要有一个堆结构。 此处讨论递增排序。以及用最大堆。 注意：让存放堆的数组作为全局变量，n为元素个数，数组存放元素从下标1开始，n结束。 int heap[11] …
android 横竖屏限制如何配置
在开发android的应用中，有时候需要限制横竖屏切换。只需要在AndroidManifest.xml文件中加入android:screenOrientation属性限制。 ndroid:screenOrientation"landscape"是限制此页面横屏显示， ndroid:screenOrientation"portrait"是…
Java面试题总结-Day4
<?xml version"1.0" encoding"utf-8"?> Java面试题总结-Day4Java面试题总结-Day4 Table of Contents 1. ArrayList和LinkedList区别 1.1. 是否线程安全1.2. 底层数据结构1.3. 插入和删除是否受元素位置的影响1.4. 是否支持快速随机访问1.5. 内存空…
Linux 使用者身份與群組記錄的檔案
在我們Linux系統當中，預設的情況下，所有的系統上的帳號與一般身份使用者，還有那個root的相關資訊， 都是記錄在/etc/passwd這個檔案內的。至於個人的密碼則是記錄在/etc/shadow這個檔案下。 此外，Linux所有的群組名稱都…
1098 Insertion or Heap Sort 需再做
1. 应该还做过一道类似的题目，也是要求判断属于哪种排序的中间过程，并要求写出下一轮排序结果，这次的进步是上来就知道用向量存数据，这样方便直接比较，而且下标0不能存元素，因为堆排序的堆是一个完全二叉树…
基于node.js的压缩合并安装
1.构建工具（grunt,gulp） 下载地址：http://gruntjs.cn/http://gruntjs.com/（1）安装nodejs(http://www.nodejs.org/) 验证是否安装成功，命令行输入 node -v （2）grunt 的安装 安装全局…
jenkins 修改工作目录
修改Jenkins路径 Jenkins的默认安装路径是/var/lib/jenkins 现在由于这个根目录的磁盘太小，所以切换到/data 目录下。 Jenkins目录、端口、工作目录等信息在/etc/sysconfig/jenkins 下，所以需要修改这个文件。 将JENKINS_HOME"/var/lib/jenkins&quo…