二叉树的度和遍历方式

Posted on Tue, 01 Apr 2025 15:43:11 +0800 by LiangMingJian

二叉树的度 #

二叉树节点的度是指节点的子树个数，二叉树的度指所有节点中度的最大值。

比如下图中 1 号节点的孩子是 2、3、4，则 1 号节点的度数是 3，且 1 号节点的度是最大的，故该树的度为 3。

二叉树的遍历方式 #

一棵二叉树由根结点、左子树和右子树三部分组成，若规定遍历根结点记为（D）、遍历左子树记为（L）、遍历右子树记为（R）。

则二叉树的遍历方式可以分为：

• 前序遍历（DLR）：从根节点开始，从左往右，左子树永远比右子树先遍历。
• 中序遍历（LDR）：从左字树开始，然后根，最后右字树，根节点永远在中间。
• 后序遍历（LRD）：从左字树开始，然后右子树，最后才是根，根节点在最后面。

可以看出，遍历的顺序看的是根节点所在的位置，第一个就是前序，中间就是中序，最后一个就是后序。

什么叫层序遍历 #

一棵二叉树从根节点开始，按层，从上到下，从左到右进行遍历的方式称为层序遍历。