一、二叉树的链式结构
顺序存储虽然直观,但在处理稀疏树或动态增长场景时存在空间浪费。链式存储通过指针将节点连接起来,更加灵活。二叉树的链式结构主要分为二叉链(含左右指针)和三叉链(含父指针),本教程重点讲解最常用的二叉链。
// 定义二叉树节点
typedef char Elemtype;
typedef struct BinaryTree {
Elemtype data;
struct BinaryTree* leftChild;
struct BinaryTree* rightChild;
} BTNode;
每个节点包含数据域和两个指针域,分别指向左子树和右子树的根节点地址。这种结构天然适合递归操作。
二、二叉树的创建
在掌握基本性质后,我们手动构建一棵二叉树来演示节点链接。相比复杂的增删查改逻辑,手动初始化有助于理解树形结构。
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;
}
注意:务必检查 malloc 返回值,并在返回前确保指针已初始化。
2. 手动链接节点
通过调用 BuyNode 生成节点,再手动设置 leftChild 和 rightChild 指针。
BTNode* createNewBT() {
// 创建节点 A-I, O
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;
}


