专题-【线索二叉树】

**线索二叉树**

线索二叉树是一种特殊的二叉树结构，它通过在每个结点中存储额外的信息来实现对二叉树进行遍历的功能。这种结构可以用来表示一棵二叉树的前序、中序和后序遍历结果。

**线索二叉树的定义**

线索二叉树是一种带有额外信息的二叉树，每个结点包含以下信息：

* `key`：结点的值* `left`：左孩子的指针（可能为NULL）
* `right`：右孩子的指针（可能为NULL）
* `front`：前序遍历结果中的线索（可能为NULL）
* `back`：后序遍历结果中的线索（可能为NULL）

**线索二叉树的构造**

要构造一个线索二叉树，我们需要先定义一个结点结构，然后根据给定的前序、中序和后序遍历结果来构建线索二叉树。

c// 结点结构typedef struct Node {
 int key;
 struct Node* left;
 struct Node* right;
 struct Node* front;
 struct Node* back;
} Node;

// 构造函数Node* constructTree(int pre[], int in[], int post[], int n) {
 if (n ==0) return NULL;

 // 根据前序遍历结果找到根结点 Node* root = malloc(sizeof(Node));
 root->key = pre[0];
 root->left = NULL;
 root->right = NULL;
 root->front = NULL;
 root->back = NULL;

 int i, j;
 for (i =0; i < n; i++) {
 if (in[i] == root->key) break;
 }

 // 根据中序遍历结果找到左子树和右子树 Node* left = constructTree(pre +1, in, post, i);
 Node* right = constructTree(pre + i +1, in + i +1, post + i, n - i -1);

 // 根据前序遍历结果找到线索 root->front = left;
 root->back = right;

 return root;
}

c// 前序遍历void preOrder(Node* node) {
 if (node == NULL) return;

 printf("%d ", node->key);
 preOrder(node->front);
}

// 中序遍历void inOrder(Node* node) {
 if (node == NULL) return;

 inOrder(node->left);
 printf("%d ", node->key);
 inOrder(node->right);
}

// 后序遍历void postOrder(Node* node) {
 if (node == NULL) return;

 postOrder(node->left);
 postOrder(node->right);
 printf("%d ", node->key);
}

cint main() {
 int pre[] = {1,2,4,5,3,6,7};
 int in[] = {4,2,5,1,6,3,7};
 int post[] = {4,5,2,6,7,3,1};

 Node* root = constructTree(pre, in, post, sizeof(pre) / sizeof(int));

 printf("前序遍历:");
 preOrder(root);
 printf("
");

 printf("中序遍历:");
 inOrder(root);
 printf("
");

 printf("后序遍历:");
 postOrder(root);
 printf("
");

 return0;
}