当前位置: 首页> 科技> 数码 > 【408考点之数据结构】二叉树的遍历及线索二叉树

【408考点之数据结构】二叉树的遍历及线索二叉树

时间:2025/7/13 12:05:30来源:https://blog.csdn.net/gygkhd/article/details/139985747 浏览次数:0次

二叉树的遍历及线索二叉树

一、二叉树的遍历

二叉树的遍历是指按照一定的顺序访问二叉树中所有节点。常见的遍历方法有前序遍历(Preorder Traversal)、中序遍历(Inorder Traversal)、后序遍历(Postorder Traversal)和层次遍历(Level Order Traversal)。

  1. 前序遍历(Preorder Traversal)

    • 过程:访问根节点 -> 前序遍历左子树 -> 前序遍历右子树
    • 代码实现
    void preorderTraversal(TreeNode *root) {if (root) {printf("%d ", root->data);preorderTraversal(root->left);preorderTraversal(root->right);}
    }
    
  2. 中序遍历(Inorder Traversal)

    • 过程:中序遍历左子树 -> 访问根节点 -> 中序遍历右子树
    • 代码实现
    void inorderTraversal(TreeNode *root) {if (root) {inorderTraversal(root->left);printf("%d ", root->data);inorderTraversal(root->right);}
    }
    
  3. 后序遍历(Postorder Traversal)

    • 过程:后序遍历左子树 -> 后序遍历右子树 -> 访问根节点
    • 代码实现
    void postorderTraversal(TreeNode *root) {if (root) {postorderTraversal(root->left);postorderTraversal(root->right);printf("%d ", root->data);}
    }
    
  4. 层次遍历(Level Order Traversal)

    • 过程:按照层次从上到下、从左到右依次访问各节点
    • 代码实现
    #include <stdio.h>
    #include <stdlib.h>
    #define MAX_QUEUE_SIZE 100typedef struct TreeNode {int data;struct TreeNode *left;struct TreeNode *right;
    } TreeNode;typedef struct {TreeNode *data[MAX_QUEUE_SIZE];int front;int rear;
    } Queue;void initQueue(Queue *q) {q->front = q->rear = 0;
    }int isQueueEmpty(Queue *q) {return q->front == q->rear;
    }void enqueue(Queue *q, TreeNode *node) {if ((q->rear + 1) % MAX_QUEUE_SIZE == q->front) {printf("Queue is full\n");return;}q->data[q->rear] = node;q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    }TreeNode* dequeue(Queue *q) {if (isQueueEmpty(q)) {printf("Queue is empty\n");return NULL;}TreeNode *node = q->data[q->front];q->front = (q->front + 1) % MAX_QUEUE_SIZE;return node;
    }void levelOrderTraversal(TreeNode *root) {if (!root) return;Queue q;initQueue(&q);enqueue(&q, root);while (!isQueueEmpty(&q)) {TreeNode *node = dequeue(&q);printf("%d ", node->data);if (node->left) enqueue(&q, node->left);if (node->right) enqueue(&q, node->right);}
    }
    
二、线索二叉树

线索二叉树是一种特殊的二叉树,通过对空指针加以利用,使得二叉树的遍历更加高效。在线索二叉树中,每个节点的空指针指向在某种遍历方式下的前驱或后继节点。

  1. 线索的定义

    • 前驱(Predecessor):在某种遍历方式下,当前节点的前一个节点。
    • 后继(Successor):在某种遍历方式下,当前节点的后一个节点。
  2. 线索二叉树的类型

    • 前序线索二叉树(Preorder Threaded Binary Tree):前序遍历下的前驱和后继。
    • 中序线索二叉树(Inorder Threaded Binary Tree):中序遍历下的前驱和后继。
    • 后序线索二叉树(Postorder Threaded Binary Tree):后序遍历下的前驱和后继。
  3. 线索二叉树的结构定义

    typedef struct ThreadedTreeNode {int data;struct ThreadedTreeNode *left;struct ThreadedTreeNode *right;int ltag; // 0: left指向左孩子, 1: left指向前驱int rtag; // 0: right指向右孩子, 1: right指向后继
    } ThreadedTreeNode;
    
  4. 中序线索二叉树的建立

    void createInorderThread(ThreadedTreeNode *root, ThreadedTreeNode **pre) {if (root) {createInorderThread(root->left, pre);if (!root->left) {root->left = *pre;root->ltag = 1;}if (*pre && !(*pre)->right) {(*pre)->right = root;(*pre)->rtag = 1;}*pre = root;createInorderThread(root->right, pre);}
    }void createInorderThreadTree(ThreadedTreeNode *root) {ThreadedTreeNode *pre = NULL;if (root) {createInorderThread(root, &pre);if (pre->right == NULL) {pre->rtag = 1;}}
    }
    
  5. 中序线索二叉树的遍历

    void inorderThreadedTraversal(ThreadedTreeNode *root) {ThreadedTreeNode *p = root;while (p) {while (p->ltag == 0) {p = p->left;}printf("%d ", p->data);while (p->rtag == 1 && p->right != NULL) {p = p->right;printf("%d ", p->data);}p = p->right;}
    }
    

使用场景

  1. 表达式树的构建和求值:通过中序遍历和后序遍历,可以有效地对表达式进行解析和求值。
  2. 数据库查询优化:使用线索二叉树可以加快查询速度,减少查询时间。
  3. 文件系统管理:层次遍历用于文件系统目录的遍历,便于管理和查找文件。
  4. 数据压缩与编码:霍夫曼树利用二叉树结构实现高效的编码和解码。
关键字:【408考点之数据结构】二叉树的遍历及线索二叉树

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: