链式二叉树数据结构（递归）

目录

一、链式二叉树结构实现

二、链式二叉树的基本方法实现

2.1 创造树结点

2.2 创造二叉树（前序）

2.3 二叉树的销毁

2.4 前中后序遍历

2.5 层序遍历

2.6 求二叉树结点个数

2.7 二叉树叶子结点个数

2.8 二叉树第k层节点个数

2.9 二叉树查找值为x的节点

2.10 判断二叉树是否是完全二叉树

三、总结

一、链式二叉树结构实现

typedef char BTDataType; //二叉树结构 typedef struct BinaryTreeNode { BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right; };

二、链式二叉树的基本方法实现

2.1 创造树结点

//创造树结点 BTNode* BuyNode(BTDataType x) { BTNode* root = (BTNode*)malloc(sizeof(BTNode)); if (root == NULL) { perror("malloc"); exit(1); } root->data = x; root->left = root->right = NULL; return root; }

2.2 创造二叉树（前序）

以这个实例为准：

这里用到了递归的思想，先不断递归左子树，然后跳出递归条件为NULL，然后再销毁函数栈并返回到递归之前那个函数，进而继续进行下一个代码块。比如在这里我们递归到左子树的最后一个NULL后，NULL这个创建的函数栈帧返回到D这个函数中继续执行右子树NULL，然后进入NULL这个函数栈帧中，跳出循环回到D这个函数中，返回D这个数据，此时D这个函数栈帧也就销毁了，进而不断递归右子树（D的兄弟结点）。

//构造二叉树(前序) BTNode* BinaryTreeCreate(BTDataType* a, int* pi)//a为数组，pi为下标 { if (a[*pi] == '#')//#表示空 { (*pi)++;//一定要加加 return NULL; } //根左右 BTNode* root = BuyNode(a[*pi]); (*pi)++; root->left = BinaryTreeCreate(a, pi); root->right = BinaryTreeCreate(a, pi); return root; }

2.3 二叉树的销毁

二叉树的销毁也是通过递归的方式进行实现的。

这里是不能顺序删除头结点的，首先要递归到左右再删头结点，否则唯一一个可以寻找左右结点的头结点消失了。

//二叉树的销毁 void BinaryTreeDestroy(BTNode** root) { assert(root); if (*root == NULL) { return; } BinaryTreeDestroy(&(*root)->left); BinaryTreeDestroy(&(*root)->right); free(*root); (*root)->data = 0; *root = NULL; }

指针销毁时，一定要记得销毁内部数据，避免释放后的数据残留，导致的安全问题。

2.4 前中后序遍历

//前序遍历 void BinaryTreePrevOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } //根左右 printf("%c ", root->data); BinaryTreePrevOrder(root->left); BinaryTreePrevOrder(root->right); } //中序遍历 void BinaryTreeInOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } //左根右 BinaryTreeInOrder(root->left); printf("%c ", root->data); BinaryTreeInOrder(root->right); } //后序遍历 void BinaryTreePostOrder(BTNode* root) { if (root == NULL) { printf("NULL "); return; } //左右根 BinaryTreePostOrder(root->left); BinaryTreePostOrder(root->right); printf("%c ", root->data); }

2.5 层序遍历

//层序遍历 void BinaryTreeLevelOrder(BTNode* root) { Queue q; QueueInit(&q); //插入队列中 QueuePush(&q, root); while (!QueueEmpty(&q)) { //取对头（保存） BTNode* top = QueueFront(&q); printf("%c ", top->data); QueuePop(&q); //将左右孩子插入 if(top->left) { QueuePush(&q, top->left); } if(top->right) { QueuePush(&q, top->right); } } QueueDestroy(&q); }

2.6 求二叉树结点个数

二叉树结点个数等于根结点加左右子树的结点个数=1+左右子树的结点

//求二叉树结点个数 int BinaryTreeSize(BTNode* root) { //结点个数=1+左右子树结点 if (root == NULL) { return 0; } return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right); }

2.7 二叉树叶子结点个数

叶子结点个数=左子树叶子结点个数 + 右子树结点个数

//求二叉树叶子结点个数 int BinaryTreeLeafSize(BTNode* root) { if (root == NULL) { return 0; } if (root->left == NULL && root->right == NULL) { return 1; } return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right); }

2.8 二叉树第k层节点个数

第k层结点递归过程中可以用逆向思维，将第一层设置为k层，然后不断递归减一达到预期的层数，达到我们想要的目的。第k层的结点个数=左子树第k层结点个数+右子树第k层结点个数。

//第k层结点个数 int BinaryTreeLevekSize(BTNode* root, int k) { if (root == NULL) { return 0; } if (k == 1) { return 1; } return BinaryTreeLevekSize(root->left,k - 1) + BinaryTreeLevekSize(root->right, k - 1); }

2.9 二叉树查找值为x的节点

寻找为x的结点，这里假设x为F这个结点，那我们寻找F这个结点时，只需要找到一个即可，所以我们向不断递归左子树孩子的结点与寻找值对比，找到后直接返回，所以return 后面接的是||这个或操作符，避免重复递归。

//在二叉树中寻找x值 BTNode* BinaryTreeFind(BTNode* root, BTDataType x) { if (root == NULL) { return NULL; } if (root->data == x) { return root; } BTNode* left = BinaryTreeFind(root->left, x); if (left) { return left; } BTNode* right = BinaryTreeFind(root->right, x); if (right) { return right; } return NULL; }

2.10 判断二叉树是否是完全二叉树

//判断二叉树是否是完全二叉树 bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { //取对头 BTNode* top = QueueFront(&q); QueuePop(&q); if (root == NULL)//跳出循环 { break; } QueuePush(&q, root->left); QueuePush(&q, root->right); } while (!QueueEmpty(&q)) { //判断当层第一个NULL这一层是否还有结点 BTNode* top = QueueFront(&q); QueuePop(&q); if (top != NULL) { QueueDestroy(&q); return false; } } QueueDestroy(&q); return true; }

三、总结

实现以上的二叉树方法离不开递归，当然这里遍历可以分两种类型，一种是递归型（前中后序遍历），另一种是非递归型（层序遍历），但是另一种非递归型需要利用到另外学到的数据结构（队列）。用这个队列可以存储需要顺序遍历的结点，当然这个思想，让我也知道了原来数据结构之间也是可以联系在一起的，并可以一起使用并实现一个另一个数据结构的方法。这个二叉树体现出了递归的便利性，但也需要我们不断画图，并不断理解起函数栈帧的建立和销毁。总的来说，二叉树这些代码实现让我大脑充实了很多知识，学会了递归，在一个就是我觉得重要的是二叉树的创造，我在这里卡了很久，因为总是忘记在为空的情况下让指针加加，导致我调试也很难看出来，而且创造二叉树，是我们理解二叉树的基础，我认为很有必要重点关注这个。