一、前言

数组的搜索比较方便,可以直接用下标,但删除和插入就比较麻烦;

链表与之相反,删除和插入元素很快,但查找比较慢;

此时,二叉树应运而生,二叉树既有链表的好处,也有数组的好处,在处理大批量的动态数据时比较好用,是一种折中的选择。

文件系统和数据库系统一般都是采用树(特别是B树)的数据结构数据,主要为排序和检索的效率。

二叉树是一种最基本最典型的排序树,用于教学和研究树的特性,本身很少在实际中进行应用,因为缺点太明显,就像冒泡排序一样,因为效率问题并不实用,但也是我们必须会的。

二、二叉树缺点

1、顺序存储可能会浪费空间(在非完全二叉树的时候),但是读取某个指定的结点的时候效率比较高O(0);

2、链式存储相对于二叉树,浪费空间较少,但是读取某个结点的时候效率偏低O(nlogn)。

三、遍历与结点删除

二叉树是一种非常重要的数据结构,非常多的数据结构都是基于二叉树的基础演变而来的。对于二叉树有深度遍历和广度遍历,深度遍历有前序、中序以及后序三种遍历方法,广度遍历即我们寻常所说的层次遍历。由于树的定义本身就是递归定义,因此采用递归的方法实现树的三种遍历。

对于一段代码来说,可读性有时候要比代码本身的效率要重要的多。

1、四种基本的遍历思想

* 前序遍历:根结点 -->左子树-->右子树;
* 中序遍历:左子树 -->根结点-->右子树;
* 后续遍历:左子树 -->右子树-->根结点;
* 层次遍历:仅仅需按成次遍历即可;
2、自定义二叉树

3、代码实现
package dataStructure.tree; public class BinaryTreeTest { public static void
main(String[] args) { //创建一个二叉树 BinaryTree binaryTree = new BinaryTree();
//创建结点 HeroNode root = new HeroNode(1, "宋江"); HeroNode node2 = new HeroNode(2,
"卢俊义"); HeroNode node3 = new HeroNode(3, "吴用"); HeroNode node4 = new
HeroNode(4, "公孙胜"); HeroNode node5 = new HeroNode(5, "关胜");
root.setLeft(node2); root.setRight(node3); node3.setLeft(node4);
node3.setRight(node5); binaryTree.setRoot(root); System.out.println("前序遍历");
binaryTree.preOrder(); System.out.println("中序遍历"); binaryTree.midOrder();
System.out.println("后序遍历"); binaryTree.postOrder(); binaryTree.delNode(3);
System.out.println("删除结点3,前序遍历"); binaryTree.preOrder(); } } //定义BinaryTree 二叉树
class BinaryTree { private HeroNode root; public HeroNode getRoot() { return
root; } public void setRoot(HeroNode 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("二叉树为空,无法遍历"); } } //删除结点 public void delNode(int no) {
if(root != null) { //如果只有一个root结点, 这里立即判断root是不是就是要删除结点 if(root.getNo() == no)
{ root = null; } else { //递归删除 root.delNode(no); } }else{
System.out.println("空树,不能删除~"); } } } //先创建HeroNode 结点 class HeroNode { private
int no; private String name; private HeroNode left; //默认null private HeroNode
right; //默认null public HeroNode(int no, String name) { this.no = no; this.name
= name; } public int getNo() { return no; } public void setNo(int no) { this.no
= no; } public String getName() { return name; } public void setName(String
name) { this.name = name; } public HeroNode getLeft() { return left; } public
void setLeft(HeroNode left) { this.left = left; } public HeroNode getRight() {
return right; } public void setRight(HeroNode right) { this.right = right; }
@Override public String toString() { return "HeroNode [no=" + no + ", name=" +
name + "]"; } //前序遍历 public void preOrder() { System.out.println(this);//先输出父节点
//递归向左子树前序遍历 if(this.left != null) { this.left.preOrder(); } //递归向右子树前序遍历
if(this.right != null) { this.right.preOrder(); } } //中序遍历 public void
midOrder() { //递归向左子树中序遍历 if(this.left != null) { this.left.midOrder(); }
System.out.println(this);//输出父节点 //递归向右子树前序遍历 if(this.right != null) {
this.right.midOrder(); } } //后序遍历 public void postOrder() { //递归向左子树后序遍历
if(this.left != null) { this.left.postOrder(); } //递归向右子树前序遍历 if(this.right !=
null) { this.right.postOrder(); } System.out.println(this);//输出父节点 } //递归删除结点
//1.如果删除的节点是叶子节点,则删除该节点 //2.如果删除的节点是非叶子节点,则删除该子树 public void delNode(int no) {
//思路 /* * 1. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点. 2.
如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除) 3.
如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除) 4.
如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除 5. 如果第4步也没有删除结点,则应当向右子树进行递归删除. */ //2.
如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除) if(this.left !=
null && this.left.no == no) { this.left = null; return; }
//3.如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
if(this.right != null && this.right.no == no) { this.right = null; return; }
//4.我们就需要向左子树进行递归删除 if(this.left != null) { this.left.delNode(no); }
//5.则应当向右子树进行递归删除 if(this.right != null) { this.right.delNode(no); } } }
4、控制台输出

技术
©2019-2020 Toolsou All rights reserved,
vue的v-if与v-show的区别C语言控制台小游戏,打砖块用C++跟你聊聊“原型模式” (复制/拷贝构造函数)身价530亿美元!世界首富前妻再嫁化学老师:承诺捐赠一半财富关于过年ESP8266/ESP32 系统篇: 优化系统启动时间java简单的抽奖算法,抽奖Demo比特币站上5.2万美元 美团CEO王兴:理论上中本聪已经是世界首富了连 CEO 都不香了?这些互联网大佬接连辞任比尔·盖茨:疫情后彻底恢复正常可能要到2022年末