LearnJava
  • Summary
    • Introduction
    • MyResume
  • 开发
    • 小程序
      • 小程序开发问题总结
      • 小程序bug
    • 环境搭建
      • Linux搭建git服务器
      • Linux切换JDK版本
      • Mac搭建http服务器
      • Ubuntu搭建C++开发环境
      • ProtoBuffer安装
      • Ubuntu开启Telnet
      • Linux搭建邮件服务器
    • 遇到的问题
      • Mac下eclipse问题
      • Mac下Github问题
      • Markdown解决方案实例
      • Spring问题
  • 编程语言
    • C++
      • C&C++框架汇总
      • C++Primer课后习题记录
      • C++疑问
      • C++与java的异同
      • C++内存模型
      • C++知识点
      • Make和Cmake
    • GO
      • Go语言简介
      • Go语言知识点
    • XML
      • XML知识点
  • 技术学习
    • JavaIO
      • AIO通信
      • IO和NIO
      • 阻塞式IO通信
      • 非阻塞式IO通信
    • 计算机网络
      • CDN
      • HTTPS协议入门
      • HTTP_POST请求的数据格式
      • HTTP错误码和出现场景
      • HTTP协议入门
      • TCP/IP协议入门
      • Wireshark抓包
      • 域名解析过程
    • 计算机原理
      • 整型计算
      • GPU
      • Swap内存
    • 架构学习
      • 分布式锁
      • 分布式系统的CAP理论
      • IaaS,PaaS,SaaS的区别
      • Web框架
      • 康威定律
      • 秒杀系统设计
      • 数据异构
      • 微服务架构入门
      • 协程
      • MQ推拉模式对比
      • UML图
      • 缓存穿透击穿和雪崩
    • 前端学习
      • 安装使用VUE
      • 搭建VUE项目
    • 大数据
      • Hadoop之HBASE
      • Hadoop之HDFS
      • Hadoop之MapReduce
      • Hadoop简介
    • 数据结构
      • 二叉树
      • 图
      • 跳表
      • Bitmap
    • 算法
      • 排序算法
        • 插入排序
        • 归并排序
        • 计数排序
        • 快速排序
        • 冒泡排序
        • 选择排序
      • Hash算法
      • MD5介绍
      • 一致性Hash算法
      • 数字全排列
      • MD5介绍
      • 储水量
      • 最大子序列
    • Java多线程
      • AQS原理
      • AtomicInteger原理
      • Condition
      • Fork/Join框架
      • happens-before
      • Java锁优化
      • Java线程池
      • Java中的阻塞队列
      • Java实现线程的三种方式
      • Lock
      • Lock的种类
      • ThreadLocal
      • 线程状态及其转换
    • Java设计模式
      • Builder模式
      • 代理模式
      • 工厂和抽象工厂模式
      • 观察者模式
      • 设计模式概述
      • 职责链模式
      • 装饰者模式
      • Java实现单例的5种方式
    • Java学习
      • Java拓展学习
        • JavaSPI
      • Java序列化
      • Java异常
      • Java注解
      • 学习UML图
      • Java的Lambda表达式
      • Java集合之ArrayList
      • Java集合之HashMap
      • Java集合之LinkedList
      • List⤅&Set的操作和遍历
      • JavaP反编译命令
      • Servlet学习
    • JVM学习
      • 分层编译
      • Java进程内存占用
      • JVM参数
      • JVM常用工具
      • JVM的内存模型
      • 垃圾回收机制
      • 看懂gc日志
      • 类加载机制和双亲委派模型
      • 类的反射
      • 自己动手编译OPENJDK
      • ASM字节码增强技术
      • CodeCache
      • GC耗时案例
      • JVM性能调优
    • Linux学习
      • gdb调试定位
      • Linux常用命令
      • Linux工具
      • Linux进程通信的方式
      • Linux文件系统结构
      • Linux系统知识点
      • Linux小技巧
      • Shell学习
      • Vim常用命令
    • Java设计模式
      • 设计模式概述
      • 代理模式
      • 装饰者模式
    • Mysql
      • InnoDB介绍
      • Mac_mysql问题
      • mysql之group_concat函数
      • mysql事务
      • Mysql优化
      • Mysql实用命令
      • mysql慢查询
      • mysql文件
      • mysql视图
      • mysql锁
      • mysql索引
      • mysql约束
      • 存储过程和触发器
      • mysql常用语法
    • Spring
      • SpringCloud
        • 搭建Jenkins自动部署
        • SpringCloud介绍
        • SpringCloudBus
        • SpringCloudConfig
        • SpringCloudEureka
        • SpringCloudFeign
        • SpringCloudHystrix
        • SpringCloudRibbon
        • SpringCloudSleuth
        • SpringCloudStream
        • SpringCloudZuul
      • FactoryBean理解
      • MyBatis入门介绍
      • rose框架学习
      • SpringMVC的启动流程
      • SpringBean的生命周期
      • SpringBoot入门
      • Spring入门AOP和IOC
      • SpringMVC入门笔记
      • SpringMVC集成Log4j2
      • web.xml详解
    • web中间件学习
      • Redis
        • Redis入门
        • Redis持久化
        • Redis的数据类型
        • Redis特性
      • Gremlin入门
      • Elasticsearch安装使用
      • HugeGraph入门
      • jetty介绍
      • Kafka介绍使用
      • Maven安装配置
      • Netty介绍使用
      • Netty的编解码
      • Maven的pom介绍
      • Nginx介绍
      • Nginx配置详解
      • ProtocolBuffers学习笔记
      • Resin学习
      • RESTful入门
      • RocketMQ入门
      • RPC入门
      • Thrift介绍
      • Tomcat常用配置
      • Tomcat学习
      • Tomcat实现
      • zookeeper入门
      • Zookerper选举原理
  • 文档读后感
    • 除了写代码你还会干什么
  • 效率提升
    • Java诊断工具Arthas
    • Mac下安装多版本java
    • Mac下显示git分支
    • Mac中Clion快捷键
    • Mac中Eclipse快捷键
    • MacShell常用快捷键
    • PlantUML入门
    • Windows与Linux服务器传文件
    • Sublime技巧
    • 搜索引擎检索技巧
  • 总结
    • 2017工作总结
Powered by GitBook
On this page
  • 一、查找节点
  • 二、计算树的深度
  • 三、清空树
  • 四、递归遍历
  • 五、按层遍历
  • 六、先序,中序遍历的非递归实现
  • 七、树的路径
  • 八、二叉树的左旋和右旋

Was this helpful?

  1. 技术学习
  2. 数据结构

二叉树

本文讲解二叉树的基本操作:

  • 查找节点

  • 计算树的高度

  • 清空树

  • 递归遍历:先序遍历、中序遍历、后序遍历

  • 按层遍历

  • 前序、中序的非递归遍历

  • 树的路径

  • 树的左旋和右旋

来看一下树的结构:

class TreeNode {
    String value;
    TreeNode left;
    TreeNode right;
    public TreeNode() {

    }
    public TreeNode(String value) {
        this.value = value;
    }
}

首先,为了方便后面看到效果,先手动初始化一个有4个节点的二叉树:

Tree tree = new Tree();
TreeNode root = new TreeNode("root");
TreeNode node1 = new TreeNode("ndoe1");
TreeNode node2 = new TreeNode("ndoe2");
TreeNode node3 = new TreeNode("ndoe3");
root.left = node1;
root.right = node2;
node1.left = node3;

一、查找节点

//查找节点
public TreeNode findNode(TreeNode treeNode, String value) {
  if(null == treeNode)
    return null;

  if(treeNode.value.equals(value))
    return treeNode;

  TreeNode leftNode = findNode(treeNode.left, value);//递归左子树
  TreeNode rightNode = findNode(treeNode.right, value);//递归右子树
  if(leftNode.value.equals(value))
    return leftNode;
  if(rightNode.value.equals(value))
    return rightNode;

  return null;
}

二、计算树的深度

//计算树的深度
//递归方法
public int deepth(TreeNode treeNode) {
  if(treeNode == null)
    return 0;
  int left = deepth(treeNode.left);
  int right = deepth(treeNode.right);
  return left > right? left + 1: right + 1;
}

三、清空树

//清空二叉树
public void clearTreeNode(TreeNode treeNode) {
  if(null != treeNode) {
    clearTreeNode(treeNode.left);
    clearTreeNode(treeNode.right);
    treeNode = null;
  }
}

四、递归遍历

//遍历1 先序遍历
public void showDLR(TreeNode treeNode) {
  if(null != treeNode) {
    showData(treeNode);
    showDLR(treeNode.left);
    showDLR(treeNode.right);
  }
}
//遍历2 中序遍历
public void showLDR(TreeNode treeNode) {
  if(null != treeNode) {
    showLDR(treeNode.left);
    showData(treeNode);
    showLDR(treeNode.right);
  }
}
//遍历3 后序遍历
public void showLRD(TreeNode treeNode) {
  if(null != treeNode) {
    showLRD(treeNode.left);
    showLRD(treeNode.right);
    showData(treeNode);
  }
}

五、按层遍历

//遍历4 按层遍历 借助队列 先进先出
public void showByLevel(TreeNode treeNode) {
  if(null == treeNode)
    return;

  LinkedList<TreeNode> list = new LinkedList<>();
  TreeNode current;
  list.offer(treeNode);//将根节点入队

  while(!list.isEmpty()) {
    current = list.poll();//队首出队
    showData(current);//打印节点
    if(null != current.left) {
      list.offer(current.left);
    }
    if(null != current.right) {
      list.offer(current.right);
    }
  }
}

运行结果:

树的深度是:3
先序遍历:
root-->ndoe1-->ndoe3-->ndoe2-->
中序遍历:
ndoe3-->ndoe1-->root-->ndoe2-->
后序遍历:
ndoe3-->ndoe1-->ndoe2-->root-->
按层遍历
root-->ndoe1-->ndoe2-->ndoe3-->

六、先序,中序遍历的非递归实现

//遍历5 前序遍历的非递归实现
public void showDLRNotRecursion(TreeNode treeNode) {
  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = treeNode;
  while(null != node || stack.size() >0) {
    while(null != node) {
      showData(node);
      stack.push(node);
      node = node.left;
    }
    if(stack.size() > 0) {
      node = stack.pop();
      node = node.right;
    }
  }
}
//遍历6  中序遍历的非递归实现
public void showLDRNotRecursion(TreeNode treeNode) {
  Stack<TreeNode> stack = new Stack<>();
  TreeNode node = treeNode;
  while(null != node || stack.size() > 0) {
    while(null != node) {
      stack.push(node);
      node = node.left;
    }
    if(stack.size() > 0) {
      node = stack.pop();
      showData(node);
      node = node.right;
    }
  }
}

七、树的路径

public static void main(String[] args) {
    TreeNode node1 = new TreeNode("1");
    TreeNode node2 = new TreeNode("2");
    TreeNode node3 = new TreeNode("3");
    TreeNode node4 = new TreeNode("4");
    TreeNode node5 = new TreeNode("5");
    TreeNode node6 = new TreeNode("6");
    TreeNode node7 = new TreeNode("7");
    node1.left = node2;
    node1.right = node3;
    node2.left = node4;
    node2.right = node5;
    node5.left = node6;
    node5.right = node7;

    List<TreeNode> list = new ArrayList<>();
    list.add(node1);
    lujing(list, node1);
}
// 打印二叉树的所有路径
public static void lujing(List<TreeNode> list, TreeNode node) {
        if (node.left == null && node.right == null) {
            for (int i = 0; i < list.size(); i++) {
                System.out.print(list.get(i).val + " --> ");
            }
            System.out.println();
            return;
        }

        if (node.left != null) {
            List<TreeNode> newList = new ArrayList<>(list);
            newList.add(node.left);
            lujing(newList, node.left);
        }

        if (node.right != null) {
            List<TreeNode> newList = new ArrayList<>(list);
            newList.add(node.right);
            lujing(newList, node.right);
        }
    }

八、二叉树的左旋和右旋

  • 左旋:节点右儿子的左儿子(若存在)变为节点的右儿子,节点变为右儿子的左儿子;

  • 右旋:节点左二子的右儿子(若存在)变为节点的左二子,节点变为左二子的右儿子。

举个例子:

可以看到,如果旋转前是一个二叉排序树,那么旋转后仍然是一个二叉排序树。

// 左旋
public static void zuoxuan(TreeNode head) {
    TreeNode headRight = head.right;
    head.right = headRight.left;
    headRight.left = head;
}

// 右旋
public static void youxuan(TreeNode head) {
    TreeNode headLeft = head.left;
    head.left = headLeft.right;
    headLeft.right = head;
}
Previous数据结构Next图

Last updated 4 years ago

Was this helpful?