必会编程基础知识：二叉树

今日知识点：二叉树

全文字数： 772

阅读时间：5分钟

什么是二叉树？

二叉树是每个结点最多有两个子树的树结构。如果一个节点有3个子树，就不能称之为二叉树。例如下图b的二叉树，A的左子树是T B Z部分，它的右子树是X这一部分，而X的左子树又是C Y这部分，右子树就是P，这就是二叉数。

二叉树的特点

1. 非空二叉树只有一个根结点

2. 每一个结点最多有两颗子树，且分别被称为该结点的左子树和右子树

二叉树的基本性质

性质1：在二叉树的第k层上，最多有2k-1（k>=1）个结点。

性质2：深度为m的二叉树最多有2m-1个结点。21-1+22-1+…+2m-1=2m-1

性质3：在任意一颗二叉树中，度为0的结点（即叶子结点）总是比度为2的结点多一个。 n0=n2+1

性质4：具有n个结点的二叉树，其深度至少为[log2n]+1。其中[log2n]表示取log2n的整数部分

满二叉树

除最后一层外，每一层上的所有结点都有两个子结点，如下图所示。

完全二叉树

除最后一层外，每一层上的结点数达到最大值；在最后一层上只缺少右边若干结点。

注：具有n个结点的完全二叉树的深度为[log2n]+1

二叉树的存储结构

二叉树通常采用链式存储结构。每个结点由数据域和指针域两部分组成。

数据域：用于存放结点中的数据

指针域：又分左指针域、右指针域，分别用于存放左子节点、右子结点的存储地址。

以下图这棵二叉树为例，看一下它的逻辑结构是怎样的。

其中BT指向的是二叉树的头指针。

再来简单看一下，它的物理存储结构是什么样子。i相当于计算机中的存储地址。

二叉树的前序遍历

前序遍历（DLR）根->左->右

若二叉树为空，则结束;否则：

1.访问根节点

2.前序遍历左子树

3.前序遍历右子树

二叉树的中序遍历

中序遍历 （LDR）左->根->右

若二叉树为空，则结束;否则：

1.中序遍历左子树

2.访问根节点

3.中序遍历右子树

二叉树的后序遍历

后序遍历（LRD）左->右->根

若二叉树为空，则结束;否则：

1.后序遍历左子树

2.后序遍历右子树

3.访问根节点

怎么样？是不是其实也不难

二叉树是计算机二级必须会的考点

也是学习编程很重要的基础知识

今天搞定它了吧~

1元团购通关二级、更多编程干货