数据结构二叉树的建立

数据结构中的二叉树是一种非线性数据结构，每个节点最多有两个子节点，通常称为左子节点和右子节点。建立二叉树的过程通常包括以下几个步骤：

1. **创建节点**：首先定义一个二叉树节点类，包含数据（通常是整数、字符等）、指向下一对子节点的引用（左孩子和右孩子）以及一个指向父节点的引用。

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

2. **构造过程**：从根节点开始，可以手动插入元素或递归地创建子节点。如果给定一个有序序列，可以选择中序遍历的方式来构造一个平衡二叉搜索树（如AVL树或红黑树）。

- **递归插入**：对于一个空的树，新节点直接作为根；对于已有节点，根据节点值与目标值的关系决定是在左子树还是右子树中插入。
- **非递归插入**：使用栈来辅助，依次将元素入栈，遇到小于当前栈顶元素时在其左子树插入，大于则在右子树，直到找到合适位置。

3. **构建空树**：如果数据源为空，可以直接创建一个空的根节点。

4. **链式表示**：二叉树可以用链式结构来存储，即每个节点包含指向左右子节点的指针，而不是数组形式。这样更方便插入、删除和遍历操作。