每日一例 | 二叉树数据结构了解下?
共 4080字,需浏览 9分钟
·
2021-05-28 14:02
前言
数据结构是任何编程语言的基础,可以这样说,如果你熟练掌握了各种数据结构,那你就离写出优秀代码不远了。为什么?因为所有的业务逻辑都是基于编程语言构建的模型实现的,而模型又是基于数据结构实现的,数据结构本身是脱离于编程语言的。
之前看到一位大佬分享了他对编程的看法,他觉得一切编程都是建模,网上购物就是对我们传统购物流程建模,社交聊天就是对我们传统的交流方式建模,业务的契合程度,取决于你的建模粒度,你的建模粒度越细化,越贴合实际业务,但同时也越复杂。
废话有点多,简单来说,其实比编程能力更重要的是建模能力,模型建的好,系统效率才能高。
好了,我们回到今天的内容,今天要分享的内容是二叉树的实现,以及二叉树的常用方法实现,算是对数据结构的初探。我们常用的数据结构有表、栈、队列、树、散列、堆等,我们常用的集合都是通过这些实现的,有些会复杂一点,会用到两种数据结构。
二叉树
树的基本数据结构
最基本的树是这样的,它可以有多个节点:
代码实现是这样的:
class TreeNode {
Object element;
TreeNode firstChild;
TreeNode nextSibling;
}
二叉树结构
二叉树是最多只能有两个子节点的树,左边的子节点叫left
节点,右边的子节点叫right
节点:
代码实现:
class BinaryNode<T> {
T element;
BinaryNode<T> left;
BinaryNode<T> right;
public BinaryNode() {
}
public BinaryNode(T element) {
this.element = element;
}
public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
this.element = element;
this.left = left;
this.right = right;
}
@Override
public String toString() {
return "BinaryNode{" +
"element=" + element +
", left=" + left +
", right=" + right +
'}';
}
}
二叉树遍历
二叉树的遍历方式有三种,分别叫先序遍历、中序遍历和后序遍历。
先序遍历就是从上到下,从左到右遍历,即先打印父节点,再打印左节点,再打印右节点。
中序遍历是有左节点先打印左节点,然后依次从左到右遍历,左后打印右节点。
后序遍历是先打印子节点,再打印父节点,顺序也是从左到右。
以下图为例:
中序遍历是这样的:
(a + (b * C)) + (((d * e) + f) * g)
后序遍历是这样的:
a b c * + d e * f + g * +
先序遍历是这样的:
+ + a * b c * + * d e f g
这里分享下中序遍历的实现,这里用到了递归算法,其他的遍历由于时间关系就先不写了
private void printTree(BinaryNode<T> t) {
if (t != null) {
printTree(t.left);
System.out.println(t.element);
printTree(t.right);
}
}
总结
二叉树是算法题中经常要用到的一种数据结构,我还依稀记得去年有一次面试的时候,面试官让我实现一个二叉树的算法,我愣是没写出来,压根就没概念,但是一直到现在,对二叉树也是知之甚少,所以从那时候我就觉得得好好补下数据结构这块的知识了。毕竟欠下的债,终究是要还的,像我们这些非科班出身的小伙伴,更是要好好努力呀,特别是数据结构这一块。没伞的孩子,要努力奔跑呀!
每天早上的时间都很紧张,所以能分享的内容也就不会太多,但是如果你真正去思考每天分享的知识点,应该还是有收获的,至少我感觉是这样的,这种潜移默化的学习和进步,一定会让你越来越优秀,加油吧!
- END -