数据结构——二叉树-阿里云开发者社区

一、概念

1.定义

一棵二叉树是结点组成的一个有限集合，该集合：

（1）：或为空

（2）：由一个根结点加上左子树和右子树组成

（3）：左、右子树也是二叉树

例：

2.特性

（1）二叉树不存在度大于2的结点

（2）二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树

（3）空树也是二叉树

3.特殊的二叉树

3.1满二叉树

一个二叉树的每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数为-1，则这个二叉树为满二叉树。

3.2完全二叉树

对于深度为k，且有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时称为完全二叉树。

满二叉树是一种特殊的完全二叉树。

4.二叉树的性质

（1）：若规定根结点的层数为1，则一棵非空二叉树的第i层上最多有个结点。

（2）：若规定根结点的层数为1，则深度为h的二叉树的最大结点数是-1。

（3）：对任何一棵二叉树，如果度为0其叶子结点个数为，度为2的分支结点个数为，则有。

（4）：若规定根结点的层数为1，具有n个结点的满二叉树的深度。（ps:是将log以2为底，n+1为对数的值进行取整赋给h）

（5）：对于具有n个结点的完全二叉树，如果按照从上至下，从左至右的数组顺序对所有结点从0开始编号，则对于序号为i的结点有：

—若i>0，i位置结点的双亲序号为（i-1）/2；i=0，i为根结点编号，无双亲结点

—若2i+1=n则无左孩子

—若2i+2=n则无右孩子

5.二叉树的存储结构

5.1顺序存储

顺序存储结构就是采用数组来存储，一般使用数组存储只适合表示完全二叉树，因为不是完全二叉树会存在空间浪费。而现实使用中只有堆才会使用数组来存储。

二叉树顺序存储在物理上是一个数组，在逻辑上是一棵二叉树。

5.2链式存储

二叉树的链式存储结构是指用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域。

左右指针分别用来给出该结点左右孩子所在的链结点的存储地址。

二、结构体定义

typedef int BTDataType;
typedef struct BinaryTreeNode//二叉树
{
  BTDataType data;
  struct BinaryTreeNode* lchild;//左孩子
  struct BinaryTreeNode* rchild;//右孩子
}BTNode;

三、接口实现

BTNode* BinaryTreeCreate(BTDataType* array, int size, BTDataType invalid, int* index);// 通过前序遍历数组构建二叉树
BTNode* BuyBTNode(BTDataType data);//申请结点
void BinaryTreeDestory(BTNode** root);// 二叉树销毁
int BinaryTreeSize(BTNode* root);// 二叉树节点个数
int BinaryTreeLeafSize(BTNode* root);// 二叉树叶子节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树第k层节点个数
int BinaryHeight(BTNode* root);//二叉树高度
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树查找值为x的节点
void BinaryTreePrevOrder(BTNode* root);// 二叉树前序遍历 
void BinaryTreeInOrder(BTNode* root);// 二叉树中序遍历
void BinaryTreePostOrder(BTNode* root);// 二叉树后序遍历
void BinaryTreeLevelOrder(BTNode* root);// 层序遍历
int BinaryTreeComplete(BTNode* root);// 判断二叉树是否是完全二叉树
void Test_BinaryTree();//测试函数

1.通过前序遍历数组构建二叉树

BTNode* BinaryTreeCreate(BTDataType* array, int size, BTDataType invalid, int* index) {// 通过前序遍历数组构建二叉树
  assert(array);
  BTNode* root = NULL;
  if (*index < size && array[*index] != invalid) {//index小于数组返回并且当前元素不是无效元素，递归创建
  root = BuyBTNode(array[*index]);//创建根结点
  (*index)++;
  root->lchild = BinaryTreeCreate(array, size, invalid, index);//递归创建左子树
  (*index)++;
  root->rchild = BinaryTreeCreate(array, size, invalid, index);//递归创建右子树
  }
  return root;
}
BTNode* BuyBTNode(BTDataType data) {//申请结点
  BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
  if (newNode == NULL) {//申请失败
  assert(0);
  return NULL;
  }
  newNode->lchild = NULL;
  newNode->rchild = NULL;
  newNode->data = data;
  return newNode;
}

其中size为数组的大小；index为数组下标标志；用invalid来代表数组中的无效元素。

通过前序遍历的思想进行递归创建二叉树。

2.二叉树的查找

BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {// 二叉树查找值为x的节点
  if (root == NULL) {//空树
  return NULL;
  }
  if (root->data == x) {//x为根结点
  return root;
  }
  BTNode* ret = NULL;
  if (ret = BinaryTreeFind(root->lchild, x)) {//递归查找左子树
  return ret;
  }
  return BinaryTreeFind(root->rchild, x);//递归查找右子树
}

3.统计二叉树结点个数

int BinaryTreeSize(BTNode* root) {// 二叉树结点个数
  if (root == NULL) {
  return 0;
  }
  return BinaryTreeSize(root->lchild) + BinaryTreeSize(root->rchild) + 1;
}

4.统计二叉树叶子结点个数

int BinaryTreeLeafSize(BTNode* root) {// 二叉树叶子结点个数
  if (root == NULL) {//空树
  return 0;
  }
  if (root->lchild == NULL && root->rchild == NULL) {//碰到叶子结点回退并返回1
  return 1;
  }
  return BinaryTreeLeafSize(root->lchild) + BinaryTreeLeafSize(root->rchild);//累计叶子结点个数
}

5.统计二叉树第k层结点个数

int BinaryTreeLevelKSize(BTNode* root, int k) {// 二叉树第k层节点个数
  if (root == NULL || k <= 0) {//空树||k不合法
  return 0;
  }
  if (k == 1) {//第一层
  return 1;
  }
  return BinaryTreeLevelKSize(root->lchild, k - 1) + BinaryTreeLevelKSize(root->rchild, k - 1);//排除了根结点，高度降1
}

6.求二叉树高度

int BinaryHeight(BTNode* root) {//二叉树高度
  if (root == NULL) {
  return 0;
  }
  int leftHeight = BinaryHeight(root->lchild) + 1;
  int rightHeight = BinaryHeight(root->rchild) + 1;
  return leftHeight > rightHeight ? leftHeight : rightHeight;//返回较高的子树+1即为二叉树高度
}

7.二叉树前序遍历

void BinaryTreePrevOrder(BTNode* root) {// 二叉树前序遍历 
  if (root == NULL) {
  return;
  }
  printf("%d ", root->data);
  BinaryTreePrevOrder(root->lchild);
  BinaryTreePrevOrder(root->rchild);
}

8.二叉树中序遍历

void BinaryTreeInOrder(BTNode* root) {// 二叉树中序遍历
  if (root == NULL) {
  return;
  }
  BinaryTreeInOrder(root->lchild);
  printf("%d ", root->data);
  BinaryTreeInOrder(root->rchild);
}

9.二叉树后序遍历

void BinaryTreePostOrder(BTNode* root) {// 二叉树后序遍历
  if (root == NULL) {
  return;
  }
  BinaryTreePostOrder(root->lchild);
  BinaryTreePostOrder(root->rchild);
  printf("%d ", root->data);
}

10.二叉树层序遍历

void BinaryTreeLevelOrder(BTNode* root) {// 层序遍历
  if (root == NULL) {
  return;
  }
  Queue q;
  QueueInit(&q);//初始化队列
  QueuePush(&q, root);//根结点入队
  while (!QueueEmpty(&q)) {//队列不为空
  BTNode* cur = QueueFront(&q);//获取队头
  QueuePop(&q);//出队
  printf("%d ", cur->data);
  if (cur->lchild) {//若有左孩子，左孩子入队
    QueuePush(&q, cur->lchild);
  }
  if (cur->rchild) {//若有右孩子，右孩子入队
    QueuePush(&q, cur->rchild);
  }
  }
  printf("\n");
  QueueDestroy(&q);//销毁队列
}

二叉树层序遍历需要借助队列进行辅助，往期博客有队列实现的具体方法。

11.判断二叉树是否是完全二叉树

int BinaryTreeComplete(BTNode* root) {// 判断二叉树是否是完全二叉树
  if (root == NULL) {//空树也是完全二叉树
  return 1;
  }
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  int isCompleteTree = 1;
  int flag = 0;
  while (!QueueEmpty(&q)) {//按照层序遍历的思想找第一个不饱和的结点
  BTNode* cur = QueueFront(&q);//获取队头
  QueuePop(&q);//出队
  if (flag) {
    //已经找到不饱和结点，其后续结点均为叶子结点，不能有孩子
    if (cur->lchild || cur->rchild) {//有孩子一定不是完全二叉树
    isCompleteTree = 0;
    break;
    }
  }
  else {
    //按照层序遍历找不饱和的结点
    if (cur->lchild && cur->rchild) {//左右孩子都存在，饱和结点;左右孩子依次入队列
    QueuePush(&q, cur->lchild);
    QueuePush(&q, cur->rchild);
    }
    else if (cur->lchild) {//只有左孩子，找到不饱和结点
    QueuePush(&q, cur->lchild);
    flag = 1;
    }
    else if (cur->rchild) {//只有右孩子，一定不是完全二叉树
    break;
    }
    else {//叶子结点
    flag = 1;
    }
  }
  }
  QueueDestroy(&q);//销毁队列
  return isCompleteTree;
}

具体的思想就是根据完全二叉树依次排列的特点，找到二叉树第一个不饱和的结点，判断当前结点以及是否满足完全二叉树的特点，以及是否满足后续结点都为叶子结点的特点进行判断此二叉树是否是完全二叉树。

12.二叉树的销毁

void BinaryTreeDestory(BTNode** root) {// 二叉树销毁
  if (*root == NULL) {
  return;
  }
  //利用后续遍历的思想进行销毁
  BinaryTreeDestory(&(*root)->lchild);
  BinaryTreeDestory(&(*root)->rchild);
  free(*root);
  *root = NULL;//将外部的实参置为空
}

四、接口测试

1.测试函数

void Test_BinaryTree() {//测试函数
  int array[] = { 1,2,3,-1,-1,-1,4,5,-1,-1,6 };
  int index = 0;
  BTNode* root = BinaryTreeCreate(array, sizeof(array) / sizeof(array[0]), -1, &index);//用-1代表无效元素，即这个子树不存在
  BTNode* ret = NULL;
  if (BinaryTreeComplete(root)) {
  printf("是完全二叉树。\n");
  }
  else {
  printf("不是完全二叉树。\n");
  }
  printf("前序遍历:");
  BinaryTreePrevOrder(root);
  printf("\n");
  printf("中序遍历:");
  BinaryTreeInOrder(root);
  printf("\n");
  printf("后序遍历:");
  BinaryTreePostOrder(root);
  printf("\n");
  printf("层序遍历:");
  BinaryTreeLevelOrder(root);
  printf("二叉树中总节点个数：%d\n", BinaryTreeSize(root));
  printf("二叉树中叶子节点个数：%d\n", BinaryTreeLeafSize(root));
  if (ret = BinaryTreeFind(root, 5))
  {
  printf("%d 在二叉树中\n", ret->data);
  }
  else
  {
  printf("%d 不在二叉树中\n", 5);
  }
  if (ret = BinaryTreeFind(root, 15))
  {
  printf("%d 在二叉树中\n", ret->data);
  }
  else
  {
  printf("%d 不在二叉树中\n", 15);
  }
  printf("二叉树的高度：%d\n", BinaryHeight(root));
  printf("二叉树第%d层节点个数%d\n", 3, BinaryTreeLevelKSize(root, 3));
  printf("二叉树第%d层节点个数%d\n", 10, BinaryTreeLevelKSize(root, 10));
  BinaryTreeDestory(&root);//销毁二叉树
}

2.测试结果

五、完整代码

#include<stdio.h>
#include<assert.h>
#include<malloc.h>
#include"Queue.h"
typedef int BTDataType;
typedef struct BinaryTreeNode//二叉树
{
  BTDataType data;
  struct BinaryTreeNode* lchild;//左孩子
  struct BinaryTreeNode* rchild;//右孩子
}BTNode;
BTNode* BinaryTreeCreate(BTDataType* array, int size, BTDataType invalid, int* index);// 通过前序遍历数组构建二叉树
BTNode* BuyBTNode(BTDataType data);//申请结点
void BinaryTreeDestory(BTNode** root);// 二叉树销毁
int BinaryTreeSize(BTNode* root);// 二叉树节点个数
int BinaryTreeLeafSize(BTNode* root);// 二叉树叶子节点个数
int BinaryTreeLevelKSize(BTNode* root, int k);// 二叉树第k层节点个数
int BinaryHeight(BTNode* root);//二叉树高度
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);// 二叉树查找值为x的节点
void BinaryTreePrevOrder(BTNode* root);// 二叉树前序遍历 
void BinaryTreeInOrder(BTNode* root);// 二叉树中序遍历
void BinaryTreePostOrder(BTNode* root);// 二叉树后序遍历
void BinaryTreeLevelOrder(BTNode* root);// 层序遍历
int BinaryTreeComplete(BTNode* root);// 判断二叉树是否是完全二叉树
void Test_BinaryTree();//测试函数
int main() {
  Test_BinaryTree();
  return 0;
}
BTNode* BinaryTreeCreate(BTDataType* array, int size, BTDataType invalid, int* index) {// 通过前序遍历数组构建二叉树
  assert(array);
  BTNode* root = NULL;
  if (*index < size && array[*index] != invalid) {//index小于数组返回并且当前元素不是无效元素，递归创建
  root = BuyBTNode(array[*index]);//创建根结点
  (*index)++;
  root->lchild = BinaryTreeCreate(array, size, invalid, index);//递归创建左子树
  (*index)++;
  root->rchild = BinaryTreeCreate(array, size, invalid, index);//递归创建右子树
  }
  return root;
}
BTNode* BuyBTNode(BTDataType data) {//申请结点
  BTNode* newNode = (BTNode*)malloc(sizeof(BTNode));
  if (newNode == NULL) {//申请失败
  assert(0);
  return NULL;
  }
  newNode->lchild = NULL;
  newNode->rchild = NULL;
  newNode->data = data;
  return newNode;
}
BTNode* BinaryTreeFind(BTNode* root, BTDataType x) {// 二叉树查找值为x的节点
  if (root == NULL) {//空树
  return NULL;
  }
  if (root->data == x) {//x为根结点
  return root;
  }
  BTNode* ret = NULL;
  if (ret = BinaryTreeFind(root->lchild, x)) {//递归查找左子树
  return ret;
  }
  return BinaryTreeFind(root->rchild, x);//递归查找右子树
}
int BinaryTreeSize(BTNode* root) {// 二叉树结点个数
  if (root == NULL) {
  return 0;
  }
  return BinaryTreeSize(root->lchild) + BinaryTreeSize(root->rchild) + 1;
}
int BinaryTreeLeafSize(BTNode* root) {// 二叉树叶子结点个数
  if (root == NULL) {//空树
  return 0;
  }
  if (root->lchild == NULL && root->rchild == NULL) {//碰到叶子结点回退并返回1
  return 1;
  }
  return BinaryTreeLeafSize(root->lchild) + BinaryTreeLeafSize(root->rchild);//累计叶子结点个数
}
int BinaryTreeLevelKSize(BTNode* root, int k) {// 二叉树第k层节点个数
  if (root == NULL || k <= 0) {//空树||k不合法
  return 0;
  }
  if (k == 1) {//第一层
  return 1;
  }
  return BinaryTreeLevelKSize(root->lchild, k - 1) + BinaryTreeLevelKSize(root->rchild, k - 1);//排除了根结点，高度降1
}
int BinaryHeight(BTNode* root) {//二叉树高度
  if (root == NULL) {
  return 0;
  }
  int leftHeight = BinaryHeight(root->lchild) + 1;
  int rightHeight = BinaryHeight(root->rchild) + 1;
  return leftHeight > rightHeight ? leftHeight : rightHeight;//返回较高的子树+1即为二叉树高度
}
void BinaryTreePrevOrder(BTNode* root) {// 二叉树前序遍历 
  if (root == NULL) {
  return;
  }
  printf("%d ", root->data);
  BinaryTreePrevOrder(root->lchild);
  BinaryTreePrevOrder(root->rchild);
}
void BinaryTreeInOrder(BTNode* root) {// 二叉树中序遍历
  if (root == NULL) {
  return;
  }
  BinaryTreeInOrder(root->lchild);
  printf("%d ", root->data);
  BinaryTreeInOrder(root->rchild);
}
void BinaryTreePostOrder(BTNode* root) {// 二叉树后序遍历
  if (root == NULL) {
  return;
  }
  BinaryTreePostOrder(root->lchild);
  BinaryTreePostOrder(root->rchild);
  printf("%d ", root->data);
}
void BinaryTreeLevelOrder(BTNode* root) {// 层序遍历
  if (root == NULL) {
  return;
  }
  Queue q;
  QueueInit(&q);//初始化队列
  QueuePush(&q, root);//根结点入队
  while (!QueueEmpty(&q)) {//队列不为空
  BTNode* cur = QueueFront(&q);//获取队头
  QueuePop(&q);//出队
  printf("%d ", cur->data);
  if (cur->lchild) {//若有左孩子，左孩子入队
    QueuePush(&q, cur->lchild);
  }
  if (cur->rchild) {//若有右孩子，右孩子入队
    QueuePush(&q, cur->rchild);
  }
  }
  printf("\n");
  QueueDestroy(&q);//销毁队列
}
int BinaryTreeComplete(BTNode* root) {// 判断二叉树是否是完全二叉树
  if (root == NULL) {//空树也是完全二叉树
  return 1;
  }
  Queue q;
  QueueInit(&q);
  QueuePush(&q, root);
  int isCompleteTree = 1;
  int flag = 0;
  while (!QueueEmpty(&q)) {//按照层序遍历的思想找第一个不饱和的结点
  BTNode* cur = QueueFront(&q);//获取队头
  QueuePop(&q);//出队
  if (flag) {
    //已经找到不饱和结点，其后续结点均为叶子结点，不能有孩子
    if (cur->lchild || cur->rchild) {//有孩子一定不是完全二叉树
    isCompleteTree = 0;
    break;
    }
  }
  else {
    //按照层序遍历找不饱和的结点
    if (cur->lchild && cur->rchild) {//左右孩子都存在，饱和结点;左右孩子依次入队列
    QueuePush(&q, cur->lchild);
    QueuePush(&q, cur->rchild);
    }
    else if (cur->lchild) {//只有左孩子，找到不饱和结点
    QueuePush(&q, cur->lchild);
    flag = 1;
    }
    else if (cur->rchild) {//只有右孩子，一定不是完全二叉树
    break;
    }
    else {//叶子结点
    flag = 1;
    }
  }
  }
  QueueDestroy(&q);//销毁队列
  return isCompleteTree;
}
void BinaryTreeDestory(BTNode** root) {// 二叉树销毁
  if (*root == NULL) {
  return;
  }
  //利用后续遍历的思想进行销毁
  BinaryTreeDestory(&(*root)->lchild);
  BinaryTreeDestory(&(*root)->rchild);
  free(*root);
  *root = NULL;//将外部的实参置为空
}
void Test_BinaryTree() {//测试函数
  int array[] = { 1,2,3,-1,-1,-1,4,5,-1,-1,6 };
  int index = 0;
  BTNode* root = BinaryTreeCreate(array, sizeof(array) / sizeof(array[0]), -1, &index);//用-1代表无效元素，即这个子树不存在
  BTNode* ret = NULL;
  if (BinaryTreeComplete(root)) {
  printf("是完全二叉树。\n");
  }
  else {
  printf("不是完全二叉树。\n");
  }
  printf("前序遍历:");
  BinaryTreePrevOrder(root);
  printf("\n");
  printf("中序遍历:");
  BinaryTreeInOrder(root);
  printf("\n");
  printf("后序遍历:");
  BinaryTreePostOrder(root);
  printf("\n");
  printf("层序遍历:");
  BinaryTreeLevelOrder(root);
  printf("二叉树中总节点个数：%d\n", BinaryTreeSize(root));
  printf("二叉树中叶子节点个数：%d\n", BinaryTreeLeafSize(root));
  if (ret = BinaryTreeFind(root, 5))
  {
  printf("%d 在二叉树中\n", ret->data);
  }
  else
  {
  printf("%d 不在二叉树中\n", 5);
  }
  if (ret = BinaryTreeFind(root, 15))
  {
  printf("%d 在二叉树中\n", ret->data);
  }
  else
  {
  printf("%d 不在二叉树中\n", 15);
  }
  printf("二叉树的高度：%d\n", BinaryHeight(root));
  printf("二叉树第%d层节点个数%d\n", 3, BinaryTreeLevelKSize(root, 3));
  printf("二叉树第%d层节点个数%d\n", 10, BinaryTreeLevelKSize(root, 10));
  BinaryTreeDestory(&root);//销毁二叉树
}

数据结构——二叉树

一、概念

1.定义

2.特性

3.特殊的二叉树

3.1满二叉树

3.2完全二叉树

4.二叉树的性质

5.二叉树的存储结构

5.1顺序存储

5.2链式存储

二、结构体定义

三、接口实现

1.通过前序遍历数组构建二叉树

2.二叉树的查找

3.统计二叉树结点个数

4.统计二叉树叶子结点个数

5.统计二叉树第k层结点个数

6.求二叉树高度

7.二叉树前序遍历

8.二叉树中序遍历

9.二叉树后序遍历

10.二叉树层序遍历

11.判断二叉树是否是完全二叉树

12.二叉树的销毁

四、接口测试

1.测试函数

2.测试结果

五、完整代码

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

数据结构——二叉树

一、概念

1.定义

2.特性

3.特殊的二叉树

3.1满二叉树

3.2完全二叉树

4.二叉树的性质

5.二叉树的存储结构

5.1顺序存储

5.2链式存储

二、结构体定义

三、接口实现

1.通过前序遍历数组构建二叉树

2.二叉树的查找

3.统计二叉树结点个数

4.统计二叉树叶子结点个数

5.统计二叉树第k层结点个数

6.求二叉树高度

7.二叉树前序遍历

8.二叉树中序遍历

9.二叉树后序遍历

10.二叉树层序遍历

11.判断二叉树是否是完全二叉树

12.二叉树的销毁

四、接口测试

1.测试函数

2.测试结果

五、完整代码

热门文章

最新文章

相关课程

相关电子书