二叉树

二叉树

定义

二叉树是每个节点最多有两个子树的树结构。它有五种基本形态:二叉树可以是空集;根可以有空的左子树或右子树;或者左、右子树皆为空。

基本术语

  1. 度:节点所拥有子节点的个数
  2. 叶子节点:度为0的节点,即是没有子节点的节点
  3. 分支节点:度不为0的节点
  4. 根节点: 没有父节点的节点
  5. 层次:根节点的层次为1,其余节点的层次等于该双亲节点的层次加1
  6. 深度:树中节点的最大层次

性质

  • 性质1:二叉树第i层上的结点数目最多为 2^{i-1} (i≥1)。
  • 性质2:深度为k的二叉树至多有2{k}-1个结点(k≥1)。
  • 性质3:包含n个结点的二叉树的高度至少为log2 (n+1)
  • 性质4:在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1

满二叉树

定义

  • 除了最后一层,所有分支节点的子节点个数为2

特点

  1. 叶子只能出现在最后一层。
  2. 非叶子结点度一定是2.
  3. 在同样深度的二叉树中,满二叉树的结点个数最多,叶子树最多。

完全二叉树

定义

  • 若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。
  • 完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。
  • 一棵二叉树至多只有最下面的一层上的结点的度数可以小于2,并且最下层上的结点都集中在该层最左边的若干位置上,而在最后一层上,右边的若干结点缺失的二叉树,则此二叉树成为完全二叉树。

判断完全二叉树

  • 完全二叉树:叶节点只能出现在最下层和次下层,并且最下面一层的结点都集中在该层最左边的若干位置的二叉树
  • 满二叉树必然是完全二叉树,完全二叉树不一定是满二叉树

特点

  • 叶子结点只可能在最大的两层上出现,对任意结点,若其右分支下的子孙最大层次为L,则其左分支下的子孙的最大层次必为L 或 L+1;
  • 满二叉树一定是完全二叉树,完全二叉树不一定是满二叉树
  • 只允许最后一层有空缺结点且空缺在右边,即叶子结点只能在层次最大的两层上出现
  • 对任一结点,如果其右子树的深度为j,则其左子树的深度必为j或j+1。 即度为1的点只有1个或0个

二叉查找树

定义

  • 二叉查找树(Binary Search Tree),也称有序二叉树(ordered binary tree),排序二叉树(sorted binary tree),是指一棵空树或者具有下列性质的二叉树:
    1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
    2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
    3. 任意节点的左、右子树也分别为二叉查找树。
    4. 没有键值相等的节点(no duplicate nodes)。

插入节点

12345678910111213141516171819202122232425262728293031323334353637383940414243

/** * 插入节点 * @param value 节点的值 */ public void insertNode(int value){ //如果根节点为null if (root==null) { root=new Node(value,null,null); //创建根节点,此时没有左右子节点 return; //返回即可,表示插入成功,这个插入的节点就是根节点 } //如果根节点已经存在,那么就需要从根节点开始比较大小 Node currentNode=root; //当前节点 Node parentNode=root; //当前节点的父节点,需要保存这个节点 boolean isLeftChild=true; //记录待插入的数是parentNode的左节点还是右节点 //当当前节点不为空,表示没有找到插入的位置,当currentNode节点为null的时候,那么这个就是待插入的位置 while(currentNode!=null){ parentNode=currentNode; //保存当前节点的父节点 //如果待插入的值小于当前值,那么到当前节点的左子树中查找 if (value<currentNode.getValue()) { currentNode=currentNode.getLeftChild(); //当前节点继续向下成为左子节点 isLeftChild=true; //左节点 }else if (value>currentNode.getValue()) { //如果待插入的数大于当前节点的值,那么到当前节点的右边查找 currentNode=currentNode.getRightNode(); isLeftChild=false; }else { //value和currentNode.value相等,不允许插入 System.out.println(value+"已经存在,不允许插入"); return; //直接返回,后面的数字不用插入了 } } //循环结束,此时的parentNode就是待插入数字的父节点 //如果待插入的节点是左子节点 if (isLeftChild) { Node node=new Node(value, null, null); parentNode.setLeftChild(node); //设置左节点 }else { //是右子节点 Node node=new Node(value, null, null); parentNode.setRightNode(node); //设置右节点 } }

查找指定值

  • 比较需要查找的值,如果大于当前节点的值,在其右子树中查找,如果小于当前节点的值,在其左子树中查找

123456789101112131415161718

/** * 在二叉查找树中查找指定的值 * @param value * @return 返回的找到的节点,如果为null表示没有找到 * 从根节点查找,比较值,如果大于,在右子树中查找,如果小于在左子树中查找 */public Node findValue(int value){ Node currentNode=this.root; //从根节点开始查找 //如果currentNode不为null并且值不相等,跳出循环的条件是:要么没有找到,返回null,要么找到了,值相等 while(currentNode!=null&&currentNode.value!=value){ if (value<currentNode.getValue()) { currentNode=currentNode.getLeftChild(); }else { currentNode=currentNode.getRightNode(); } } return currentNode;}

删除节点

  • 分为三种:
    • 删除叶子节点
    • 删除只有一个子节点的节点
    • 删除含有两个子节点的节点

参考文章

二叉树的遍历

前序遍历

  • 访问顺序: 先访问父结点,再前序遍历左子树,最后再前面序遍历右子树,即是: 父节点 – 左 子树 — 右子树
  • 图中遍历的结果是:
    1. 从根节点开始,访问1
    2. 访问2,此时的2作为父节点,访问左子树
    3. 访问4,此时的4作为父节点,访问左子树,没有左子树,访问右子树,也没有右子树,此时开始访问父节点4的右子树
    4. 访问5,此时的5作为父节点,访问左子树
    5. 访问7,此时的7作为父节点,访问左子树,没有,访问右子树
    6. 访问8 ,此时的8作为父节点,访问左子树,没有,访问右子树没有,此时以1作为父节点,开始访问有节点
    7. 访问3,此时的3作为父节点,访问左子树,没有,访问右子树
    8. 访问6,此时的6作为父节点,左右节点都没有,访问结束
  • 最后的前序遍历为:1,2,4,5,7,8,3,6。
  • 递归调用的算法如下:

123456789101112131415161718

//前序遍历对外的方法 public void PreOrder(){ PreOrder(this.root); //从根节点开始访问 } /** * 前序遍历 * 递归 * @param node 父节点 */ private void PreOrder(Node node){ //如果节点不为null if (node!=null) { System.out.println(node.getValue()); //输出值 PreOrder(node.getLeftChild()); //访问左子树 PreOrder(node.getRightNode()); //访问右子树 } }

中序遍历

  • 先中序遍历左子树,然后再访问根结点,最后再中序遍历右子树即左—根—右
  • 总的来说,把当前节点看成是根节点,如果这个根节点还存在左子树,继续向下,直到当前节点不存在左子树,那么输出当前节点即可,然后输出父节点的值,然后输出右子树的值,如此反复即可
  • 中序遍历的规则是【左根右】,我们从root节点A看起; 此时A是根节点,遍历A的左子树; A的左子树存在,找到B,此时B看做根节点,遍历B的左子树; B的左子树不存在,返回B,根据【左根右】的遍历规则,记录B,遍历B的右子树; B的右子树存在,找到C,此时C看做根节点,遍历C的左子树; C的左子树存在,找到D,由于D是叶子节点,无左子树,记录D,无右子树,返回C,根据【左根右】的遍历规则,记录C,遍历C的右子树; C的右子树不存在,返回B,B的右子树遍历完,返回A; 至此,A的左子树遍历完毕,根据【左根右】的遍历规则,记录A,遍历A的右子树; A的右子树存在,找到E,此时E看做根节点,遍历E的左子树; E的左子树不存在,返回E,根据【左根右】的遍历规则,记录E,遍历E的右子树; E的右子树存在,找到F,此时F看做根节点,遍历F的左子树; F的左子树存在,找到G,此时G看做根节点,遍历G的左子树; G的左子树存在,找到H,由于H是叶子节点,无左子树,记录H,无右子树,返回G,根据【左根右】的遍历规则,记录G,遍历G的右子树; G的右子树存在,找到K,由于K是叶子节点,无左子树,记录K,无右子树,返回G,根据【左根右】的遍历规则,记录F,遍历F的右子树; F的右子树不存在,返回F,E的右子树遍历完毕,返回A; 至此,A的右子树也遍历完毕;
  • 详细的算法如下:

123456789101112

//中序遍历对外的方法 public void InOrder(){ InOrder(this.root); //传入根节点 } private void InOrder(Node node){ if (node!=null) { InOrder(node.getLeftChild()); //先遍历左子树 System.out.println(node.getValue()); InOrder(node.getRightNode()); //遍历右子树 } }

后续遍历

  • 先后序遍历左子树,然后再后序遍历右子树,最后再访问根结点即左—右—根。
  • 总的来说,把当前节点当做根节点,只要是存在左右子树的继续向下,不输出当前节点的值,直到没有左右子树才输出,再返回,如此反复即可
  • 总结: 当根据顺序访问的时候,只要当前节点没有左右节点或者左右节点已经输出过了,才可以输出当前节点的值
  • 详细过程如下:
    1. 从根节点1开始,访问左子树2,把2当成根节点,访问左子树4,把4当成根节点,访问左子树,没有,输出4
    2. 返回父节点2,把2当成根节点,此时的左子树4已经输出了,那么开始访问右子树5,把5当成根节点,访问左子树7,把7当成根节点,访问左子树,没有,但是存在右子树8,把8当成根节点,访问左子树,没有,访问右子树,没有,此时输出8
    3. 返回父节点7,发现不存在左节点,右节点8已经输出了,因此输出7
    4. 返回父节点5,发现左节点7已经输出了,并且没有右子树,因此输出5
    5. 返回父节点2,发现左右节点都输出了,因此继续返回父4节点1
    6. 把1当成根节点,发现左子树已经遍历完成,访问左子树3,把当前的3当成根节点,访问左子树,没有,访问右子树6,把6当成根节点,发现左右子树都不存在,输出6
    7. 返回父节点3,发现没有左子树,并且右节点6已经输出了,因此输出3
    8. 返回父节点1,输出1
  • 最终的顺序为:4,8,7,5,6,3,1
  • 详细算法如下:

12345678910111213

//后序遍历对外的方法 public void PostOrder(){ this.PostOrder(this.root); //从根节点开始 } //后序遍历 private void PostOrder(Node node){ if(node!=null){ PostOrder(node.getLeftChild()); //遍历左子树 PostOrder(node.getRightNode()); //遍历右子树 System.out.println(node.getValue()); //输出 } }

红黑树

参考文章

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏王硕

原 B树C语言代码实现

6499
来自专栏Java学习网

用Java实现处理日期的工具类——常用日期处理方法

日期处理是开发过程中经常遇到的问题,以下是总结了开发中常用的方法,代码如下: import java.text.ParseException; import j...

2945
来自专栏mukekeheart的iOS之旅

二叉树的基本概念和遍历

一、二叉树的基本概念 平衡二叉树:如果一棵树不为空,并且其中所有的子树都满足各自的左子树与右子树的高度差都不超过1。(空树是平衡二叉树)  1 //判断二叉树...

24410
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

1033
来自专栏数据处理

二叉搜索树

1133
来自专栏后端之路

最熟悉的ArrayList

上来先问几个问题 ArrayList是否存在最大容量? 如果ArrayList存在最大容量 那么达到最大之后会如何处理 ArrayList的性能影响因素 Arr...

1895
来自专栏JavaEdge

AbstractList源码解析1 实现的方法2 两种内部迭代器3 两种内部类3 SubList 源码分析4 RandomAccessSubList 源码:AbstractList 作为 Lis

它实现了 List 的一些位置相关操作(比如 get,set,add,remove),是第一个实现随机访问方法的集合类,但不支持添加和替换

3712
来自专栏拭心的安卓进阶之路

Java 集合深入理解(7):ArrayList

今天心情有点美丽,学学 ArrayList 放松下吧! 什么是 ArrayList ? ? ArrayList 是 Java 集合框架中 List接口 的一个实...

2167
来自专栏猿人谷

单链表

线性表的链式表示和实现       线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以使不连续的)。因此,为...

2855
来自专栏mathor

LeetCode222. 完全二叉树的节点个数

 常规思路,遍历整棵树,时间复杂度O(N),但是有一种时间复杂度小于O(N)的做法  首先遍历头结点右子树的最左边界,如果最左边界不为空,说明头结点的左子...

903

扫码关注云+社区