二叉树的度和遍历方式

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

二叉树的度 #

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

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

什么叫前序、后序、中序 #

一棵二叉树由根结点、左子树和右子树三部分组成，若规定 D、L、R 分别代表遍历根结点、遍历左子树、遍历右子树，则二叉树的遍历方式有 6 种：DLR、DRL、LDR、LRD、RDL、RLD，由于先遍历左子树和先遍历右子树在算法设计上没有本质区别，所以，只讨论三种方式：

• DLR–前序遍历（根在前，从左往右，一棵树的根永远在左子树前面，左子树又永远在右子树前面 ）
• LDR–中序遍历（根在中，从左往右，一棵树的左子树永远在根前面，根永远在右子树前面）
• LRD–后序遍历（根在后，从左往右，一棵树的左子树永远在右子树前面，右子树永远在根前面）

什么叫层序 #

一棵二叉树由按层，从上到下，从左到右进行遍历。