关键词：
二叉树在面试过程中出现的频率非常高，因此熟练掌握二叉树是吊打面试官的必备技能。
基本认识
二叉树：是节点的一个有限集合，该集合要么为空，要么由一个根节点加上左子树和右子树组成。
特点：
- 每个节点最多有两颗子树，即二叉树不存在度大于 2 的节点。
- 二叉树的子树有左右之分，左子树在左，右子树在右。
二叉树的存储结构
二叉树的存储结构有：
- 顺序存储
- 链式存储
顺序存储
顺序存储是使用一维数组存储二叉树中的节点，节点的存储位置就是数组的下表索引。
可以看到，顺序存储结构在存储非完全二叉树时，会出现空间利用不完全的问题。对于某种极端情况，比如只有左子树，或只有右子树，采用顺序存储结构是十分浪费空间的。因此顺序存储一般适用于完全二叉树。
链式存储
链式存储是使用链表来存储，每个节点包含三个域： 数据域和左右孩子域。
二叉树遍历
二叉树的遍历方式有：
- 先序遍历
- 中序遍历
- 后序遍历
- 层级遍历
其中先中后序都是相对于根节点而言的，先序就是先根再左右孩子，中序就是先左孩子再根最后右孩子，后续就是先左孩子再右孩子最后根。层级遍历就是从上往下一层层的访问节点。
例如上面二叉树链式存储结构图，
先序： A B D E C
中序： D B E A C
后续： D E B C A
层级： A B C D E
二叉树遍历代码实现
定义二叉树节点类：
/**
* 二叉树的节点
*/
public class Node
private int value;
private Node left;
private Node right;
public Node()
public Node(int value)
this.value = value;
public int getValue()
return value;
public void setValue(int value)
this.value = value;
public Node getLeft()
return left;
public void setLeft(Node left)
this.left = left;
public Node getRight()
return right;
public void setRight(Node right)
this.right = right;
@Override
public String toString()
return "ListNode" +
"value=" + value +
", left=" + left +
", right=" + right +
'';
定义二叉树类, 通过根节点来定义：
/**
* 二叉树类
*/
public class BinaryTree
/**
* 根节点
*/
private Node root;
public BinaryTree()
public BinaryTree(int value)
Node node = new Node(value);
setRoot(node);
public Node getRoot()
return root;
public void setRoot(Node root)
this.root = root;
1. 插入节点
/**
* 往二叉树中插入节点
*
* @param value
*/
public void add(int value)
Node newNode = new Node(value);
// 没有根节点时，插入到根节点
if (root == null)
root = newNode;
else // 有节点
Node curNode = root;
while (true)
// 插入节点的值小于当前节点的值，放到当前节点的左边
if (value < curNode.getValue())
// 如果当前节点没有左孩子，则直接放入，否则继续循环
if (curNode.getLeft() == null)
curNode.setLeft(newNode);
break;
curNode = curNode.getLeft();
else if (value > curNode.getValue()) // 插入节点大于当前节点的值，放到节点的右边
if (curNode.getRight() == null)
curNode.setRight(newNode);
break;
curNode = curNode.getRight();
2. 先序遍历
/**
* 先序遍历，输出到 List 集合中
*
* @return
*/
private void pre2(Node node, List<Integer> list)
if (node == null)
return;
list.add(node.getValue());
pre2(node.getLeft(), list);
pre2(node.getRight(), list);
3. 中序遍历
/**
* 中序遍历
*
* @param node
* @param list
*/
private void middle(Node node, List<Integer> list)
if (node == null || list == null)
return;
middle(node.getLeft(), list);
list.add(node.getValue());
middle(node.getRight(), list);
4. 后序遍历
/**
* 后续遍历
*
* @param node
* @param list
*/
private void after(Node node, List<Integer> list)
if (node == null || list == null)
return;
after(node.getLeft(), list);
after(node.getRight(), list);
list.add(node.getValue());
5. 层级遍历
/**
* 层级遍历(最基本的)： 通过队列来实现
*/
public List<Integer> levelTraversal()
List<Integer> list = new ArrayList<>();
if (root == null)
return list;
Queue<Node> queue = new LinkedList<>(); // 定义一个队列
queue.add(root); // 根节点先插入队列
Node curNode;
while (!queue.isEmpty()) // 队列不为空，循环取出元素
curNode = queue.poll();
list.add(curNode.getValue());
if (curNode.getLeft() != null)
queue.add(curNode.getLeft());
if (curNode.getRight() != null)
queue.add(curNode.getRight());
return list;
6. 层级遍历, 并把每层分成一组
/**
* 层级遍历，将每一层分成一个单独的组
*/
public List<List<Integer>> levelTraversalGroup()
List<List<Integer>> resultList = new ArrayList<>(); // 包含每层的外部 list
if (root == null)
return resultList;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty())
List<Integer> sublist = new ArrayList<>(); // 存放每一层中的元素 list
int size = queue.size(); // 此时的 size() 大小就是每层中元素的个数
for (int i = 0; i < size; i++)
Node curNode = queue.poll();
sublist.add(curNode.getValue());
if (curNode.getLeft() != null)
queue.offer(curNode.getLeft());
if (curNode.getRight() != null)
queue.offer(curNode.getRight());
resultList.add(sublist); // 将每层的list 加入到外部 list 中
return resultList;
7. 层级遍历, 把每层分成一组, 并按照奇数层从右往左，偶数层从左往右
/**
* 层级遍历，将每一层分为单独的一组，并且按照 z 字形输出
*
* @return
*/
public List<List<Integer>> levelTraversalGroupZ()
List<List<Integer>> resultList = new ArrayList<>(); // 包含每层的外部 list
if (root == null)
return resultList;
Queue<Node> queue = new LinkedList<>(); // LinkedList 实现队列
queue.offer(root);
boolean right2Left = true;
while (!queue.isEmpty())
List<Integer> sublist = new ArrayList<>(); // 存放每一层中的元素 list
int size = queue.size(); // 此时的 size() 大小就是每层中元素的个数
for (int i = 0; i < size; i++)
Node curNode = queue.poll();
if (right2Left)
sublist.add(0, curNode.getValue());
else
sublist.add(curNode.getValue());
if (curNode.getLeft() != null)
queue.offer(curNode.getLeft());
if (curNode.getRight() != null)
queue.offer(curNode.getRight());
right2Left = !right2Left;
resultList.add(sublist); // 将每层的list 加入到外部 list 中
return resultList;
8. 深度优先遍历
/**
* 二叉树深度遍历，利用堆栈，先将右子树压栈，再将左子树压栈，这样左子树就再栈顶。
*
* @return
*/
private List<Integer> depthTraversal(Node root)
List<Integer> list = new ArrayList<>();
if (root == null)
return list;
Stack<Node> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty())
Node node = stack.pop();
list.add(node.getValue());
if (node.getRight() != null)
stack.push(node.getRight());
if (node.getLeft() != null)
stack.push(node.getLeft());
return list;
9. 获取第 k 层节点
/**
* 获取第 k 层元素
*
* @param level
* @return
*/
public List<Integer> getDataByLevel(int level)
List<Integer> list = new ArrayList<>();
if (root == null || level < 1)
return list;
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
int curLevel = 1;
while (!queue.isEmpty())
int size = queue.size(); // 此时的 size() 大小就是每层中元素的个数
for (int i = 0; i < size; i++)
Node curNode = queue.poll();
if (level == curLevel)
list.add(curNode.getValue());
if (curNode.getLeft() != null)
queue.offer(curNode.getLeft());
if (curNode.getRight() != null)
queue.offer(curNode.getRight());
curLevel++;
return list;
10. 查找某个值
/**
* 查找某个值
*/
private boolean query(Node node, int value)
if (node == null)
return false;
if (value < node.getValue())
return query(node.getLeft(), value);
else if (value > node.getValue())
return query(node.getRight(), value);
else
return true;
10. 获取二叉树的深度
private int getTreeDepth(Node node)
if (node == null)
return 0;
int left = getTreeDepth(node.getLeft());
int right = getTreeDepth(node.getRight());
return left > right ? left + 1 : right + 1;
11. 判断二叉树是否是平衡二叉树
private boolean isBalanceTree(Node node)
if (node == null)
return true;
int lh = getTreeDepth(node.getLeft());
int rh = getTreeDepth(node.getRight());
return Math.abs(lh - rh) <= 1 && isBalanceTree(node.getLeft()) && isBalanceTree(node.getRight());
测试代码
public class BinaryTreeDemo
public static void main(String[] args)
// 构建一个二叉树
/**
* 6
* / \\
* 4 9
* / \\ / \\
* 2 5 7 10
* / \\
* 1 3
* /
* 0
*
*
*/
BinaryTree binaryTree = new BinaryTree();
int[] arr <数据结构二叉树(代码片段)
二叉树1.DS二叉树--二叉树构建与遍历题目描述输入输出输入样例输出样例参考代码2.DS二叉树--叶子数量题目描述输入输出输入样例输出样例参考代码3.DS二叉树——二叉树之父子结点题目描述输入输出输入样例输出样例参考代码4.... 查看详情
数据结构：二叉树(代码片段)
...中序遍历后序遍历特殊的二叉树满二叉树完全二叉树最后数据结构分类中有一种很常见的结构，那就是树，树的分类很多种，包括二叉树、二叉搜索树、红黑树、B+树等等，但大多数都是基于二叉树的衍生结构，所以今天来学习... 查看详情
数据结构《四》二叉树的实现(代码片段)
队列1.树的概念2.二叉树的概念3.二叉树的性质4.二叉树的功能实现01创建二叉树与销毁二叉树02二叉树的遍历a）二叉树的前序遍历b）二叉树的中序遍历c）二叉树的后序遍历d)二叉树的层序遍历03求二叉树中结点个数04求... 查看详情
数据结构二叉树经典基础习题(代码片段)
目录 单值二叉树思路代码相同的树思路代码二叉树的前序遍历思路代码 对称二叉树思路代码另一棵树的子树思路代码二叉树遍历（较难）思路代码 平衡二叉树思路代码 单值二叉树OJ：如果二叉树每个节点都具... 查看详情
数据结构-二叉树(代码片段)
基本概念二叉树：一个有穷的结点的集合，这个集合可以为空，若不为空，则它是由根节点和称为其左子树和右子树的两个不相交的二叉树组成。有几种特殊的二叉树，分别是斜二叉树、完全二叉树和满二叉树。二叉树的几个重... 查看详情
数据结构----二叉树(未写完)(代码片段)
二叉树1)树①树的概念②树的专用名词2）二叉树①二叉树概念②特殊的二叉树③二叉树总结性质3）二叉树顺序结构和实现①堆实现堆的概念堆向下调整算法堆向上调整算法堆的接口代码实现②堆应用建堆排序topK算法4ÿ... 查看详情
java集合与数据结构二叉树(代码片段)
Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情
java集合与数据结构二叉树(代码片段)
Java集合与数据结构二叉树树型结构概念重要概念树的表示形式二叉树概念二叉树的基本形态两种特殊的二叉树二叉树的性质二叉树的遍历二叉树基本功能的实现二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树最大... 查看详情
数据结构学习笔记（二叉树）总结与整理(代码片段)
数据结构学习笔记（二叉树）总结与整理二叉树定义二叉树结构二叉树常用操作二叉树的创建递归方式二叉树的遍历非递归方式二叉树的遍历二叉树的其他功能堆（二叉树的顺序结构）堆的实现二叉树定义概念... 查看详情
数据结构学习笔记（二叉树）总结与整理(代码片段)
数据结构学习笔记（二叉树）总结与整理二叉树定义二叉树结构二叉树常用操作二叉树的创建递归方式二叉树的遍历非递归方式二叉树的遍历二叉树的其他功能堆（二叉树的顺序结构）堆的实现二叉树定义概念... 查看详情
数据结构二叉树的简单理解和代码实现(代码片段)
前言：本章主要介绍二叉树的链式结构，及其前序、中序、后序遍历操作，还有二叉树的其它基本操作包括求结点个数、求叶子结点个数、求第K层结点个数、求二叉树深度等。文章目录二叉树的链式结构二叉树的遍... 查看详情
java数据结构————二叉树(代码片段)
文章目录一、树型结构（了解）1.概念2.树与非树3.树的一些重要的概念4.树的表示形式（了解）5.树的一些应用二、二叉树1.二叉树的概念2.二叉树的基本形态3.两种特殊的二叉树4.二叉树的性质5.二叉树的存储三、... 查看详情
数据结构之二叉树(代码片段)
简述：二叉树是十分重要的数据结构，主要用来存放数据，并且方便查找等操作，在很多地方有广泛的应用。二叉树有很多种类，比如线索二叉树，二叉排序树，平衡二叉树等，本文写的是最基础最简单的二叉树。思路：二叉树... 查看详情
数据结构之二叉树的实现(代码片段)
二叉树的实现文章目录二叉树的实现二叉链表结构：建立节点之间的关系二叉树的遍历前序遍历中序遍历后序遍历层序遍历节点个数以及高度二叉树结点个数二叉树叶子节点个数二叉树第k层节点个数二叉树的深度二叉树查找... 查看详情
数据结构树相关代码（数据结构笔试复测leecode牛客）(代码片段)
图基础介绍树基础二叉树的前序遍历二叉树的中序遍历二叉树的后序遍历二叉树的层次遍历按之字形顺序打印二叉树二叉树的最大深度二叉树中和为某一值的路径(一)二叉搜索树与双向链表对称的二叉树合并二叉树二叉树的镜像... 查看详情
数据结构二叉树(代码片段)
二叉树概念在计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（leftsubtree）和“右子树”（rightsubtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树的每个结点至... 查看详情
考研数据结构与算法树与二叉树(代码片段)
考研数据结构与算法（六）树与二叉树文章目录考研数据结构与算法（六）树与二叉树一、树的概念和基础术语1.1定义1.2基础术语1.3树的性质二、二叉树2.1二叉树定义2.2二叉树性质2.2.1满二叉树2.2.2完全二叉树2.2.3... 查看详情
二叉树的存储结构(代码片段)
二叉树是非线性结构，即每个数据结点至多只有一个前驱，但可以有多个后继。它可采用顺序存储结构和链式存储结构。二叉树有两种存储结构： 顺序存储结构； 链式存储结构： 二叉链式结构 三叉... 查看详情