树|树,二叉树(完全二叉树,满二叉树)概念图解满二叉树)概念图解|二叉树(完

1、树的定义
2、树的概念
3、二叉树
4、二叉树遍历
5、满二叉树
6、完全二叉树
总结

1、树的定义树是n个结点的有限集合，有且仅有一个根结点，其余结点可分为m个根结点的子树。

文章图片

2、树的概念

结点的度:一个结点拥有子树的个数称为度。比如A的度为3，C的度为2，H的度为0。度为0的结点称为叶子节点（D,F,G,H）。树的度是树中所有结点的度的最大值，此树的度为3。
树中结点的最大层次成为树的深度或高度。此树的深度为4。
父节点A的子结点B,C,D；B,C,D也是兄弟节点
树的集合称为森林.树和森林之间有着密切的关系.删除一个树的根结点,其所有原来的子树都是树,构成森林.用一个结点连接到森林的所有树的根结点就构成树.

3、二叉树二叉树是每个节点最多拥有两个子节点，左子树和右子树是有顺序的不能任意颠倒。

文章图片

4、二叉树遍历前序遍历（前根遍历）：根——>左——>右
中序遍历（中根遍历）：左——>根——>右
后序遍历（后根遍历）：左——>右——>根
已知前序和中序，求后序问题，前序 ABDGCEFH中序 DGBAECHF
解法：根据前序、中序综合判断画出树的节点图，然后再写后序遍历：DGBEHFCA
（前序和中序的子树也满足前序或中序的规则）

文章图片

二叉树的深度优先遍历（DFS）与广度优先遍历（BFS）
DFS深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。利用数据结构“栈”，父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点。
DFS:ABDGCEFH
BFS广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。利用数据结构“队列”，父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点。
BFS：ABCDGEFH

5、满二叉树 【树|树,二叉树(完全二叉树,满二叉树)概念图解】高度为h，由2^h-1个节点构成的二叉树称为满二叉树。