数据结构初阶:二叉树链式存储实现
在顺序存储结构之外,二叉树更常见的实现方式是链式存储。这种方式通过指针将节点连接起来,相比数组更加灵活,能够适应各种形态的二叉树。
一、二叉树的链式结构
链式二叉树的核心在于节点定义。每个节点包含数据域以及指向左右子树的指针。我们通常使用二叉链表来实现,即每个节点包含两个指针域。
// 链式二叉树的节点定义
typedef struct BinaryTree {
Elemtype data;
struct BinaryTree* leftChild;
struct BinaryTree* rightChild;
} BTNode;
这里 data 存储当前节点的值,leftChild 和 rightChild 分别指向左子树和右子树的根节点地址。如果某个方向没有子节点,则对应指针为 NULL。
二、二叉树的创建
为了便于理解基本性质,我们先手动构建一棵具体的二叉树,暂不涉及复杂的增删查改逻辑。
2.1、创建二叉树节点
节点创建与链表类似,需要动态分配内存并初始化指针。
// 创建新节点
BTNode* BuyNode(Elemtype data) {
BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
if (newNode == NULL) {
perror("create new node fail!");
return NULL;
}
newNode->data = data;
newNode->leftChild = newNode->rightChild = NULL;
return newNode;
}
注意内存分配失败时的处理,以及初始化后将左右指针置空,避免野指针。
2.2、二叉树节点的链接
通过调用 BuyNode 创建各个节点后,手动建立它们之间的父子关系。
BTNode* createNewBT() {
// 创建节点
BTNode* NodeA = BuyNode('A');
BTNode* NodeB = BuyNode('B');
BTNode* NodeC = BuyNode('C');
BTNode* NodeD = BuyNode();
BTNode* NodeE = BuyNode();
BTNode* NodeF = BuyNode();
BTNode* NodeG = BuyNode();
BTNode* NodeH = BuyNode();
BTNode* NodeI = BuyNode();
BTNode* NodeO = BuyNode();
NodeA->leftChild = NodeB;
NodeA->rightChild = NodeC;
NodeB->leftChild = NodeD;
NodeB->rightChild = NodeE;
NodeD->leftChild = NodeH;
NodeC->leftChild = NodeF;
NodeF->leftChild = NodeI;
NodeH->leftChild = NodeO;
NodeA;
}



