三叉链表存储二叉树（三叉链表存储二叉树空指针）

## 三叉链表存储二叉树### 简介在二叉树的链式存储结构中，我们通常使用孩子兄弟表示法，即使用两个指针域，分别指向左孩子和右孩子。然而，这种表示方法在某些操作中效率较低，例如查找父节点。为了解决这个问题，我们可以引入

三叉链表

来存储二叉树。### 三叉链表结构三叉链表是在二叉链表的基础上增加一个指针域，用于指向当前节点的父节点。其结构如下：```c typedef struct TriTNode {ElemType data; // 数据域struct TriTNode

lchild; // 左孩子指针struct TriTNode

rchild; // 右孩子指针struct TriTNode

parent; // 父节点指针 } TriTNode,

TriTree; ```其中：- `data`：存储节点数据。 - `lchild`：指向左孩子节点。 - `rchild`：指向右孩子节点。 - `parent`：指向父节点。### 三叉链表的优点相比于二叉链表，三叉链表具有以下优点：1.

方便查找父节点:

通过`parent`指针可以直接访问父节点，无需从根节点开始遍历。 2.

简化某些操作:

一些需要访问父节点的操作，例如查找节点的祖先节点、计算节点深度等，使用三叉链表会更加方便。 3.

更灵活的遍历方式:

除了先序、中序、后序遍历，三叉链表还可以实现更灵活的遍历方式，例如从任意节点开始向上或向下遍历。### 三叉链表的缺点当然，三叉链表也存在一些缺点：1.

空间开销更大:

相比于二叉链表，三叉链表每个节点需要额外存储一个指针，增加了空间开销。 2.

构建过程较复杂:

在构建三叉链表时，需要同时维护三个指针域，相对复杂一些。### 应用场景尽管三叉链表存在一些缺点，但它在某些应用场景下仍然具有优势，例如：1.

需要频繁查找父节点的应用:

例如，在表达式树中，需要频繁访问父节点进行运算符优先级的判断。 2.

需要进行路径查找的应用:

例如，在路由算法中，可以使用三叉链表存储网络拓扑结构，并利用父节点指针进行路径查找。### 总结三叉链表是一种特殊的二叉树存储结构，通过增加一个父节点指针，可以方便地访问父节点，并简化一些操作。虽然它相对于二叉链表增加了空间开销，但在某些应用场景下仍然具有优势。## 代码示例```c #include #include typedef struct TriTNode {int data;struct TriTNode

lchild;struct TriTNode

rchild;struct TriTNode

parent; } TriTNode,

TriTree;// 创建节点 TriTNode

createNode(int data) {TriTNode

newNode = (TriTNode

)malloc(sizeof(TriTNode));newNode->data = data;newNode->lchild = NULL;newNode->rchild = NULL;newNode->parent = NULL;return newNode; }// 插入节点 void insertNode(TriTree

root, int data) {TriTNode

newNode = createNode(data);if (

root == NULL) {

root = newNode;return;}TriTNode

current =

root;while (1) {if (data < current->data) {if (current->lchild == NULL) {current->lchild = newNode;newNode->parent = current;return;} else {current = current->lchild;}} else {if (current->rchild == NULL) {current->rchild = newNode;newNode->parent = current;return;} else {current = current->rchild;}}} }// 打印树 (先序遍历) void printTree(TriTree root) {if (root != NULL) {printf("%d ", root->data);printTree(root->lchild);printTree(root->rchild);} }int main() {TriTree root = NULL;insertNode(&root, 5);insertNode(&root, 3);insertNode(&root, 8);insertNode(&root, 2);insertNode(&root, 4);insertNode(&root, 7);insertNode(&root, 9);printf("先序遍历: ");printTree(root);printf("\n");return 0; } ```这段代码演示了如何使用 C 语言实现三叉链表，并进行了节点的创建、插入和打印操作。

三叉链表存储二叉树

简介在二叉树的链式存储结构中，我们通常使用孩子兄弟表示法，即使用两个指针域，分别指向左孩子和右孩子。然而，这种表示方法在某些操作中效率较低，例如查找父节点。为了解决这个问题，我们可以引入**三叉链表**来存储二叉树。

三叉链表结构三叉链表是在二叉链表的基础上增加一个指针域，用于指向当前节点的父节点。其结构如下：```c typedef struct TriTNode {ElemType data; // 数据域struct TriTNode *lchild; // 左孩子指针struct TriTNode *rchild; // 右孩子指针struct TriTNode *parent; // 父节点指针 } TriTNode, *TriTree; ```其中：- `data`：存储节点数据。 - `lchild`：指向左孩子节点。 - `rchild`：指向右孩子节点。 - `parent`：指向父节点。

三叉链表的优点相比于二叉链表，三叉链表具有以下优点：1. **方便查找父节点:** 通过`parent`指针可以直接访问父节点，无需从根节点开始遍历。 2. **简化某些操作:** 一些需要访问父节点的操作，例如查找节点的祖先节点、计算节点深度等，使用三叉链表会更加方便。 3. **更灵活的遍历方式:** 除了先序、中序、后序遍历，三叉链表还可以实现更灵活的遍历方式，例如从任意节点开始向上或向下遍历。

三叉链表的缺点当然，三叉链表也存在一些缺点：1. **空间开销更大:** 相比于二叉链表，三叉链表每个节点需要额外存储一个指针，增加了空间开销。 2. **构建过程较复杂:** 在构建三叉链表时，需要同时维护三个指针域，相对复杂一些。

应用场景尽管三叉链表存在一些缺点，但它在某些应用场景下仍然具有优势，例如：1. **需要频繁查找父节点的应用:** 例如，在表达式树中，需要频繁访问父节点进行运算符优先级的判断。 2. **需要进行路径查找的应用:** 例如，在路由算法中，可以使用三叉链表存储网络拓扑结构，并利用父节点指针进行路径查找。

总结三叉链表是一种特殊的二叉树存储结构，通过增加一个父节点指针，可以方便地访问父节点，并简化一些操作。虽然它相对于二叉链表增加了空间开销，但在某些应用场景下仍然具有优势。

代码示例```c

include

include typedef struct TriTNode {int data;struct TriTNode *lchild;struct TriTNode *rchild;struct TriTNode *parent; } TriTNode, *TriTree;// 创建节点 TriTNode* createNode(int data) {TriTNode* newNode = (TriTNode*)malloc(sizeof(TriTNode));newNode->data = data;newNode->lchild = NULL;newNode->rchild = NULL;newNode->parent = NULL;return newNode; }// 插入节点 void insertNode(TriTree* root, int data) {TriTNode* newNode = createNode(data);if (*root == NULL) {*root = newNode;return;}TriTNode* current = *root;while (1) {if (data < current->data) {if (current->lchild == NULL) {current->lchild = newNode;newNode->parent = current;return;} else {current = current->lchild;}} else {if (current->rchild == NULL) {current->rchild = newNode;newNode->parent = current;return;} else {current = current->rchild;}}} }// 打印树 (先序遍历) void printTree(TriTree root) {if (root != NULL) {printf("%d ", root->data);printTree(root->lchild);printTree(root->rchild);} }int main() {TriTree root = NULL;insertNode(&root, 5);insertNode(&root, 3);insertNode(&root, 8);insertNode(&root, 2);insertNode(&root, 4);insertNode(&root, 7);insertNode(&root, 9);printf("先序遍历: ");printTree(root);printf("\n");return 0; } ```这段代码演示了如何使用 C 语言实现三叉链表，并进行了节点的创建、插入和打印操作。