二叉树的理解、遍历、逆推

二叉树：一个节点上最多有2个子节点

• 复杂二叉树
• 前序：A BEF CGH 解析：ABC的前序ABC，B的前序BEF，C的前序CGH
• 中序：EBF A GCH 解析：ABC的中序BAC，B的中序EBF，C的中序GCH
• 后序：EFB GHC A 解析：ABC的后序BCA，B的中序EFB，C的中序GHC

二叉树的遍历

tip：无子树时往上遍历

1. 前序遍历二叉树：ATBZXCYF
   • 解析：（跟左右）A(A的左子树为T(T无左子树，T的右子树为(B(B的左子树为Z，无右子树)))，A右子树为X(X左子树为C(C左子树为Y(无左子树，无右子树))，X右子树为F(无左子树，无右子树)))
   • 规律：跟左右，依次往下找每个节点的前序
2. 中序遍历二叉树：TZBACYXF
   • 解析：（左跟右）T(T无左子树，T的右子树为B(B的左子树为Z(Z无左子树，Z无右子树，紧接着往上为B)))A(跟节点) X(X左子树为C(C无左子树，C右子树为Y(Y无左子树，Y无右子树，紧接着往上为C))，X右子树为F)
   • 规律：左跟右，依次往下找每个节点的中序
3. 后序遍历二叉树：ZBTYCFXA
   • 解析：(跟左右)T(T无左子树，T右子树为B(B左子树为Z，B无右子树，紧接着往上找为B，紧接着往上找为T))X(X左子树为C(C无左子树，C右子树为Y，紧接着往上找为C)，X右子树为F，紧接着往上找为X)A
   • 规律：左右跟，依次往下找每个节点的后序

逆推二叉树 1

2