树

标签： ... 结点 称为 geq 二叉树 n2

树的定义

1. 树的构造性递归定义：一个结点X组成的集合{X}是一棵树，这个结点X称为这棵树的根(root)。假设X是一个结点，T₁,T₂,...,T_k是k棵互不相交的树，可以构造一棵新树：令X为根，并有k条边由X指向树T₁,T₂,...,T_k。这些边也叫做分支，T₁,T₂,...,T_k称作根为X的树之子树(SubTree)。
2. 直观定义：(1) 除根以外，其余结点都有入度。 (2) 层次结构

树与二叉树的基本术语

1. 树的逻辑结构特点:

   • 除根结点之外, 每棵子树的根结点有且仅有一个直接前驱, 但可以有0个或多个直接后继
   • 即一对多的关系, 反映了结点之间的层次关系

2. 基本术语:

   • 结点的度：结点所具有的子树的个数。
   • 树的度：树中各结点度的最大值。
   • 叶子结点：度为0的结点，也称为终端结点
   • 分支结点：度不为0的结点，也称为非终端结点。
   • 结点的孩子、双亲：树中某结点子树的根结点称为这个结点的孩子结点（子结点、儿子），这个结点称为它孩子结点的双亲结点（父结点）
   • 兄弟：具有同一个双亲的孩子结点互称为兄弟。
   • 祖先、子孙：在树中，如果有一条路径从结点x到结点y，那么x就称为y的祖先，而y称为x的子孙。
   • 路(径)和路(径)长度：如果树的结点序列n₁,n₂, ... ,n_k有如下关系：结点n_i是n_i+1的双亲(1\(\leq\;\)i<k)，则把n₁,n₂, ... ,n_k称为一条由n₁至n_k的路径：路径上经过的边的个数称为路径长度。
   • 结点的层数：根结点的层数为1，对其余任何结点，若某结点在第k层，则其孩子结点在第k+1层。
   • 树的深度：树中所有结点的最大层数，也称高度。
   • 有序树、无序树：如果一棵树中结点的各子树从左到右是有次序的，称这棵树为有序树：反之，称为无序树。
   • 森林：m(m$\geq$0)棵互不相交的树的集合。

3. 二叉树的定义：

   • 二叉树是一个n(n$\geq$0)个结点的有限集合，该集合或者为空(为空二叉树)；或者是由一个根结点和两棵互不相交的、分别称为左子树和右子树的二叉树组成。

4. 二叉树的性质

   • 在二叉树的第i层上至多有2^i-1个结点(i$\geq$1)
   • 深度为k的二叉树至多有2^k-1个结点(k$\geq$1)，最少有k个结点。
     (1) 深度为k且具有2^k-1个结点的二叉树一定是满二叉树。
     (2) 深度为k且具有k个结点的二叉树不一定是满二叉树。
   • 对任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则有:n₀=n₂+1，而与度数为1的结点数n₁无关。(1) 分支数=结点总数-1 -> n-1=n₁+2n₂ (2) n=n₀+n₁+n₂ 由(1)(2)得证:n₀=n₂+1
   • 具有n(n$\geq$0)个结点的完全二叉树的高度为 log₂(n+1) 向上取整。

5. 完全（满）二叉树的性质

   • 完全二叉树的顺序存储结构：如果把一棵完全二叉树的具有n个结点自顶向下，同一层自左向右连续编号：1,2, ... ,n，且使该编号对应于数组的下标，即编号为i(1 $\leq$ i $\leq$ n)的结点存储在下标为i的数组单元中，则这种存储表示方法称为完全（满）二叉树的顺序存储结构。

   • 完全二叉树的顺序存储结构的性质

     (1) 若i = 1，则i是根结点，无父结点

     (2) 若i > 1，则i的父结点为 i/2 向下取整

     (3) 若2*i $\leq$n，则i有左儿子且为2*i；否则，i无左儿子

     (4) 若2*i+1 $\leq$n，则i有右儿子且为2*i+1；否则，i无右儿子

     (5) 若i为偶数，且i < n，则有右兄弟，且为i+1。

遍历

1. 分类

   先序、中序、后序、层序

2. 已知先序、中序，可唯一确定二叉树

3. 作业：完全二叉树用数组存放（按层存储），已知前序、中序，完成构造二叉树的算法。

标签：,...,结点,称为,geq,二叉树,n2
From： https://www.cnblogs.com/vireally/p/17368415.html