我们使用二叉树总该需要有一个连接他们的方法,比如根节点有两个子节点,我们一个在根节点左侧,一个在根节点右侧,我们到底该如何表示他们,其实非常简单,我们只需给根节点这个节点中增加两个属性,一个指向左侧子节点的指针,一个是指向右侧节点的指针即可。如下图表示:
【实现代码】
#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; }