Tree

Source: tree/

---

二叉树

节点定义（tree/binary_tree.h）：

C++

typedef struct node {
    int data;
    struct node *lchild, *rchild;
} *BTREE;

遍历

方式	顺序	函数
前序遍历	根 → 左 → 右	PreOrderTraverse(BTREE&)
中序遍历	左 → 根 → 右	Inorder(BTREE&)
后序遍历	左 → 右 → 根	Posorder(BTREE&)
层序遍历	逐层从左到右	见 Traversal - BFS

二叉搜索树的中序遍历结果为递增序列。

祖先查询

C++

void Ancestor(BTREE tree, int item);  // 输出节点 item 的所有祖先节点

序列化与反序列化

将二叉树转换为字符串表示，再还原为树结构，常用于持久化或网络传输。

LeetCode

• leetcode 236: 二叉树两结点的最近公共祖先