【数据结构】二叉树的实现-阿里云开发者社区

一、二叉树我们需要实现的功能

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);

二、以下为具体功能的实现

1.创建新节点

该步骤创建一个新节点

typedef char BTDataType;
typedef struct BinaryTree
{
    BTDataType data;
    struct BinaryTreeNode* left;
  struct BinaryTreeNode* right;
}BTNode;

2.构建二叉树

通过数组构建二叉树

1. // 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
2. BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);

前序遍历：先遍历根，再遍历左子树和右子树

注:该步骤：当数组内容为#或者数组已经访问完，都应该返回NULL,当该数组中的内容不为‘#并且数组并未执行完毕，则开辟一块新的空间，类型为BTNode，此时根节点的数据为数组中的内容，并对其进行后置访问，根节点的左节点和根节点的右节点，分别进行遍历，最后我们返回根节点

BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
  if (a[*pi] == NULL || (*pi) >= n)
  {
    a[(*pi)++];
    return NULL;
  }
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL)
  {
    perror("fail:malloc");
    return;
  }
  root->data = a[(*pi)++];
  root->left = BinaryTreeCreate(a,n,pi);
  root->right = BinaryTreeCreate(a,n,pi);
  return root;
}

3、二叉树的销毁

注：当根节点为空时，我们对其直接进行放回，如果根节点不为空，我们对其进行遍历，访问到最后一个节点，我们对其返回释放

void BinaryTreeDestory(BTNode* root)
{
    if (root == NULL)
    return;
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  //printf("%p %c\n", root, root->data);
  free(root);
}

4.二叉树节点个数和二叉树叶子节点的个数

注：二叉树节点个数，如果根节点为空，则返回0，若根节点不为空我们，对其左右子树进行遍历，并且其往回进行遍历时，我们进行+1操作，最后的返回值即为二叉树节点的个数

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

5.前中后序遍历：二叉树的遍历

在之前我已经写过相关内容的博客，可以点击上面链接直接进行查看

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

6. 二叉树查找值为x的节点

注：查找第k层，我们将我们的问题化为小问题，也就是我们第一层的结点需要往下找k-1层，第二层的结点需要往下找k-2层，以此类推，只有当我们的k为1的时候返回的就是我们需要找的k层的结点的个数的总和

// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  if (ret1)
    return ret1;
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret2)
    return ret2;
  return NULL;
}

7.层序遍历

注：此时我们采用非递归的方式进行实现，主要用到了队列，我们清楚队列，是先进先出的方式，我们将数据存储进队列当中，再对其进行取出

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct
{
  QNode* head;
  QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//放数据
void QueuePush(Queue* pq, QDataType x);
//删除
void QueuePop(Queue* pq);
//长度
int QueueSize(Queue* pq);
//取头
QDataType QueueFront(Queue* pq);
//取尾
QDataType QueueBack(Queue* pq);
//判断空
bool QueueEmpty(Queue* pq);

Queue.c

#include"queue.h"
//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//放数据
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //开辟空间
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  //添加数据
  newnode->data = x;
  newnode->next = NULL;
  //链接
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//判断空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
//删除
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}
//取头
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//取尾
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//长度
int QueueSize(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  int count = 0;
  while (cur)
  {
    ++count;
    cur = cur->next;
  }
  return count;
}

层序遍历的实现

注：先创建一个队列，对其进行初始化，如果根节点不为空，我们将其放入新创建的队列当中，我们将队列进行循环处理，取出队列当中的首元素，对其进行打印，并销毁，再对二叉树进行递归放入队列当中，如果根节点的左子树中存在数据，我们将其取出放入队列中，如果二叉树的根节点的右子树中，包含数据，我们也对其进行取出放入队列当中，再对队列，进行首元素提取，打印，打印完之后再对该元素进行销毁

void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueuePush(&q, root);
  }
  //如果队列不为空，进入。
  while (!QueueEmpty(&q))
  {
    //取出 打印 
    BTNode* front = QueueFront(&q);
    printf("%c ", front->data);
    QueuePop(&q);
    if (front->left)
    {
      QueuePush(&q, front->left);
    }
    if (front->right)
    {
      QueuePush(&q, front->right);
    }
  }
  printf("\n");
  //销毁队列
  QueueDestroy(&q);
}

8.判断是否为完全二叉树

1.如果后面全是空，则是完全二叉树；

2.如果后面还有非空，则不是完全二叉树。

int BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front)
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
    else
    {
      //遇到NULL，跳出。
      break;
    }
  }
  //1.如果后面全是空，则是完全二叉树；
  //2.如果后面还有非空，则不是完全二叉树。
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}

代码汇总：

bt.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
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);

bt.c

#include"bt.h"
#include"queue.h"
// 通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
  if (a[*pi] == NULL || (*pi) >= n)
  {
    a[(*pi)++];
    return NULL;
  }
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL)
  {
    perror("fail:malloc");
    return;
  }
  root->data = a[(*pi)++];
  root->left = BinaryTreeCreate(a,n,pi);
  root->right = BinaryTreeCreate(a,n,pi);
  return root;
}
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
  {
    return;
  }
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
}
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  return 1 + BinaryTreeSize(root->left) + BinaryTreeSize(root->right);
}
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left == NULL && root->right)
    return 1;
  return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);
}
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{
  assert(k >= 1);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);
}
// 二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  BTNode* ret1 = BinaryTreeFind(root->left, x);
  if (ret1)
    return ret1;
  BTNode* ret2 = BinaryTreeFind(root->right, x);
  if (ret2)
    return ret2;
  return NULL;
}
// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root)
{
  if (root == NULL)
    return;
  printf("%c ", root->data);
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
}
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreePrevOrder(root->left);
  printf("%c ", root->data);
  BinaryTreePrevOrder(root->right);
}
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreePrevOrder(root->left);
  BinaryTreePrevOrder(root->right);
  printf("%c ", root->data);
}
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root != NULL)
  {
    //如果根节点不为空，我们对其进行存储
    QueuePush(&q,root);
  }
  while (!QueueEmpty(&q))
  {
    //取出 打印
    BTNode* front = QueueFront(&q);
    printf("%c",front->data);
    QueuePop(&q);
    if (front->left)
    {
      QueuePush(&q,front->left);
    }
    if (front->right)
    {
      QueuePush(&q,front->right);
    }
  }
  printf("\n");
  QueueDestroy(&q);
}
// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BTNode* root)
{
  Queue q;
  QueueInit(&q);
  if (root)
  {
    QueuePush(&q, root);
  }
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front)
    {
      QueuePush(&q, front->left);
      QueuePush(&q, front->right);
    }
    else
    {
      //遇到NULL，跳出。
      break;
    }
  }
  //1.如果后面全是空，则是完全二叉树；
  //2.如果后面还有非空，则不是完全二叉树。
  while (!QueueEmpty(&q))
  {
    BTNode* front = QueueFront(&q);
    QueuePop(&q);
    if (front)
    {
      QueueDestroy(&q);
      return false;
    }
  }
  QueueDestroy(&q);
  return true;
}

Queue.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//前置声明
struct BinaryTreeNode;
typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
  struct QueueNode* next;
  QDataType data;
}QNode;
typedef struct
{
  QNode* head;
  QNode* tail;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//放数据
void QueuePush(Queue* pq, QDataType x);
//删除
void QueuePop(Queue* pq);
//长度
int QueueSize(Queue* pq);
//取头
QDataType QueueFront(Queue* pq);
//取尾
QDataType QueueBack(Queue* pq);
//判断空
bool QueueEmpty(Queue* pq);

Queue.c

#include"queue.h"
//初始化
void QueueInit(Queue* pq)
{
  assert(pq);
  pq->head = pq->tail = NULL;
}
//销毁
void QueueDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->head = pq->tail = NULL;
}
//放数据
void QueuePush(Queue* pq, QDataType x)
{
  assert(pq);
  //开辟空间
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    printf("malloc fail\n");
    exit(-1);
  }
  //添加数据
  newnode->data = x;
  newnode->next = NULL;
  //链接
  if (pq->tail == NULL)
  {
    pq->head = pq->tail = newnode;
  }
  else
  {
    pq->tail->next = newnode;
    pq->tail = newnode;
  }
}
//判断空
bool QueueEmpty(Queue* pq)
{
  assert(pq);
  return pq->head == NULL;
}
//删除
void QueuePop(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  if (pq->head->next == NULL)
  {
    free(pq->head);
    pq->head = pq->tail = NULL;
  }
  else
  {
    QNode* next = pq->head->next;
    free(pq->head);
    pq->head = next;
  }
}
//取头
QDataType QueueFront(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->head->data;
}
//取尾
QDataType QueueBack(Queue* pq)
{
  assert(pq);
  assert(!QueueEmpty(pq));
  return pq->tail->data;
}
//长度
int QueueSize(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->head;
  int count = 0;
  while (cur)
  {
    ++count;
    cur = cur->next;
  }
  return count;
}

Test.c

#include"bt.h"
#include"queue.h"
int main()
{
    char ch[] = "ABD##E#H##CF##G##";
    //gets(ch);
    int n = strlen(ch);
    int i = 0;
    //BinaryTreeCreate
    BTNode* root = BinaryTreeCreate(ch, n, &i);
    //进行前序遍历，输出遍历结果。
    BinaryTreePrevOrder(root);
    printf("\n");
    //进行中序遍历，输出遍历结果。
    BinaryTreeInOrder(root);
    printf("\n");
    //进行后序遍历，输出遍历结果。
    BinaryTreePostOrder(root);
    printf("\n");
    //结点个数
    int ret = BinaryTreeSize(root);
    printf("%d\n", ret);
    //叶结点的个数
    int ret1 = BinaryTreeLeafSize(root);
    printf("%d\n", ret1);
    //第k个结点
    int ret2 = BinaryTreeLevelKSize(root, 2);
    printf("%d\n", ret2);
    //借用队列实现层序遍历
    BinaryTreeLevelOrder(root);
    // 判断二叉树是否是完全二叉树
    int ret3 = BinaryTreeComplete(root);
    printf("%d\n", ret3);
    BTNode* c = BinaryTreeFind(root, ch[2]);
    printf("%c", c->data);
    BinaryTreeDestory(root);
    root = NULL;
    return 0;
}

【数据结构】二叉树的实现