数据结构简单入门/复习（四）-树与二叉树的知识介绍（C语言）

MWHLS • 2020/08/05 am11:24 • C, 数据结构, 计算机语言

已阅： 14

在栈与队列树与二叉树这两个章节之前还有串和数组与广义表，但字符串与数组的基本使用并没有值得注意的，因此跳过。
这部分介绍树与二叉树的知识点，各种实现代码将在后续章节补充。
2022/1/23：更新为 Markdown 格式，修复挂的图，修改图对应描述以适应新格式。

树的定义

二叉树的定义、性质

二叉树的遍历

树的定义

下图便是一种树，A是树的根，树的编号按层序遍历编号。

一棵非空树中，（1）有且只有一个根(root)（2）除根结点外的其他结点可以组成多个互不相见的树，被称为根的子树。

树的结点：包含一个数据元素及若干指向其子树的分支。
结点的度：结点拥有的子树个数。
叶子/终端结点：度为零，即没有子树。
非终端节点/分支结点：度不为零。
树的度：取树内各结点的度的最大值。
孩子/孩子结点：结点的子树的根，即子树中与结点相邻的结点。
双亲/父结点：上述关系（孩子结点）的颠倒。
兄弟/兄弟结点：拥有同一个父结点的结点。
祖先：父结点的父结点的父结点的...结点。
子孙：孩子结点的孩子结点的孩子结点的...结点。

结点的层次：树的根为第一次，其孩子为第二层...
深度：取树中结点层次的最大值。
有序树：子树有序，不可交换。
无序树：子树无序，可以交换。
森林：多棵不相交树的集合。

二叉树的定义、性质

二叉树是一种特殊的树，每个结点最多只有两棵子树，且子树有左右之分，是有序树。

性质1：在二叉树的第i层至多有2^(i-1)个结点（i>=1）。
性质2：深度为k的二叉树至多有(2^k)-1个结点（k>=1）。
性质3：对于任何一棵二叉树T，若其叶子/终端结点数为N，度为2的结点数为M，啧N=M+1。
性质4：具有n个结点的完全二叉树的深度为 (log2 n)+1，log2 n向下取整。
性质5：对一棵n个结点的完全二叉树的结点按层序编号，则对任意结点i（1<=i<=n），有：
(1)若 i=1，则 i 是二叉树的根，若 i>1，则双亲是是 i/2，向下取整。
(2)若 2i>n，则结点 i 无孩子结点（是叶子），相反，则其左孩子是结点 2i。
(3)若 2i + 1 > n，则结点i无右孩子，相反，其右孩子是结点 2i+1。