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

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

【实现代码】

#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;
}