- 二叉树是一种特殊的树结构，应用广泛
- 下面，我将详细介绍 二叉树的相关知识，希望你们会喜欢。
示意图
示意图
示意图
二叉树的存储结构包括：顺序存储结构 & 链式存储结构
示意图
注：上述的链式存储方式，即为树结构中的孩子兄弟表示法。具体如下：
示意图
大多数情况下，二叉树的建立会采用 链式存储结构
建立的核心：
数据结构 = 链表 、实现方式 = 递归 / 非递归 算法
4.1 数据结构
采用链表的方式，也称为：二叉链表
- 为了确保每个结点都有左右孩子，所以空指针 = 虚结点 = #
- 这种处理也称：扩展二叉树
示意图
- 节点结构 & 树的定义如下
/**
* 设置结点结构
*/
public static class treenode {
t val; // 二叉树的结点数据
treenode leftnode; // 二叉树的左子树（左孩子）
treenode rightnode; // 二叉树的右子树（右孩子）
public treenode(t data,treenode left,treenode right) {
this.val = data;
this.leftnode = left;
this.rightnode = right;
}
// 获得 & 设置二叉树的结点数据
public t getdata(){
return val;
}
public void setdata(t data){
this.val = data;
}
// 获得 & 设置二叉树的左子树（左孩子）
public treenode getleftnode(){
return leftnode;
}
public void setleftnode(treenode leftnode){
this.leftnode = leftnode;
}
// 获得 & 设置二叉树的右子树（右孩子）
public treenode getrightnode(){
return rightnode;
}
public void setrightnode(treenode rightnode){
this.rightnode = rightnode;
}
}
/**
* 作用：构造二叉树
* 注：必须逆序建立，即：先建立子节点，再逆序往上建立
* 原因：非叶子节点会使用到下面的节点，而初始化是按顺序初始化的，不逆序建立会报错
*/
public node init(){
// 结构如下：(由下往上建立)
// a
// b c
// d e f
// g h i
node i = new node("i", null, null);
node h = new node("h", null, null);
node g = new node("g", null, null);
node f = new node("f", null, null);
node e = new node("e", null, i);
node d = new node("d", g, h);
node c = new node("c", e, f);
node b = new node("b", d, null);
node a = new node("a", b, c);
return a; // 返回根节点
}
4.2 递归 算法
- 通过 递归方式 构造出整个二叉树
- 构造过程 = 将遍历算法的输出结点操作 替换成： 生成结点 & 赋值操作 即可
关于遍历算法，下节会详细说明
5.1 定义
从根节点出发，按照某种次序访问二叉树中的所有结点，使得每个结点被访问1次 且 只被访问1次
5.2 遍历方式
二叉树的遍历方式包括：
- 前序遍历（深度优先遍历）
- 中序遍历
- 后序遍历
- 层序遍历（广度优先遍历）
5.3 遍历实现
遍历的实现方式分为：递归 & 非递归方式，下面会详细说明
5.3.1 前序遍历
也称 深度优先遍历
- 简介
示意图
- 递归实现
/**
* 内容：前序遍历
* 方式：递归
*/
public void preorder(node root){
// 1. 判断二叉树结点是否为空；若是，则返回空操作
if(root ==null)
return;
// 2. 访问根节点（显示根结点）
printnode(root);
// 3. 遍历左子树
preorder(root.getleftnode());
// 4. 遍历右子树
preorder(root.getrightnode());
}
示意图
- 非递归实现
主要采用 栈实现
流程图
/**
* 方式：非递归（栈实现）
*/
public static void preorder_stack(node root){
stack stack = new stack();
// 步骤1：直到当前结点为空 & 栈空时，循环结束
while(root != null || stack.size()>0){
// 步骤2：判断当前结点是否为空
// a. 若不为空，执行3
// b. 若为空，执行5
if(root != null){
// 步骤3：输出当前节点，并将其入栈
printnode(root);
stack.push(root);
// 步骤4：置当前结点的左孩子为当前节点
// 返回步骤1
root = root.getleftnode();
}else{
// 步骤5：出栈栈顶结点
root = stack.pop();
// 步骤6：置当前结点的右孩子为当前节点
root = root.getrightnode();
// 返回步骤1
}
}
}
示意图
5.3.2 中序遍历
- 简介
示意图
- 递归实现
/**
* 方式：递归
*/
public void inorder(node root){
// 1. 判断二叉树结点是否为空；若是，则返回空操作
if(root ==null)
return;
// 2. 遍历左子树
inorder(root.getleftnode());
// 3. 访问根节点（显示根结点）
printnode(root);
// 4. 遍历右子树
inorder(root.getrightnode());
}
示意图
- 非递归实现
主要采用 栈实现
流程图
/**
* 方式：非递归（栈实现）
*/
public static void inorder_stack(node root){
stack stack = new stack();
// 1. 直到当前结点为空 & 栈空时，循环结束
while(root != null || stack.size()>0){
// 2. 判断当前结点是否为空
// a. 若不为空，执行3、4
// b. 若为空，执行5、6
if(root != null){
// 3. 入栈当前结点
stack.push(root);
// 4. 置当前结点的左孩子为当前节点
// 返回步骤1
root = root.getleftnode();
}else{
// 5. 出栈栈顶结点
root = stack.pop();
// 6. 输出当前节点
printnode(root);
// 7. 置当前结点的右孩子为当前节点
root = root.getrightnode();
// 返回步骤1
}
}
5.3.3 后序遍历
- 简介
示意图
- 递归实现
/**
* 方式：递归
*/
public void postorder(node root){
// 1. 判断二叉树结点是否为空；若是，则返回空操作
if(root ==null)
return;
// 2. 遍历左子树
postorder(root.getleftnode());
// 3. 遍历右子树
postorder(root.getrightnode());
// 4. 访问根节点（显示根结点）
printnode(root);
}
示意图
- 非递归实现
主要采用 栈实现
示意图
/**
* 方式：非递归（栈实现）
*/
public void postorder_stack(node root){
stack stack = new stack();
stack output = new stack();
// 步骤1：直到当前结点为空 & 栈空时，循环结束——> 步骤8
while(root != null || stack.size()>0){
// 步骤2：判断当前结点是否为空
// a. 若不为空，执行3、4
// b. 若为空，执行5、6
if(root != null){
// 步骤3：入栈当前结点到中间栈
output.push(root);
// 步骤4：入栈当前结点到普通栈
stack.push(root);
// 步骤4：置当前结点的右孩子为当前节点
// 返回步骤1
root = root.getrightnode();
}else{
// 步骤5：出栈栈顶结点
root = stack.pop();
// 步骤6：置当前结点的右孩子为当前节点
root = root.getleftnode();
// 返回步骤1
}
}
// 步骤8：输出中间栈的结点
while(output.size()>0){
printnode(output.pop());
}
}
示意图
5.3.4 层序遍历
- 简介
示意图
- 实现思路
非递归实现，采用 队列
示意图
-
算法流程图
示意图
/**
* 方式：非递归（采用队列）
*/
public void leveltravel(node root){
// 创建队列
queue q=new linkedlist();
// 1. 判断当前结点是否为空；若是，则返回空操作
if(root==null)
return;
// 2. 入队当前结点
q.add(root);
// 3. 判断当前队列是否为空，若为空则跳出循环
while(!q.isempty()){
// 4. 出队队首元素
root = q.poll();
// 5. 输出 出队元素
printnode(root);
// 6. 若出队元素有左孩子，则入队其左孩子
if(root.getleftnode()!=null) q.add(root.getleftnode());
// 7. 若出队元素有右孩子，则入队其右孩子
if(root.getrightnode()!=null) q.add(root.getrightnode());
}
}
示意图
5.4 遍历方式总结
示意图
- 上述讲解的是基础的二叉树
- 根据不同的需求场景，二叉树分为许多类型，主要有：
示意图
- 下面，我将详细讲解各种二叉树的类型
6.1 线索二叉树
- 简介
示意图
-
示意图
示意图
-
特别注意
- 问：如何区别该指针 = 指向左（右）孩子 or 前驱（后继）
- 答：增设标志域：ltag 和 rtag
示意图
6.2 二叉排序树
也称：二叉查找树、二叉搜索树
-
特点
示意图
-
作用 & 应用场景
示意图
6.3 平衡二叉排序树（avl树）
属于 二叉搜索树的一种特殊类型
- 特点
示意图
- 具体介绍
示意图
6.4 红黑树
属于 二叉搜索树的一种特殊类型
示意图
6.5 赫夫曼树
- 简介
示意图
- 哈夫曼树算法
即，如何找出哈弗曼树。具体算法请看下图
算法描述
示意图
更加详细请看文章：http://www.cnblogs.com/mcgrady/p/3329825.html
- 哈夫曼编码
示意图
更加详细请看文章：http://blog.csdn.net/lfeng_coding/article/details/47782141
6.6 其他类型（特殊形态）
包括：斜树、满二叉树 & 完全二叉树
示意图
6.7 总结
示意图