目录
1，二叉树的介绍
【数据结构|数据结构-二叉树（一 链式存储）（Java版）】1.1，树的定义
1.2，概念解释
2，二叉树
2.1，二叉树的特点
2.2，二叉树的性质
2.3，斜树
2.4，满二叉树
2.5，完全二叉树
3，二叉树的实现
3.1，二叉树的节点类型
3.2，二叉树遍历操作（递归实现）
3.2.1，前序遍历递归实现
3.2.2，中序遍历递归实现
3.2.3，后序遍历递归实现
3.3，二叉树的遍历操作（非递归实现）
3.3.1，前序遍历非递归实现
3.3.2，中序遍历非递归实现
3.3.3，后序遍历非递归实现
3.4，二叉树的层次遍历实现
3.5，二叉树的查找算法（递归实现）
3.5.1，前序查找递归实现
3.5.2，中序查找非递归实现
3.5.3，后续查找递归实现
3.6，二叉树中删除一个节点
3.7，定义一颗二叉树
4，测试代码
1，二叉树的介绍 在介绍二叉树的概念之前，我们先来看看什么是树。
1.1，树的定义 树（Tree）是n（n>=0)个结点的有限集。n=0时称为空树。在任意一颗非空树中：
- 有且仅有一个特定的称为根（Root）的结点；
- 当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1、T2、......、Tn，其中每一个集合本身又是一棵树，并且称为根的子树。
- n>0时根结点是唯一的，不可能存在多个根结点，数据结构中的树只能有一个根结点。
- m>0时，子树的个数没有限制，但它们一定是互不相交的。
文章图片
1.2，概念解释 针对树的定义，现在我们来看一些关于树的概念。
- 节点的度：结点拥有的子树数目称为结点的度。看下面图片，每个节点拥有子节点的个数就是本节点度的大小。
文章图片
- 节点之间的关系
- 节点的层次
文章图片
- 树的深度
2，二叉树 了解了上面树的基本概念之后，下面我们来看看树的一种特殊情况，树中每一个节点的度最大是2的这种特殊的树，二叉树。二叉树的节点有左右之分。
2.1，二叉树的特点
- 由二叉树定义以及图示分析得出二叉树有以下特点：
- 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
- 左子树和右子树是有顺序的，次序不能任意颠倒。
- 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
- 在二叉树的第
文章图片
层上最多有
文章图片
个节点 。（i>=1） - 二叉树中如果深度为k,那么最多有
文章图片
个节点(也就是二叉树是一棵完全二叉树的情况）。(k>=1） - n0=n2+1， n0表示度数为0的节点数，n2表示度数为2的节点数。
- 在完全二叉树中，具有n个节点的完全二叉树的深度为[
文章图片
]+1，其中[log2n]是向下取整。 - 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：
- 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
- 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
- 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
文章图片
2.4，满二叉树 满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
- 满二叉树的特点有：
- 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
- 非叶子结点的度一定是2。
- 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
文章图片
2.5，完全二叉树 完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。
文章图片
- 特点：
- 叶子结点只能出现在最下层和次下层。
- 最下层的叶子结点集中在树的左部。
- 倒数第二层若存在叶子结点，一定在右部连续位置。
- 如果结点度为1，则该结点只有左孩子，即没有右子树。
- 同样结点数目的二叉树，完全二叉树深度最小。
- 注：满二叉树一定是完全二叉树，但反过来不一定成立。
3.1，二叉树的节点类型
class TreeNode{
private int data;
private TreeNode left;
private TreeNode right;
public TreeNode(int data) {
this.data = https://www.it610.com/article/data;
}public int getData() {
return data;
}public TreeNode getLeft() {
return left;
}public TreeNode getRight() {
return right;
}public void setLeft(TreeNode left) {
this.left = left;
}public void setRight(TreeNode right) {
this.right = right;
}@Override
public String toString() {
return"TreeNode{" +
"data="https://www.it610.com/article/+ data +'}';
}
}3.2，二叉树遍历操作（递归实现） 3.2.1，前序遍历递归实现
前序遍历: 先输出父节点，再遍历左子树和右子树，在递归遍历左子树和右子树的时候需要判断节点是否是空，否则会报空指针异常。
/**
* 二叉树的前序遍历递归实现
*/
public void preOrder(){
//前序遍历，先输出节点值，在递归左右子树
System.out.println(this.getData());
//判断左边节点是否是空，如果不空就递归遍历
if(this.left != null){
this.left.preOrder();
}
//判断右孩子是否是空
if(this.right != null){
this.right.preOrder();
}
}3.2.2，中序遍历递归实现
中遍历：先遍历左子树，再输出父节点，再遍历右子树。（同样需要判断左右孩子是否是空，否则发生空指针异常）
/**
* 二叉树中序遍历递归实现
*/
public void midOrder(){
//判断左边节点是否是空，如果不空就递归遍历
if(this.left != null){
this.left.midOrder();
}
System.out.println(this.getData());
if(this.right != null){
this.right.midOrder();
}
}3.2.3，后序遍历递归实现
后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点。
/**
* 后序遍历递归实现
*/
public void postOrder(){//判断左边节点是否是空，如果不空就递归遍历
if(this.left != null){
this.left.postOrder();
}
if(this.right != null){
this.right.postOrder();
}
System.out.println(this.getData());
}小结：递归的实现，主要看输出父节点的顺序，在递归的过程中，每一个节点都有三次机会被访问到，第一次访问到并且直接输出，那就是前序遍历，第二次访问到输出的话就是中序遍历，第三次访问到并且输出的话就是后续遍历。
3.3，二叉树的遍历操作（非递归实现） 二叉树的非递归遍历实现需要借助一个栈来实现。
3.3.1，前序遍历非递归实现
- 二叉树前序非递归遍历实现过程
- 如果二叉树非空，先把根节点入栈，如果是空直接返回。
- 如果栈不空，先抛出栈顶元素，并且访问栈顶的元素。
- 如果当前栈顶元素的左右子树都不空，那么先把右子树压入栈，在把左子树压入栈。注意：应为栈是先进后出的原则，所以在这里要先把右子树入栈，然后左子树在入栈。
- 循环抛出栈顶元素，直到栈为空为止。
- 代码实现
public void preOrderNonRec(){
if(this.root == null)
return ;
//也就是二叉树不空
Stack stack=new Stack();
//先把根节点入栈
stack.push(this.root);
while (!stack.isEmpty()){
//如果栈不空，就一直循环
TreeNode treeNode=(TreeNode)stack.pop();
System.out.println(treeNode.getData());
//如果当前节点的左右节点都不空，那么全部入栈，因为栈是先进后出原则
//所以前续遍历的时候，先入右子树，在入左子树
if(treeNode.getRight()!= null){
stack.push(treeNode.getRight());
}
if(treeNode.getLeft() != null){
stack.push(treeNode.getLeft());
}}
}3.3.2，中序遍历非递归实现
- 二叉树中序遍历非递归过程：
- 如果二叉树左子树非空，循环遍历左子树直到空为止。
- 抛出栈顶元素并且访问栈顶元素。
- 如果当前节点右子树非空，那么右子树入栈。
- 循环访问直到栈空为止。
- 如果二叉树左子树非空，循环遍历左子树直到空为止。
- 代码实现：
public void midOrderNonRec(){
if(this.root == null)
return;
Stackstack=new Stack();
TreeNode treeNode=this.root;
//先一直走到最左边的节点
stack.push(this.root);
while (!stack.isEmpty()){
while (treeNode.getLeft() != null){
stack.push(treeNode.getLeft());
treeNode=treeNode.getLeft();
}
//退出循环，说明已经走到最左边的节点。抛出节点开始打印
treeNode=stack.pop();
System.out.println(treeNode.getData());
if(treeNode.getRight() != null){
stack.push(treeNode.getRight());
treeNode=treeNode.getRight();
}}
} 3.3.3，后序遍历非递归实现
二叉树后续非递归遍历过程：对二叉树后续的非递归遍历，可以观察到和先续遍历相反，所以仿照先续遍历，先访问左子树，在访问右子树，把访问到的元素全部入栈，最后抛出栈即可。
- 二叉树后序非递归遍历 过程
- 如果二叉树非空，先把根节点入栈。
- 如果栈不空，先抛出栈顶元素，并且把元素入栈。
- 如果当前栈顶元素的左右子树都部空，那么先把左子树压入栈，在把右子树压入栈。
- 循环抛出栈顶元素，直到栈为空为止。
- 如果二叉树非空，先把根节点入栈。
//后续非递归遍历
public void postOrderNonRec(){
if(this.root == null)
return ;
//也就是二叉树不空
Stack stack=new Stack();
Stack stack1=new Stack();
//先把根节点入栈
stack.push(this.root);
while (!stack.isEmpty()){
//如果栈不空，就一直循环
TreeNode treeNode=(TreeNode)stack.pop();
stack1.push(treeNode.getData());
//如果当前节点的左右节点都不空，那么全部入栈，因为栈是先进后出原则
//所以中续遍历的时候，先入左子树，在入右子树
if(treeNode.getLeft()!= null){
stack.push(treeNode.getLeft());
}
if(treeNode.getRight() != null){
stack.push(treeNode.getRight());
}
}
while (!stack1.isEmpty()){
System.out.println(stack1.pop());
}
}3.4，二叉树的层次遍历实现 二叉树的层次遍历需要借助队列来实现
//二叉树的层次遍历
public void levelOrder(){
TreeNode treeNode=this.root;
Queue queue=new LinkedList();
queue.add(this.root);
while (!queue.isEmpty()){
TreeNode treeNode1=queue.remove();
System.out.print(treeNode1.getData()+" ");
if(treeNode1.getLeft() != null){
queue.add(treeNode1.getLeft());
}
if(treeNode1.getRight()!= null){
queue.add(treeNode1.getRight());
}
}
}
3.5，二叉树的查找算法（递归实现） 3.5.1，前序查找递归实现
- 前序查找思路
- 首先判断当前节点是否是要查找的节点。
- 如果是当前查找的节点，就直接返回当前节点。
- 如果不是当前查找的节点，就判断当前节点的左子树是否是空，如果不空，则递归前序查找左子树。
- 如果左递归前序查找，找到该节点，就返回，否则继续判断当前节点的右子节点是否是空，如果不空，则继续向右递归查找。
- 代码实现：
/**
* 前序遍历查找算法
* @param value 待查找的值
* @return 查找成功就返回，否则就返回null
*/
public TreeNode preOrderSearch(int value){
//首先判断当前节点值是否等于value
if(this.getData() == value){
return this;
}
//递归遍历左子树
TreeNode treeNode=null;
if(this.left !=null){
treeNode=this.left.preOrderSearch(value);
}
if(treeNode != null){
return treeNode;
}
//左子树没有找到就递归遍历右子树
if(this.right != null){
treeNode=this.right.preOrderSearch(value);
}
return treeNode;
}3.5.2，中序查找非递归实现
- 查找思路
- 判断当前节点的左节点是否是空，如果不为空，就递归查找左子树。
- 如果在左子树中找到，就返回，如果没有找到，就和当前节点进行比较，如果是就返回当前节点，否则就继续向右进行递归查找。
- 如果右递归查找到，就返回，否则返回null。
- 代码实现：
/**
* 中序查找算法
* @param value 待查找的值
* @return 查找成功返回节点，否则返回null
*/
public TreeNode midOrderSearch(int value){
//首先向左递归查找
TreeNode treeNode=null;
if(this.left != null){
treeNode=this.left.midOrderSearch(value);
}
//如果查找到就返回
if(treeNode != null){
return treeNode;
}
//如果左子树中没有找到，就比价当前节点
if(this.getData() == value){
return this;
}
//递归在右子树上面查找
if(this.right != null){
treeNode=this.right.midOrderSearch(value);
}
return treeNode;
}
3.5.3，后续查找递归实现
- 查找思路：
- 判断当前节点的左子节点是否是空，如果不为空，则递归后续查找。
- 如果找到，就返回节点，如果没有找到，就判断当前节点的右节点是否是空，如果不为空，则右递归进行后续查找，如果找到就返回。
- 如果左子树和右子树都没有找到，就和当前节点进行比较，如果是查找到的元素就返回，不是就返回null。
- 代码实现：
/**
* 后续查找算法
* @param value 待查找的值
* @return 查找成功返回节点，否则返回Null
*/
public TreeNode postOrderSearch(int value){
TreeNode treeNode=null;
//递归在左子树上面查找
if(this.left != null){
treeNode=this.left.postOrderSearch(value);
}
//如果在左子树上面查找到就返回节点
if(treeNode != null){
return treeNode;
}
//递归在右子树上面查找
if(this.right != null){
treeNode=this.right.postOrderSearch(value);
}
//如果在右子树上面查找到，就直接返回
if(treeNode != null){
return treeNode;
}
//如果在左右子树上都没有查找到，就判断当前节点值
if(this.getData() == value)
return this;
return treeNode;
}
3.6，二叉树中删除一个节点
- 删除条件：
- 如果删除的是叶子节点，就直接进行删除。
- 如果删除的是非叶子节点，就直接删除其子树，因为如果删除的是非叶子节点，需要涉及节点的调整问题，所以在这里就直接删除子树，在后面的avl树或者排序树会做具体非叶子节点的删除和调整。
- 代码实现：
/**
* 递归删除二叉树中的节点
* @param value 需要删除的节点的值
* @return 删除成功返回1，否则返回-1
*/
public int deleteNodeInBt(int value){
if(this.root != null){
//首先判断根节点是否是要删除的节点
if(this.root.getData() == value){
this.root = null;
return 1;
}else {
//也就是根节点不是要删除的节点
return this.root.deleteNode(value);
}}else {
System.out.println("二叉树是空，不可删除！");
return -1;
}
}3.7，定义一颗二叉树 注意，上面的代码是二叉树的节点类型，删除，插入，遍历的具体实现在节点类型的类中实现。下面这段代码才是二叉树的实现。
//定义一颗二叉树
class BinaryTree{
//二叉树的跟节点
private TreeNode root;
public void setRoot(TreeNode root) {
this.root = root;
}
//前序遍历
public void preOrder(){
if(this.root!=null){
this.root.preOrder();
}else {
System.out.println("当前二叉树欸你空");
}
}
//中序遍历
public void midOrder(){
if(this.root != null){
this.root.midOrder();
}else {
System.out.println("当前二叉树为空");
}
}
//后序遍历
public void postOrder(){
if(this.root != null){
this.root.postOrder();
}else {
System.out.println("当前二叉树为空");
}
}
/**
* 前序遍历查找算法
* @param value 待查找的值
* @return 查找成功返回该节点，否则返回null
*/
public TreeNode preOrderSear(int value){
//判断当前树是否是空，空就直接返回
if(this.root != null){
return this.root.preOrderSearch(value);
}else {
return null;
}
}
public TreeNode midOrderSear(int value){
if(this.root != null){
return this.root.midOrderSearch(value);
}else {
return null;
}
}
public TreeNode postOrderSear(int value){
if(this.root != null){
return this.root.postOrderSearch(value);
}else {
return null;
}
}/**
* 递归删除二叉树中的节点
* @param value 需要删除的节点的值
* @return 删除成功返回1，否则返回-1
*/
public int deleteNodeInBt(int value){
if(this.root != null){
//首先判断根节点是否是要删除的节点
if(this.root.getData() == value){
this.root = null;
return 1;
}else {
//也就是根节点不是要删除的节点
return this.root.deleteNode(value);
}}else {
System.out.println("二叉树是空，不可删除！");
return -1;
}
}
}
4，测试代码
public class BinaryTreeDemo {
public static void main(String[] args) {
BinaryTree binaryTree=new BinaryTree();
TreeNode root=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);
root.setLeft(node2);
root.setRight(node3);
node2.setLeft(node4);
node2.setRight(node5);
node3.setLeft(node6);
node3.setRight(node7);
binaryTree.setRoot(root);
//前序遍历
//binaryTree.preOrder();
// binaryTree.preOrderNonRec();
//binaryTree.midOrderNonRec();
//binaryTree.postOrderNonRec();
//二叉树的层次遍历
// binaryTree.levelOrder();
//HashMap hashMap=new HashMap();
//二叉树的前序查找算法
//TreeNode treeNode= binaryTree.preOrderSear(6);
//TreeNode treeNode1=binaryTree.midOrderSear(6);
//TreeNode treeNode2=binaryTree.postOrderSear(77);
//System.out.println(treeNode2);
binaryTree.deleteNodeInBt(6);
binaryTree.preOrder();
}
}推荐阅读
- 算法计算经典|二叉树知识点最详细最全讲解
- Quicksort最坏的情况何时发生（）
- 堆排序实际上在哪里使用（）
- 哪一种排序算法的内存写操作最少（）
- 用大于或等于m的数求和n的不同方法
- 矩阵的不同运算快速介绍
- 用C++ STL复制的不同方法std::copy()、copy_n()、copy_if()、copy_backward()
- Java中的TreeMap、HashMap和LinkedHashMap之间的区别
- #yyds干货盘点# 数据结构与算法学习——单链表相关算法