BinaryTree二叉树

二叉树(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

二叉查找树

如果左子树不为空,则左子树所有节点的值都下雨根节点的值。 如果右子树不为空,则右子树所有节点的值均大于根节点的值。 左右子树都是二叉查找树。

二叉树遍历

二叉树是典型的非线性数据结构,遍历时需要把非线性关联的节点转成一个线性的序列。

前序遍历

输出顺序是根节点,左子树,右子树。

中序遍历

输出顺序是左子树,根节点,右子树

后序遍历

输出顺序是左子树,右子树,根节点

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券