文章目录
基本术语
结点：数据元素 若干指向子树的分支
结点的度：分支的个数
树的度：树中所有结点的度的最大值
叶子结点：度为零的结点
分支结点：度大于零的结点
路径：从根到该结点所经过的分支和结点
孩子结点：结点的子树的根
双亲结点：上一层的直系结点
结点的层次：根节点的层次为1，第L层的结点的子树的根节点的层次为L 1
树的深度：树中叶子结点的最大层次
森林：m(m>=0)棵互不相交的树的集合
树：任何一棵非空树是一个二元组Tree=（root,F），其中，root称为根结点，F是子树森林
二叉树
二叉树或为空树；或是由一个根结点加上两棵分别被称为左子树和右子树的、互不相交的二叉树组成。
二叉树的性质：
- 在二叉树的第i层上最多有2^i-1（2的i-1次方）个结点（i>=1）
- 深度为k的二叉树上最多含有2^k - 1（2的k次方减一）个结点
- 对任何一棵二叉树，若它含有n0个叶子结点，n2个度为2的结点，则必然存在关系式：n0 = n2 1
满二叉树与完全二叉树
满二叉树：深度为K且含有2^K - 1个结点的二叉树
完全二叉树：树中所含的结点与满二叉树的结点编号一一对应
- 具有n个结点的完全二叉树的深度为 (log2n) 1
- 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：
(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 i/2 的结点为其双亲结点
(2) 若 2i>n，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i 1>n，则该结点无右孩子结点， 否则，编号为2i 1 的结点为其右孩子结点
二叉树的存储（略）
顺序存储（略）
链式存储（略）
二叉树的遍历
对二叉树而言，可以有以下三种遍历路径：
（1）先上后下的按层次遍历（使用队列）
（2）先左（子树）后右（子树）的遍历
- 先序遍历（使用栈）
- 中序遍历（使用栈）
- 后序遍历（使用栈）
（3）先右（子树）后左（子树）的遍历
先左后右的遍历算法
先（根）序遍历
若二叉树为空树，则空操作，否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
中（根）序遍历
若二叉树为空树，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
后（根）序遍历
若二叉树为空树，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
先序、中序、后序遍历的非递归实现
先序遍历非递归：
中序遍历非递归：
后序遍历非递归：
层次遍历非递归：
void BinaryTreeLevelOrder(BTNode* root)
{
Queue q;
//树为空，直接返回
if (root == NULL)
{
return;
}
QueueInit(&q);
//先将根节点入队
QueuePush(&q, root);
while (QueueEmpty(&q))
{
//出队保存队头并访问
BTNode* front = QueueFront(&q);
printf("%c", front->_data);
QueuePop(&q);
//将出队结点的左子树根入队
if (front->_left)
QueuePush(&q, front->_left);
//将出队结点的右子树根入队
if (front->_right)
QueuePush(&q, front->_right);
}
}
构造二叉树
已知二叉树的先序序列和中序序列可以唯一确定一棵树
已知二叉树的后序序列和中序序列可以唯一确定一棵树
已知二叉树的先序序列和后序序列不可以唯一确定一棵树，因为无法确定左右子树。
来源：https://www./content-4-450201.html
|
