树的表示法

树的表示法有二叉链表示法、三叉链表示法、双亲链表示法等

二叉链表示法：

typedef struct BiTNode
{
	int data;
	struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//二叉链表示法1
int main_01()
{
	BiTNode t1,t2,t3,t4,t5;
	t1.data = 1;
	t2.data = 2;
	t3.data = 3;
	t4.data = 4;
	t5.data = 5;

	//建立关系
	t1.lchild = &t2;
	t1.rchild = &t3;
	t2.lchild = &t4;
	t2.rchild = &t5;

	system("pause");
	return 1;
}

//二叉链表示法2
int main()
{
	BiTNode *p1,*p2,*p3,*p4,*p5;
	p1 = (BiTNode*)malloc(sizeof(BiTNode));
	p2 = (BiTNode*)malloc(sizeof(BiTNode));
	p3 = (BiTNode*)malloc(sizeof(BiTNode));
	p4 = (BiTNode*)malloc(sizeof(BiTNode));
	p5 = (BiTNode*)malloc(sizeof(BiTNode));
	p1->data = 1;
	p2->data = 2;
	p3->data = 3;
	p4->data = 4;
	p5->data = 5;

	//建立关系
	p1->lchild = p2;
	p1->rchild = p3;
	p2->lchild = p4;
	p2->rchild = p5;

	//树的遍历

	system("pause");
	return 1;
}

三叉链表示法(双向，可以根据子结点找到父结点)：

typedef struct TriTNode
{
	int data;
	struct TriTNode *lchild,*rchild;
	struct TriTNode *parent;
}TriTNode,*TriTree;

int main()
{
	TriTNode *p1,*p2,*p3,*p4,*p5;
	p1 = (TriTNode*)malloc(sizeof(TriTNode));
	p2 = (TriTNode*)malloc(sizeof(TriTNode));
	p3 = (TriTNode*)malloc(sizeof(TriTNode));
	p4 = (TriTNode*)malloc(sizeof(TriTNode));
	p5 = (TriTNode*)malloc(sizeof(TriTNode));
	p1->data = 1;
	p2->data = 2;
	p3->data = 3;
	p4->data = 4;
	p5->data = 5;

	//建立关系
	p1->lchild = p2;
	p1->rchild = p3;
	p2->lchild = p4;
	p2->rchild = p5;

	p5->parent = p2;
	p4->parent = p2;
	p2->parent = p1;
	p3->parent = p1;

	system("pause");
	return 1;
}

双亲链表示法：

//双亲链表示法
typedef struct BptNode
{
	int data;
	int parentPosition;//指向双亲的指针，数组下标
	char LRTag;//左右孩子标志域
}BPTNode;
typedef struct BPTree
{
	BPTNode nodes[100];//因为节点之间是分散的，需要把节点存储到数组中
	int num_node;//节点数目
	int root;//根节点的位置，注意此区域存储的是父亲节点在数组的下标
}BPTree;

int main()
{
	BPTree tree;

	//根结点
	tree.nodes[0].parentPosition = 1000;//根结点没有父结点，这里随意指定了一个
	tree.nodes[0].data = 'A';

	//B结点
	tree.nodes[1].parentPosition = 0;
	tree.nodes[1].LRTag = 1;//1代指左结点
	tree.nodes[1].data = 'B';

	//C结点
	tree.nodes[1].parentPosition = 0;
	tree.nodes[1].LRTag = 2;//2代指右结点
	tree.nodes[1].data = 'C';


	system("pause");
	return 1;
}