- 二叉树
-
- 一 . 概念
- 二 . 二叉树的性质
- 三 . 常见的二叉树
-
- 3.1 满二叉树
- 3.2 完全二叉树
- 3.3 二分搜索树(BST)
- 3.4 其他常见的二叉树
- 四 . 二叉树的遍历
-
- 4.1. 前序遍历(先序遍历)
- 4.2 二叉树的中序遍历
- 4.3 二叉树的后序遍历
- 4.4 二叉树的层序遍历
二叉树
一 . 概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉 树组成。
二叉树的特点：
- 每个节点最多有两棵子树，即二叉树不存在度大于 2 的结点。
- 二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。
二 . 二叉树的性质
- 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点
- 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0)
- 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶节点个数为 n2,则有n0＝n2＋1
- 具有n个节点的完全二叉树的深度k为 上取整
对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有：
(1) 若i>0，双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点
(2)若2i+1<n，左孩子序号：2i+1，否则无左孩子
(3)若2i+2<n，右孩子序号：2i+2，否则无右孩子
三 . 常见的二叉树
3.1 满二叉树
满二叉树：每一层的节点个数都是最大值，每一层节点个数都是满的。
数据结构--二叉树的概念及遍历方法二叉树
3.2 完全二叉树
完全二叉树 ：完全二叉树的节点编号和满二叉树完全一致 ----堆-优先级队列
1.完全二叉树除了最深的一层，其他层的节点全部是满的
2.最后一层的节点都是靠左排列的
数据结构--二叉树的概念及遍历方法二叉树 数据结构--二叉树的概念及遍历方法二叉树
3.3 二分搜索树(BST)
二分搜索树(BST) ：节点的值之间有一个大小关系
左子树节点值 < 根节点值 < 右子树节点值
二分搜索树的中序遍历就是一个递增的数组
在二分搜索树中查找一个元素，就是二分查找
3.4 其他常见的二叉树
平衡二叉树：该树中任意一个节点的左右子树高度差 <= 1
AVL -> 严格平衡的BST
RBTree -> “黑节点”严格平衡的BST
四 . 二叉树的遍历
所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个节点均做一次且仅做一次访问。访问节点所做的操作依赖于具体的应用问题(比如：打印节点内容、节点内容加1)。
遍历是二叉树上最重要的操作之一，是二叉树上进行其它运算之基础，一般有以下几种遍历方式：
1.前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点—>根的左子树—>根的右子树。
2.中序遍历(Inorder Traversal)——根的左子树—>根节点—>根的右子树。
3.后序遍历(Postorder Traversal)——根的左子树—>根的右子树—>根节点。
4.层序遍历(Level Traversal)——第一层从左到右遍历—>第二层从左到右遍历—>第三层从左到右遍历…
4.1. 前序遍历(先序遍历)
所谓的二叉树的先序遍历，就是“根左右”的遍历方式，即先输出根节点再一路向左子树遍历，每访问到一个根节点就输出一个值，最后再访问并输出右子树的节点。
如上图，先访问根节点，再递归访问左子树，最后递归访问右子树
代码实现如下：
public void preOrder(TreeNode root){
if(root == null){
return;
}
System.out.print(root.val +"");
preOrder(root.left);//输出左孩子
preOrder(root.right);//输出右孩子
}
迭代写法为：
public List perorderTraversal(TreeNode root){
List ret = new ArrayList<>();
if(root == null){
return null;
}
Deque<TreeNode> stack = new LinkedList<>();
stack.push(root);
while (!stack.isEmpty()){
TreeNode cur = stack.pop();
ret.add(cur.val);
if(cur.right != null){
stack.push(cur.right);
}
if(cur.left != null){
stack.push(cur.left);
}
}
return ret;
}
4.2 二叉树的中序遍历
二叉树的中序遍历：就是先递归访问左子树，再访问根节点，最后访问右子树
代码实现为：
public void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.left);
System.out.print(root.val +"");
inOrder(root.right);
}
迭代写法：
public List inorderTravesal(TreeNode root){
List ret = new ArrayList<>();
if(root == null){
return null;
}
Deque<TreeNode> stack = new LinkedList<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//此时向左走到底
cur = stack.pop();
ret.add(cur.val);
cur = cur.right;
}
return ret;
}
4.3 二叉树的后序遍历
二叉树的后序遍历：先递归访问左子树，再递归访问右子树，最后访问根节点
代码实现为：
public void postOrder(TreeNode root){
if(root == null){
return;
}
postOrder(root.left);
postOrder(root.right);
System.out.print(root.val +"");
}
迭代写法：
public List postorderTravesal(TreeNode root){
List ret = new ArrayList<>();
if(root == null){
return null;
}
TreeNode prev = null;
TreeNode cur = root;
Deque<TreeNode> stack = new LinkedList<>();
while (cur != null || !stack.isEmpty()){
while (cur != null){
stack.push(cur);
cur = cur.left;
}
//此时已经从左走到底
cur = stack.pop();
if(cur.right == null || cur.right == prev){
ret.add(cur.val);
prev = cur;
cur = null;
}else{
//此时cur.right != null || cur.right != prev
//右子树没处理
stack.push(cur);
cur = cur.right;
}
}
return ret;
}
4.4 二叉树的层序遍历
二叉树的层序遍历：从第一层开始逐层从左到右遍历节点
代码实现：
public void levelOrder(TreeNode root){
Deque<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
int n = queue.size();
for (int i = 0; i < n; i++) {
TreeNode node = queue.poll();
System.out.print(node.val +"");
if(node.left != null){
queue.offer(node.left);
}
if(node.right != null){
queue.offer(node.right);
}
}
}
}