一、二叉树相关理论1.1二叉树定义为树中节点度在二以下的有序树。 一棵空树或一个节点树，也叫二叉树，二叉树的左右子树也各不相同。
1.2基本分类包括二叉树和完全二叉树。
1.2.1二叉树是存在于所有非叶节点中，只存在左右部分树的二叉树。
图1二叉树1.2.2完全二叉树是除末层非叶节点外存在，且只存在左右子树，末层叶节点由左至右紧密排列，右边连续缺少若干节点的二叉树
图2完全二叉树1.3的性质(二叉树的第I层至多有(i0 )个节点
性质2 )最大深度为h的二叉树中至多有一个节点
性质3 )只要任意一棵二叉树上有n0个叶节点，n1个度为2的节点，就一定有n0==n1 1
性质4 :具有n个节点的完全二叉树的最大深度是
性质5 )对于n个节点，完全二叉树从上到下，从左到右从1-i开始编号。 如果根节点为1，父节点为parent，左节点为left，右子节点为right，则具有以下公式。
(1)父节点满足：
)2)子节点满足：
1.4二叉树在逻辑上是非线性结构，但在存储时可以按照连续排列存储，也可以使用链表。 本文主要说明以排列结构进行收纳。 遍历二叉树时有四种方式：前相遍历、中相遍历、后相遍历、分层遍历。
其中遍历划分主要根据父节点的访问顺序划分，如下所示为各遍历方式的示意图。
如图3所示，3个6节点的完全二叉树1.4.1的遍历是6个节点的完全二叉树。 与编号1-6的节点对应的不重复的关键词分别是ABCDEF。 最初扫描的顺序是先扫描父节点parent，再扫描左子节点left，再扫描右子节点right，即扫描顺序。
parent —— left —— right
图3的第一次扫描输出结果是A B D E C F
具体应用请参考博主的这篇博文。 https://blog.csdn.net/naibozhuan 3744/article/details/121708034
1.4.2中顺序扫描中顺序扫描首先扫描左子节点left，然后扫描父节点parent，最后扫描右子节点right。
left ——部件—— right
图3的最初的扫描输出结果是D B E A F C
中顺序扫描一般适用于二叉搜索数，二叉搜索树的顺序输出是规则数组。
1.4.3前后遍历先是遍历左子节点left，遍历右子节点right，最后遍历父节点parent，也就是遍历顺序。
left ——右——零件
图3最初的扫描输出结果是D E B F C A
反向遍历通常用于运算符树。 也就是说，如图4所示，非叶节点是符号位，叶节点是数字位。
图4算术运算二叉树可以通过对图4进行中顺序扫描来恢复公式，通过进行后顺序扫描来计算公式。
1.4.4分层遍历级别的遍历顺序可以按从左到右、从上到下的顺序访问各个节点，并采用排队方式进行遍历。 顺序如下。
parent—— left —— right
图3的第一次扫描输出结果是A B C D E F
分层遍历可以看作是按顺序遍历收纳二叉树的整个数组。
1.5寻找二叉树的二叉树搜索要素有深度优先搜索(DFS )和广度优先搜索(BFS )，深度优先搜索一般采用递归方式进行； 另一方面，宽度优先搜索一般采用队列方式。