打牢地基-二叉树、BST

章节

tree结构简介

二叉树详解

二分搜索树 - Binary Search Tree

1 tree结构简介

tree-简介

tree-高效性

2 二叉树详解

重新认识下tree

二叉树的天然递归属性

一个节点有n个分叉- n叉树

满二叉树

定义:除了叶子节点，每个节点都有两个孩子节点

二叉树不一定是满二叉树

3 二分搜索树 - Binary Search Tree

二分搜索树-BTS 加速查询过程的原因，假如根节点val = 28, 现在在查找 30 这个元素，因为BTS的存储特性，只需要查找右子树部分就可以了，大大提高了查询的速度有个细节，需要保证node的val 是可比较的，这是有局限性的

3.1 定义树中节点-struct

节点结构体中 包含数据域 e, 左子树引用 left， 右子树引用right

3.2 定义BTS

一棵树包包含一个根节点root，以及node的个数 size

3.3 add(e)-递归新增一个节点数据

3.4 contains- 递归查询树中是否包含某个数据

3.5 二分搜索树的遍历

3.5.1 前序遍历 - 递归

3.5.2 中序遍历-递归

3.5.3 后序遍历 post_order - 递归

3.5.4 前序遍历 - 非递归算法(栈的应用)- DFS 深度优先遍历

LinkedListStack-使用先前实现的链表栈

3.5.5 二分搜索树的层序遍历-(队列的应用) BFS (Breadth First Search)

LinkedListQueue-使用先前实现的链表队列实现层序遍历

编程的过程中会发现其实每一个节点都会被访问3次。