代码分享|C语言手写二叉树（链式存储结构）链表|数据结构|算法|leetcode|二

C语言手写二叉树（链式存储结构）

二叉树结构
二叉树基本运算
代码
图例（main函数执行过程如下：）
- 阶段I
- 阶段II
- 阶段III
- 阶段IV
- 阶段V
- 先序遍历输出过程

二叉树结构二叉树可以用顺序存储或链式存储两种结构，顺序存储需要借助一维数组，然后通过内存之间位置找到相应元素，访问速度和内存将会大大提升。顺序存储结构只适用于完全二叉树，一般二叉树不宜用顺序表示。下面将着重讲解二叉树的链式存储结构。
链式存储结构提供了二叉树在计算机内的一种表示方法，称为二叉链表。

文章图片

// An highlighted block //节点结构体 typedef struct btnode { char element; struct btnode *lChild; struct btnode *rChild; }BTNode; //二叉树结构体 typedef struct binarytree { BTNode *root; }BinaryTree;

二叉树基本运算

void Create(BinaryTree *bt)；构造一棵空二叉树bt
BTNode *NewNode(char x, BTNode *ln, BTNode *rn)；创建一个新节点
bool Root(BinaryTree *bt, char *x)；判断二叉树是否为空，非空通过指针x返回根节点的值
void MakeTree(BinaryTree *bt, char e, BinaryTree *left, BinaryTree *right)；构造二叉树，根节点的值为e，left和right为左右子树

代码

// An highlighted block #include using namespace std; typedef struct btnode { char element; struct btnode *lChild; struct btnode *rChild; }BTNode; typedef struct binarytree { BTNode *root; }BinaryTree; //构造一棵空二叉树 void Create(BinaryTree *bt) { bt->root = NULL; } //创建一个新节点 BTNode *NewNode(char x, BTNode *ln, BTNode *rn) { BTNode *p = (BTNode *) malloc (sizeof(BTNode)); p->element = x; p->lChild = ln; p->rChild = rn; return p; } //判断二叉树是否为空，非空通过指针x返回根节点的值 bool Root(BinaryTree *bt, char *x) { if(bt->root) { x = &bt->root->element; return true; } else { return false; } } //构造二叉树，根节点的值为e，left和right为左右子树 void MakeTree(BinaryTree *bt, char e, BinaryTree *left, BinaryTree *right) { if(bt->root || left == right) { return ; } bt->root = NewNode(e, left->root, right->root); left->root = NULL; right->root = NULL; } // void PreOrder(BTNode *t) { if(!t) return; printf("\t%c\t\n", t->element); PreOrder(t->lChild); PreOrder(t->rChild); } //先序遍历二叉树 void PreOrderTree(BinaryTree *bt) { PreOrder(bt->root); } void Clear(BTNode *t) { if(!t) return; Clear(t->lChild); Clear(t->rChild); free(t); } void TreeClear(BinaryTree *bt) { Clear(bt->root); }int main() { BinaryTree a, b, x, y, z; //阶段I //构造5个空节点 Create(&a); Create(&b); Create(&x); Create(&y); Create(&z); //将节点连接为二叉树，注意节点a和b始终为空节点 MakeTree(&y, 'E', &a, &b); //阶段II MakeTree(&z, 'F', &a, &b); MakeTree(&x, 'C', &y, &z); //阶段III MakeTree(&y, 'D', &a, &b); //阶段IV MakeTree(&z, 'B', &y, &x); //阶段V printf("PreOrderTree: \n"); PreOrderTree(&z); //先序遍历打印二叉树 TreeClear(&z); system("pause"); return 0; }

图例（main函数执行过程如下：）阶段I