单向二叉树及双向二叉树表示

我们使用二叉树总该需要有一个连接他们的方法，比如根节点有两个子节点，我们一个在根节点左侧，一个在根节点右侧，我们到底该如何表示他们，其实非常简单，我们只需给根节点这个节点中增加两个属性，一个指向左侧子节点的指针，一个是指向右侧节点的指针即可。如下图表示：

【实现代码】

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tag_tirTNode
{
//节点的数据
char data;
//左子节点指针
struct tag_tirTNode* leftChild;
//右子节点指针
struct tag_tirTNode* rightChild;
}TirTNode;

int main()
{
// 定义树的节点元素
TirTNode treeA, treeB, treeC, treeD, treeE, treeF, treeG;

// 初始化
memset(&treeA, 0, sizeof(TirTNode));
memset(&treeB, 0, sizeof(TirTNode));
memset(&treeC, 0, sizeof(TirTNode));
memset(&treeD, 0, sizeof(TirTNode));
memset(&treeE, 0, sizeof(TirTNode));
memset(&treeF, 0, sizeof(TirTNode));
memset(&treeG, 0, sizeof(TirTNode));

treeA.data = ‘A’;// 节点值
treeA.leftChild = &treeB;// 左子节点
treeA.rightChild = &treeC;// 右子节点

treeB.data = ‘B’;
treeB.leftChild = &treeD;
treeB.rightChild = &treeE;

treeC.data = ‘C’;
treeC.leftChild = &treeF;
treeC.rightChild = &treeG;

// 让叶子节点的left和right都指向NULL
treeD.data = ‘D’;
treeD.leftChild = NULL;
treeD.rightChild = NULL;

treeE.data = ‘E’;
treeE.leftChild = NULL;
treeE.rightChild = NULL;

treeF.data = ‘F’;
treeF.leftChild = NULL;
treeF.rightChild = NULL;

treeG.data = ‘G’;
treeG.leftChild = NULL;
treeG.rightChild = NULL;

return 0;
}

以上是单向二叉树的图形和代码实现方法，其实二叉树还有双向表示的方法，就是让子节点有一个指针指向了父节点，这样就无论哪个节点，我们都可以方便的找到其父节点和子节点了。如下图： 【实现代码】

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct tag_tirTNode
{
//节点的数据
char data;
//左子节点指针
struct tag_tirTNode* leftChild;
//右子节点指针
struct tag_tirTNode* rightChild;
//父节点指针
struct tag_tirTNode* parentChild;
}TirTNode;

int main()
{
// 定义树的节点元素
TirTNode treeA, treeB, treeC, treeD, treeE, treeF, treeG;

// 初始化
memset(&treeA, 0, sizeof(TirTNode));
memset(&treeB, 0, sizeof(TirTNode));
memset(&treeC, 0, sizeof(TirTNode));
memset(&treeD, 0, sizeof(TirTNode));
memset(&treeE, 0, sizeof(TirTNode));
memset(&treeF, 0, sizeof(TirTNode));
memset(&treeG, 0, sizeof(TirTNode));

treeA.data = ‘A’;// 节点值
treeA.leftChild = &treeB;// 左子节点
treeA.rightChild = &treeC;// 右子节点
treeA.parentChild = NULL;// 根的父节点指针指向NULL

treeB.data = ‘B’;
treeB.leftChild = &treeD;
treeB.rightChild = &treeE;
// parentChild 指针指向父节点
treeB.parentChild = &treeA;

treeC.data = ‘C’;
treeC.leftChild = &treeF;
treeC.rightChild = &treeG;
treeC.parentChild = &treeA;

// 让叶子节点的left和right都指向NULL
treeD.data = ‘D’;
treeD.leftChild = NULL;
treeD.rightChild = NULL;
// parentChild 指针指向父节点
treeD.parentChild = &treeB;

treeE.data = ‘E’;
treeE.leftChild = NULL;
treeE.rightChild = NULL;
// parentChild 指针指向父节点
treeE.parentChild = &treeB;

treeF.data = ‘F’;
treeF.leftChild = NULL;
treeF.rightChild = NULL;
// parentChild 指针指向父节点
treeF.parentChild = &treeC;

treeG.data = ‘G’;
treeG.leftChild = NULL;
treeG.rightChild = NULL;
// parentChild 指针指向父节点
treeG.parentChild = &treeC;

return 0;
}