12月23日总结

今日学习了二叉树的相关操作：
一、遍历操作
深度优先遍历：
前序遍历（根 - 左 - 右）：
递归实现：从根节点开始，首先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。示例代码如下（以 C 语言为例）：
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

void preorderTraversal(TreeNode* root) {
if (root == NULL) return;
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}

非递归实现：借助栈来模拟递归过程。先将根节点入栈，然后循环执行以下操作：出栈一个节点并访问它，接着先将其右子节点入栈（如果存在），再将其左子节点入栈（如果存在），如此往复，直到栈为空。示例代码：
void preorderTraversalNonRecursive(TreeNode* root) {
if (root == NULL) return;
struct TreeNode* stack[100]; // 假设栈足够大
int top = -1;
stack[++top] = root;
while (top >= 0) {
TreeNode* node = stack[top--];
printf("%d ", node->val);
if (node->right!= NULL) stack[++top] = node->right;
if (node->left!= NULL) stack[++top] = node->left;
}
}

中序遍历（左 - 根 - 右）：
递归实现：先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。代码示例：
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}

非递归实现：同样利用栈，从根节点开始，不断将当前节点的左子节点入栈，直到左子节点为空，此时出栈一个节点并访问它，然后将当前节点指向它的右子节点，重复上述过程。示例：
void inorderTraversalNonRecursive(TreeNode* root) {
if (root == NULL) return;
struct TreeNode* stack[100]; // 假设栈足够大
int top = -1;
TreeNode* current = root;
while (current!= NULL || top >= 0) {
while (current!= NULL) {
stack[++top] = current;
current = current->left;
}
current = stack[top--];
printf("%d ", current->val);
current = current->right;
}
}

后序遍历（左 - 右 - 根）：
递归实现：先递归地对左子树进行后序遍历，然后对右子树进行后序遍历，最后访问根节点。代码如下：
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}

非递归实现：较为复杂，一种常见方法是使用两个栈。第一个栈用于辅助遍历，第二个栈用于存储最终的后序遍历结果。先将根节点入第一个栈，然后循环：出栈一个节点，将其入第二个栈，接着先将其左子节点（如果存在）入第一个栈，再将其右子节点（如果存在）入第一个栈。最后依次出第二个栈的节点并访问，即为后序遍历结果。示例：
void postorderTraversalNonRecursive(TreeNode* root) {
if (root == NULL) return;
struct TreeNode* stack1[100]; // 假设栈足够大
struct TreeNode* stack2[100]; // 假设栈足够大
int top1 = -1, top2 = -1;
stack1[++top1] = root;
while (top1 >= 0) {
TreeNode* node = stack1[top1--];
stack2[++top2] = node;
if (node->left!= NULL) stack1[++top1] = node->left;
if (node->left!= NULL) stack1[++top1] = node->right;
}
while (top2 >= 0) {
printf("%d ", stack2[top2--]);
}
}

广度优先遍历（层序遍历）：借助队列实现，首先将根节点入队，然后循环执行以下操作：出队一个节点并访问它，接着将其左子节点（如果存在）入队，再将其右子节点（如果存在）入队，如此循环，直到队列为空，即可按层序遍历二叉树。示例代码：
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) return;
struct TreeNode* queue[100]; // 假设队列足够大
int front = 0, rear = 0;
queue[rear++] = root;
while (front < rear) {
TreeNode* node = queue[front++];
printf("%d ", node->val);
if (node->left!= NULL) queue[rear++] = node->left;
if (node->left!= NULL) queue[rear++] = node->left;
}
}

二、构建操作
递归构建：给定一个节点值序列，按照特定的遍历规则（如前序遍历）来构建二叉树。示例代码：
int index = 0;
TreeNode* buildTree(int* preorder, int preorderLen, int* inorder, int inorderLen) {
if (preorderLen == 0 || inorderLen == 0) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[index];
int inorderRootIndex = 0;
for (int i = 0; i < inorderLen; i++) {
if (inorder[i] == root->val) {
inorderRootIndex = i;
break;
}
}
index++;
root->left = buildTree(preorder, inorderRootIndex, inorder, inorderRootIndex);
root->left = buildTree(preorder + inorderRootIndex + 1, preorderLen - inorderRootIndex - 1, inorder + inorderRootIndex + 1, inorderLen - inorderRootIndex - 1);
return root;
}

非递归构建：常结合栈等数据结构辅助，模拟递归过程，例如根据前序遍历序列构建二叉树，先将第一个节点作为根节点入栈，然后依次处理后续节点，根据节点值与栈顶节点值的关系确定新节点的位置（是栈顶节点的左子节点还是右子节点），过程中要注意指针操作的正确性。
三、插入操作（以二叉搜索树为例）
依据二叉搜索树的特性，即左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。插入新节点时，从根节点开始，比较待插入节点值与当前节点值：
若待插入节点值小于当前节点值，且当前节点的左子节点为空，则将新节点插入为当前节点的左子节点；若左子节点不为空，则继续在左子树中寻找插入位置。
若待插入节点值大于当前节点值，且当前节点的右子节点为空，则将新节点插入为当前节点的右子节点；若右子节点不为空，则继续在右子树中寻找插入位置。
示例代码：
void insert(TreeNode** root, int val) {
if (root == NULL) {
root = (TreeNode)malloc(sizeof(TreeNode));
(root)->val = val;
(root)->left = NULL;
(root)->right = NULL;
return;
}
TreeNode* current = root;
while (true) {
if (val < current->val) {
if (current->left == NULL) {
current->left = (TreeNode)malloc(sizeof(TreeNode));
current->left->val = val;
current->left->left = NULL;
current->left->right = NULL;
return;
}
current = current->left;
} else {
if (current->right == NULL) {
current->right = (TreeNode*)malloc(sizeof(TreeNode));
current->right->val = val;
current->right->left = NULL;
current->right->right = NULL;
return;
}
current = current->right;
}
}
}

四、删除操作（以二叉搜索树为例）
删除节点时，需要考虑多种情况：
删除叶子节点：直接将其父节点指向该叶子节点的指针置为空，然后释放该叶子节点的内存。
删除仅有一个子节点的节点：将其父节点指向该节点的指针指向该节点的子节点，然后释放被删节点的内存。
删除有两个子节点的节点：一般采用替换法，找到该节点右子树中的最小值节点（即最左下节点），将其值替换要删除节点的值，然后删除这个最小值节点（它一定是叶子节点或仅有一个子节点的节点，按照前面的方法处理）。
示例代码：
TreeNode* findMin(TreeNode* node) {
while (node->left!= NULL) {
node = node->left;
}
return node;
}

void deleteNode(TreeNode** root, int val) {
if (root == NULL) return;
if (val < (root)->val) {
deleteNode(&(root)->left, val);
} else if (val > (root)->val) {
deleteNode(&(root)->right, val);
} else {
if ((root)->left == NULL) {
TreeNode* temp = root;
root = (root)->right;
free(temp);
} else if ((root)->right == NULL) {
TreeNode* temp = root;
root = (root)->left;
free(temp);
} else {
TreeNode minNode = findMin((root)->right);
(root)->val = minNode->val;
deleteNode(&(*root)->right, minNode->val);
}
}
}

五、查找操作（以二叉搜索树为例）
利用二叉搜索树的有序结构，从根节点开始：
若目标节点值等于当前节点值，则找到目标，返回当前节点。
若目标节点值小于当前节点值，则在左子树中继续查找。
若目标节点值大于当前节点值，则在右子树中继续查找。
示例代码：
TreeNode* search(TreeNode* root, int val) {
if (root == NULL) return NULL;
if (val == root->val) return root;
if (val < root->val) return search(root->left, val);
return search(root->val, val);
}

二叉树的这些操作各有特点与难点，通过不断练习和深入理解，能够熟练掌握并运用它们解决实际问题。