树与二叉树
2023-08-20 14:53:04
发布于：河北
3阅读
0回复
0点赞
树：
定义：
度（树有几个直系“儿子”）：
节点拥有的子树的数量为节点的度，度为0的节点为叶子结点，度不为0(有儿子)的的节点为分支节点，树的度定义为树的所有节点中度的最大值。
表示法：
双亲表示法（父亲表示法）
孩子表示法
二叉树：
定义：
二叉树(Binary Tree，简称BT)是一种度数最大为2的树形结构，即二叉树的的每个结点最多有两个子节点，每个节点的子节点严格区分左节点和有节点，它的两棵子树称为左子树，右子树。
满二叉树：
若某一二叉树“子孙满堂”，即除叶子结点外，其他节点均为2，且每一层的结点总数达最大值，这种特殊形态的二叉树，叫满二叉树。
完全二叉树：
最后一层靠左侧连续，且其它层节点满，是完全二叉树。
储存：
顺序存储法（完全二叉树）：
DataType tree[N];
tree[i]是tree[2*i]和tree[2*i+1]的父节点
tree[2*i]是tree[i]的左孩子结点
tree[2*i+1]是ree[i]的右孩子结点
链式储存法：
struct Node
{
DataType data;//数据块
int father;//指向父节点的游标
int left,right;//指向左右孩子的游标
};
Node tree[N];
tree[i].left = idx1;
tree[i].right = idx2;
tree[idx1].father = i;
tree[idx2].father = 1;
二叉树的遍历：
先序遍历（根左右）：
以根(A)为分界，分成左右两部分(B,C)。先分左边,根(B)分两部分(D,E),再分右边,根(C)分两部分(F,G)。
中序遍历（左根右）
后序遍历（左右根）
总结：
1）树的基本概念，以及遍历的方式 【了解】
（1）定义
（2）基本术语 【概念掌握】
结点，度，一棵树的度
双亲，孩子
子孙，祖宗
分支节点（内部结点，非终端结点），叶子节点（终端结点）
深度，高度，层次
有序树，无序树
（3）树结构遍历（前，后）
（4）线性结构与树结构对比
2）二叉树基本概念与亲子表示法建立二叉树
（1）定义以及五种形态
（2）二叉树与度为 2 的有序树的区别
（3）特殊的一些二叉树
斜树
满二叉树 与 完全二叉树
（4）二叉树基本性质（ 5 大性质 ）
{
性质一：在二叉树的第i层上最多有2^i-1个节点(i>=1)。第一层最多1个节点，第二层最多2个节点，第三层最多4个节点。
性质二：深度为k的二叉树至多有2^k-1个节点(k>=1)。
性质三：任意一棵二叉树，若其叶子结点（度为1的节点）的数量为n((下标)0)，度为2的节点数量为n((下标)2)，则：n((下标)0)与n((下标)2)一定满足：n((下标)0)=n((下标)2)+1。
性质四：具有n(n>=0)个结点的完全二叉树的深度为[log(下标)2(n)]。设：[]表示向下取整。
性质五(针对完全二叉树)：若将有n个节点的完全二叉树自顶向下，同一层自左向右连续给结点编号,2，...，n则：
{
1.若结点编号i=1，则结点i为根，无父节点；
2.若i>1，则i的父节点编号为i/2；
3.针对编号为i的节点：
{
3.1其左
}
}
}
（5）完全二叉树前提下，根节点若编号为 1，结点编号 i 是编号 2*i 和 2*i+1
3）二叉树的存储（仅仅展示）
顺序存储 【二叉堆的选择，小数据时】
链式存储 【普通二叉树优先选择，本章主讲】
4）二叉树的遍历（前，中，后）***
（1）遍历过程阐述
图示模拟
（2）推导遍历结果
两种遍历确定唯一二叉树
前中求 后
练习：选择题（有素材）选择题
（3）构建一棵二叉树
（4）递归代码：前序遍历
（5）递归代码：中序遍历
（6）递归代码：后续遍历
这里空空如也
有帮助，赞一个