uhome

菜单

Administrator
Administrator
发布于 2024-10-23 / 9 阅读
0

遍历二叉树和线索二叉树

#数据结构

遍历二叉树

如何按照某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次。

先序遍历

若二叉树为空，则空操作；否则

  1. 访问根结点
  2. 先序遍历左子树
  3. 先序遍历右子树

递归实现

void preorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    std::cout << root->val << " "; // 访问根节点
    preorderTraversal(root->left);  // 访问左子树
    preorderTraversal(root->right); // 访问右子树
}}

迭代实现

void preorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> stack;
    stack.push(root);

    while (!stack.empty()) {
        TreeNode* current = stack.top();
        stack.pop();
        std::cout << current->val << " ";  // 访问根节点

        if (current->right != nullptr) {
            stack.push(current->right); // 先压右子树
        }
        if (current->left != nullptr) {
            stack.push(current->left);  // 再压左子树
        }
    }
}

前缀表示即波兰式，后缀表示即逆波兰式。

中序遍历

若二叉树为空，则空操作；否则

  1. 中序遍历左子树
  2. 访问根结点
  3. 中序遍历右子树

递归实现

void inorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    inorderTraversal(root->left);  // 访问左子树
    std::cout << root->val << " "; // 访问根节点
    inorderTraversal(root->right); // 访问右子树
}

迭代实现

void inorderTraversalIterative(TreeNode* root) {
    std::stack<TreeNode*> stack;
    TreeNode* current = root;

    while (current != nullptr || !stack.empty()) {
        while (current != nullptr) {
            stack.push(current);
            current = current->left;  // 访问左子树
        }
        current = stack.top();
        stack.pop();
        std::cout << current->val << " ";  // 访问根节点
        current = current->right;  // 访问右子树
    }
}

后序遍历

若二叉树为空，则空操作；否则

  1. 后序遍历左子树
  2. 后序遍历右子树
  3. 访问根结点

递归实现

void postorderTraversal(TreeNode* root) {
    if (root == nullptr) return;
    postorderTraversal(root->left);  // 访问左子树
    postorderTraversal(root->right); // 访问右子树
    std::cout << root->val << " ";   // 访问根节点
}

迭代实现

void postorderTraversalIterative(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> stack1, stack2;
    stack1.push(root);

    while (!stack1.empty()) {
        TreeNode* current = stack1.top();
        stack1.pop();
        stack2.push(current);

        if (current->left != nullptr) {
            stack1.push(current->left);  // 左子树先入栈
        }
        if (current->right != nullptr) {
            stack1.push(current->right); // 右子树再入栈
        }
    }

    while (!stack2.empty()) {
        TreeNode* current = stack2.top();
        stack2.pop();
        std::cout << current->val << " ";  // 逆序访问节点
    }
}

void postorderTraversalIterativeSingleStack(TreeNode* root) {
    if (root == nullptr) return;
    std::stack<TreeNode*> stack;
    TreeNode* current = root;
    TreeNode* lastVisited = nullptr;

    while (current != nullptr || !stack.empty()) {
        if (current != nullptr) {
            stack.push(current);
            current = current->left;  // 访问左子树
        } else {
            TreeNode* topNode = stack.top();
            if (topNode->right != nullptr && lastVisited != topNode->right) {
                current = topNode->right;  // 访问右子树
            } else {
                std::cout << topNode->val << " ";  // 访问根节点
                stack.pop();
                lastVisited = topNode;
            }
        }
    }
}

总结

按任意次序进行遍历，对含n个结点的二叉树，其时间复杂度均为O(n)。所需辅助空间为遍历过程中栈的最大容量，即树的深度，最坏情况下空间复杂度为O(n)。

线索二叉树

线索二叉树（Threaded Binary Tree）是一种特殊的二叉树结构，通过利用二叉树中原本为空的左、右子节点指针来指向该节点的前驱或后继节点，从而方便树的遍历。

每个节点除了保存数据、左指针和右指针外，增加了两个标志位，用来区分指针的用途：

  • ltag：标识左指针是普通子节点指针（值为0）还是线索指针（值为1）。
  • rtag：标识右指针是普通子节点指针（值为0）还是线索指针（值为1）。

线索：指向结点的前驱或后继的指针。

根据使用的线索类型，线索二叉树可以分为以下几种类型：

  • 前序线索二叉树：线索指向前序遍历中的前驱和后继节点。
  • 中序线索二叉树：线索指向中序遍历中的前驱和后继节点（最常见的形式）。
  • 后序线索二叉树：线索指向后序遍历中的前驱和后继节点。

中序线索二叉树

定义节点结构（C++ 示例）

struct ThreadedTreeNode {
    int val;
    ThreadedTreeNode* left;
    ThreadedTreeNode* right;
    bool ltag;  // ltag == 0 表示左子树，ltag == 1 表示前驱线索
    bool rtag;  // rtag == 0 表示右子树，rtag == 1 表示后继线索
    ThreadedTreeNode(int x) : val(x), left(nullptr), right(nullptr), ltag(0), rtag(0) {}
};

中序线索化的代码

ThreadedTreeNode* pre = nullptr;  // 全局前驱指针

// 线索化中序遍历
void inorderThreading(ThreadedTreeNode* root) {
    if (root == nullptr) return;

    // 线索化左子树
    inorderThreading(root->left);

    // 处理当前节点
    if (root->left == nullptr) {
        root->left = pre;
        root->ltag = 1;  // 左指针为线索
    }
    if (pre != nullptr && pre->right == nullptr) {
        pre->right = root;
        pre->rtag = 1;  // 右指针为线索
    }
    pre = root;  // 更新前驱节点

    // 线索化右子树
    inorderThreading(root->right);
}

中序线索二叉树的遍历

void inorderTraverseThreaded(TreeNode* root) {
    ThreadedTreeNode* current = root;

    // 找到中序遍历的第一个节点
    while (current != nullptr && current->ltag == 0) {
        current = current->left;
    }

    // 遍历线索二叉树
    while (current != nullptr) {
        std::cout << current->val << " ";  // 访问当前节点

        // 如果有后继线索，沿线索访问
        if (current->rtag == 1) {
            current = current->right;
        } else {
            // 如果没有后继线索，找到右子树的最左节点
            current = current->right;
            while (current != nullptr && current->ltag == 0) {
                current = current->left;
            }
        }
    }
}
排序算法