当前位置：首页 > news >正文

二叉树结构与遍历

news 2025/5/23 11:30:10

一、基本结构

1. 节点定义

二叉树的每个节点包含三个部分：

数据域：存储节点的值（如整数、字符等）。
左子节点指针：指向左子树。
右子节点指针：指向右子树。

C语言中的节点定义如下：

typedef struct BinTreeNode {struct BinTreeNode* left;  // 左子节点struct BinTreeNode* right; // 右子节点int val;                   // 节点值
} BTNode;

2. 树的构建

通过动态分配内存创建新节点：

BTNode* BuyBTNode(int val) {BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));newnode->val = val;newnode->left = NULL;newnode->right = NULL;return newnode;
}

二、遍历方式

遍历的核心思想：递归分解问题，将树拆分为根节点、左子树、右子树，并按特定顺序访问。

1. 前序遍历（PreOrder）

遍历顺序：根节点 -> 左子树 -> 右子树

逻辑流程

第一步：访问当前树的根节点。
第二步：将左子树视为新的子树，递归调用自身处理。
第三步：将右子树视为新的子树，递归调用自身处理。

void PreOrder(BTNode* root) {if (root == NULL) {printf(" N"); // 空节点标记为Nreturn;}printf(" %d", root->val); // 1. 访问根PreOrder(root->left);     // 2. 遍历左子树PreOrder(root->right);    // 3. 遍历右子树
}

对如下二叉树：

      1/   \2     3/ \   / \N  N N   N

输出：1 2 N N 3 N N

2. 中序遍历（InOrder）

遍历顺序：左子树 -> 根节点 -> 右子树

逻辑流程

第一步：优先递归处理左子树，直到左子树为空。
第二步：回溯到当前根节点并访问。
第三步：递归处理右子树。

代码实现

void InOrder(BTNode* root) {if (root == NULL) {printf(" N");return;}InOrder(root->left);      // 1. 遍历左子树printf(" %d", root->val); // 2. 访问根InOrder(root->right);     // 3. 遍历右子树
}

对上述二叉树，输出：N 2 N 1 N 3 N

3. 后序遍历（PostOrder）

遍历顺序：左子树 -> 右子树 -> 根节点

逻辑流程

第一步：递归处理左子树，直到左子树为空。
第二步：递归处理右子树，直到右子树为空。
第三步：回溯到当前根节点并访问。

void PostOrder(BTNode* root) {if (root == NULL) {printf(" N");return;}PostOrder(root->left);    // 1. 遍历左子树PostOrder(root->right);   // 2. 遍历右子树printf(" %d", root->val); // 3. 访问根
}

对上述二叉树，输出：N N 2 N N 3 1