Day45 #二叉树的价值和基础概念#
二叉树是典型的非线性数据结构，在实际中，有很多逻辑关系并不是简单的线性关系，常常存在一对多，甚至多对多的情况。比如我们家庭成员之间的关系、企业中职级关系。因此需要像二叉树这种非线性数据结构来表示。
优点 : 在平衡的情况下可以保证对二叉树的查找和插入都是O(logn)的时间复杂度
缺点 : 二叉树有可能不平衡；在存储结构上 , 顺序存储可能会浪费空间(在非完全二叉树的时候)，但是读取某个指定的节点的时候效率比较高O(n)；链式存储相对二叉树比较大的时候浪费空间较少，但是读取某个指定节点的时候效率偏低O(nlogn)
二叉树定义 : 二叉树（binary tree）是指树中节点的子树数目不大于2的有序树，它是一种最简单且最重要的树。递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。
二叉树的结构画出来就像一个倒着的树。
在这颗树上，每片树叶都长在一个节点上，这个节点就叫做叶子的父节点，该叶子就叫做父节点的孩子节点，孩子节点又分左右孩子节点；没有父节点的节点叫根节点；没有孩子节点的节点称之为叶子节点；
子树是包含了一个节点及该节点下所有节点的二叉树。
访问：即是访问二叉树中的某个节点
遍历：是对二叉树的一种基本运算，所谓遍历，就是按一定的规则和顺序走遍二叉树上的各个节点，使每个节点都被访问一次且只访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。
树的结构从根节点到叶子节点可以分为不同的层级，同一层级上由同个父节点衍生出来的两个节点为兄弟节点。
关键码指节点的值。
抄星友的
网友评论