数据结构--二叉树的二叉链表实现

1 二叉树的二叉链表示意图

  二叉链表的每个结点由三个域组成:数据域，左指针域和右指针域。左右指针分别用来保存左右孩子结点的存储地址。

2 二叉链表实现二叉树

2.1 头文件及其定义

• BTNode.h

#pragma once
typedef char BTDataType;
typedef struct BinaryTreeNode {
   
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);
// 二叉树节点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root);

• queue.h(队列的实现见附录)

#pragma once
#include"BTNode.h"

//队列的单向无头非循环链表的实现
typedef BTNode* QDataType;
typedef struct QNode {
   
	QDataType data;
	struct QNode* next;
} QNode;  //队列中的链表节点

typedef struct Queue {
   
	QNode* front;  //指向队头
	QNode* rear;  //指向队尾
}Queue;

void queueInit(Queue* q);
QNode* creatNode(QDataType data);
void queuePush(Queue* q, QDataType data);
void queuePop(Queue* q);
QDataType queueFront(Queue* q);
QDataType queueBack(Queue* q);
int queueSize(Queue* q);
int queueEmpty(Queue* q);
void queueDestroy(Queue* q);

• BTNode.c

#include<stdio.h>
#include<stdlib.h>
#include"queue.h"
#include"BTNode.h"

2.2 根据前序遍历的数组创建二叉树

// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* binaryTreeCreate(BTDataType arr[], int n, int* idx) {
   
	// 递归停止条件
	if (*idx >= n || arr[*idx] == '#') {