二叉树(binary tree),是每个结点最多有2个的有序树(tree) 。 简单的理解,就是一种类似于我们生活中树的结构,只不过每个结点上都最多只能有两个子结点。顶上的叫根结点,两边被称作“左子树”(left child)和“右子树”(right child)
一个二叉树所有非叶子节点都存在左右子树,并且所有的叶子节点都在同一层级上
链式存储 每个节点包含三个部分,存储数据的data变量,指向左孩子的left指针,指向右孩子的right指针
class Node {
private Object data;
private Node left;
private Node right;
}
数组存储 按照层级顺序把二叉树的节点放到数组对应的位置上,如果某一个节点的左孩子或右孩子空缺,则数组对应的位置也空出来。 父节点的下标是parent,那么它的左孩子节点下标是2parent+1;右孩子节点下标是就是2parnet+2
如果左子树不为空,则左子树所有节点的值都下雨根节点的值。 如果右子树不为空,则右子树所有节点的值均大于根节点的值。 左右子树都是二叉查找树。
二叉树是典型的非线性数据结构,遍历时需要把非线性关联的节点转成一个线性的序列。
输出顺序是根节点,左子树,右子树。
输出顺序是左子树,根节点,右子树
输出顺序是左子树,右子树,根节点