二叉树概念
2017-09-22 本文已影响179人
程序H
二叉树示意图
A
/ \
B C
/ \ / \
D E F G
二叉树简介
树是一种简单的非线性结构，所以元素之间具有明显的层次特性。
- 每个节点只有一个前件，称为父节点；（B和C的父节点为A)
- 没有前件的节点只有一个，称为根节点，简称根； (A节点为根节点，A没有前件)
- 每个节点可以有多个后节点，称为该节点的子节点； （B和C都为A的子节点）
- 没有后件(子节点)的节点，称为叶子节点； (D、E、F、G均为叶子节点)
- 一个节点拥有的后件个数，称为该节点的度；（A、B、C的度是2，D、E、F、G的度为0）
- 所有节点中最大的度，称为树的度； （A、B、C的度是2， D、E、F、G的度都为0，所以树的度为2）
- 树的最大层次，称为树的深度； (上面的树最大层次是3，所以树的深度是三层)
二叉树的特性
- 非空二叉树只有一个根节点；（A没有父节点，故A为根节点）
- 每个节点最多有两棵子树，且分别称为该节点的左子树和右子树。
二叉树的度可以为0(叶子节点) ，如果叶子节点为1(只有一颗子树)或2(有两棵子树)；
二叉树的性质
在二叉树的第k层上，最多有2^(k - 1)并且（k >= 1）个节点 (第k层共有多少个节点)；
例子：
如上图所示，一共三层，故已知k=3；2^(3-1)= 4；
从上面的示意图可以看出第三层一共4个节点，分别为D、E、F、G；
深度为m的二叉树最多有2^m-1个结点；
例子：
如上图所示，一共三层，故树的深度为3。m=3; 2^3-1 = 7;
从上面的示意图可以看出一共为7个节点。
在任意一个二叉树中，度为0的结点(即叶子节点)总比度为2的结点多一个。
解释：
如上图所示，A、B、C的度均为2，D、E、F、G度为0。
具有n个节点的二叉树，其深度至少为[log2n] + 1个,其中log2n表示取log2n的整数；
解释：
log2n什么意思？笔者写博客的时候也查了下百度，真是愧对当年的数学老师，废话不多说。
log2(n)= x 等价于 2^x=n;
例子：
如上图所示，二叉树一共有7个节点，故n=7。 logn2(7)+1 = 2+1 = 3；注：logn2(7)取整所以为2，不需要四舍五入。再看看上面图，是不是至少为3层？
二叉树及其基本性质
满二叉树：
除最后一层外，每一层上的所有节点都有两个子节点，如下图：
A
/ \
B C
/ \ / \
D E F G
完全二叉树:
除最后一层外，每一层上的节点数都达到最大值；在最后一层上至缺少右边的若干节点，如下图：
A
/ \
B C
/ \ /
D E F
- 设置完全二叉树共有n个节点。如果从根节点开始，按层序（每一层从左至右）用自然数1，2..n给节点编号(k=1, 2, ..n)，有以下结论：
1
/ \
2 3
/ \ /
4 5 6
- 若k=1，则该节点为根节点，它没有父节点；若k>1，该节点的父节点的编号为INT(k/2)，取整。
例子：
如上图，假设k=3 INT(3/2)=1. 假设k=5 INT(5/2)=2。 - 若2k≤n，则编号为k 的结点的左子结点编号为2k;否则该结点无左子结点(也无右子结点)
解释：
n为二叉树的最大节点个数，上图最大节点个数为6。
例子：
如上图，先取2这个节点，k=2，2x2<=6成立，说明2有子节点。 再取4，k=4，2x4<=6不成立，说明4没有子节点。 - 若2k+1<=n，则编号为k的节点的右节点编号为2k+1，否则该节点无右子节点；
例子：
如上图, 先取2这个节点，k=2, 2x2+1<=6成立，得到5，5为2的右节点。 k=3, 2*3+1<=6不成立，所以3节点无右子节点。
二叉树的遍历
二叉树的遍历是指不重复的访问二叉树中的所有节点。
以下为遍历走势图：
1
↙ ↘
2 3
↙ ↘ ↙
4 5 6
前序遍历(DLR)：
若二叉树为空，则结束返回；否则：
- 访问根节点；
- 前序遍历左子树；
- 前序遍历右子树;
遍历顺序为1→2→4→5→3→6
中序遍历(LDR)：
若二叉树为空，则结束返回；否则：
- 中序遍历左子树；
- 访问根节点；
- 中序遍历右子树；
遍历顺序为2→4→5→1→6→3
后序遍历(LRD)：
若二叉树为空，则结束返回；否则：
- 后序遍历左子树；
- 后序遍历右子树；
- 访问根节点；
遍历顺序为4→5→2→1→3→6
