二叉树查找中序遍历前驱结点

根据二叉树中序遍历的性质，一个节点的前驱结点是其左子树中最右侧的节点。因此，我们可以按照以下步骤查找一个节点的前驱结点：

1. 如果该节点有左子树，则前驱结点为其左子树中最右侧的节点，即左子树中最大的节点。
2. 如果该节点没有左子树，则需要向上查找其祖先节点，直到找到一个节点是其父节点的右子节点，那么该节点的父节点就是该节点的前驱结点。

下面是一个递归实现的示例代码：

def predecessor(root, p):
    if not root:
        return None
    
    # 如果 p 有左子树，则前驱结点为其左子树中最右侧的节点
    if p.left:
        node = p.left
        while node.right:
            node = node.right
        return node
    
    # 如果 p 没有左子树，则需要向上查找其祖先节点
    # 直到找到一个节点是其父节点的右子节点，那么该节点的父节点就是该节点的前驱结点
    pre = None
    while root != p:
        if p.val < root.val:
            root = root.left
        else:
            pre = root
            root = root.right
    return pre

相关问题

c语言利用非递归遍历对二叉树的中序遍历，求某个结点的双亲节点； 求某个结点的前驱和后继； 求某个结点的兄弟结点；

**非递归中序遍历查找父节点：**
中序遍历遵循“左-根-右”的顺序，如果我们要找到某节点的父节点，当我们在遍历时遇到目标节点的值，而之前访问的是其左子树，那么当前节点就是该目标节点的父节点。因为中序遍历会先访问左子节点，所以在找到目标节点前的最后一个访问节点就是父节点。

struct TreeNode *findParent(struct TreeNode *root, int target) {
    if (!root || root->val == target) return NULL; // 根节点或目标节点为NULL时返回
    if (root->val < target) { // 目标在右子树
        return findParent(root->right, target);
    } else { // 目标在左子树
        return root;
    }
}

**查找前驱和后继节点：**
- 前驱节点（predecessor）：在一个有序的二叉搜索树中，小于目标节点的最大节点。
- 后继节点（successor）：大于目标节点的最小节点。

struct TreeNode *findPredecessorSuccessor(struct TreeNode *root, int target) {
    struct TreeNode *prev = NULL, *next = NULL;
    
    // 中序遍历找到前驱节点
    while (root) {
        if (root->val > target) {
            next = root;
            root = root->left;
        } else {
            prev = root;
            root = root->right;
        }
    }
    if (prev) return prev; // 如果找到，返回前驱
    if (next) return next->left; // 若找不到前驱，返回target的后继

    // 后续同理，只需交换左右子树即可
    while (root) {
        if (root->val < target) {
            next = root;
            root = root->right;
        } else {
            prev = root;
            root = root->left;
        }
    }
    if (prev) return prev->right;
    return NULL; // 如果找不到后继，返回NULL
}

**查找兄弟节点：**
兄弟节点是指与给定节点在同一父节点下的其他节点。非递归查找需借助辅助栈。

struct TreeNode *findBrotherNode(struct TreeNode *root, struct TreeNode *node) {
    stack.push(root);
    while (!stack.empty()) {
        struct TreeNode *temp = stack.top();
        stack.pop();
        if (temp == node) {
            if (temp->left) return temp->left;
            if (temp->right) return temp->right;
            // 如果父节点不是空，那么兄弟节点在父节点的另一个孩子上
            if (!stack.empty())
                return stack.top()->left ? stack.top()->left : stack.top()->right;
        }
        if (temp->right) stack.push(temp->right);
        if (temp->left) stack.push(temp->left);
    }
    return NULL; // 如果未找到兄弟节点，返回NULL
}

：构造一棵线索二叉树，中序遍历并输出二叉树的每个结点。写一个完整c语言代码

在C语言中，构建一棵线索二叉树并进行中序遍历的过程可以分为以下几个步骤：

1. **构造线索二叉树**[^1]：
线索二叉树通过在节点结构中添加额外指针（通常称为前驱和后继指针），使得遍历更容易。这里以二叉搜索树为例，假设有一个`struct TreeNode`定义如下：

   typedef struct TreeNode {
       int val;
       struct TreeNode* left;
       struct TreeNode* right;
       struct TreeNode* prev;
       struct TreeNode* next; // 前驱和后继指针
   } TreeNode;

2. **插入结点**：
当插入新结点时，不仅更新常规的左右子节点，还要设置线索，保证线索的正确性。

3. **中序遍历**：
- 中序遍历是按照"左->根->右"的顺序访问节点，对于线索二叉树，可以通过当前节点的`prev`和`next`指针来方便地找到左孩子和右孩子。

   void inorderTraversal(TreeNode* root) {
       if (root == NULL) return;
       inorderTraversal(root->left);
       printf("%d ", root->val); // 输出结点值
       inorderTraversal(root->right);
   }

完整的C语言代码示例：

// 创建新节点
TreeNode* createNode(int val) {
    TreeNode* node = malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

// 插入结点到线索二叉树
void insertIntoTree(TreeNode** root, int val) {
    TreeNode* newNode = createNode(val);

    if (*root == NULL) {
        *root = newNode;
        newNode->prev = newNode->next = NULL;
    } else if (val < (*root)->val) {
        newNode->prev = (*root)->prev;
        newNode->next = (*root);
        if ((*root)->prev != NULL) (*root)->prev->next = newNode;
        (*root)->prev = newNode;
    } else {
        newNode->prev = (*root);
        newNode->next = (*root)->right;
        if ((*root)->right != NULL) (*root)->right->prev = newNode;
        (*root)->right = newNode;
    }
}

// 中序遍历线索二叉树
void inorderTraversal(TreeNode* root) {
    inorderTraversal(root->left);
    printf("%d ", root->val); // 输出结点值
    inorderTraversal(root->right);
}

运行`inorderTraversal(*root)`即可完成中序遍历并打印二叉树的每个结点值。