二叉树链式结构-阿里云开发者社区

1.前置说明

我们手动构建一棵二叉树：

注意：上述代码并不是创建二叉树的方式

从概念中可以看出，二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的

2.二叉树的遍历

2.1前序、中序以及后序遍历

学习二叉树结构，最简单的方式就是遍历

所谓二叉树遍历(Traversal)是按照某种特定的规则，依次对二叉树中的节点进行相应的操作，并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题

遍历是二叉树上最重要的运算之一，也是二叉树上进行其它运算的基础

其实可以这样理解：

前序遍历：根->左子树->右子树

中序遍历：左子树->根->右子树

后序遍历：左子树->右子树->根

以下面这个二叉树为例：

前序遍历：1->2->3->4->5->6
中序遍历：3->2->1->5->4->6
后序遍历：3->2->5->6->4->1

由于被访问的结点必是某子树的根，所以N(Node）、L(Left subtree）和R(Right subtree）又可解释为根、根的左子树和根的右子树

NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历

遍历的实现需要用到递归

2.2前序遍历

代码实现是这样的：

2.3中序遍历

2.4后序遍历

2.5层序遍历

层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。

设二叉树的根节点所在层数为1，层序遍历就是从所在二叉树的根节点出发，首先访问第一层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历

我们可以利用队列先进先出的特点来实现：

定义一个q队列
如果root不为空，则将root入队列
用front来保存队头数据，将队头数据pop，打印队头数据；然后遍历下一层：如果左孩子不为空，左孩子入队列；右孩子不为空，右孩子入队列；当队列不为空则继续遍历下一层，直到队列为空退出循环

关于这块的指针问题，我们画图解释一下

我们修改val也为BTNode*类型

分层打印

我们可以定义一个levelsize保存每一层的数据个数，控制一层一层打印

队列的size就是下一层的数据个数

效果是这样的

3.节点个数

3.1二叉树的节点个数

3.1叶子节点个数

4.求树的高度

如果为空返回0
不为空左子树和右子树高度更高的那个+1

5.求第k层的节点个数

如果为空返回0
如果不为空且k=1 返回1
如果不为空且k>1 返回左子树的k-1层+右子树的k-1层

5.查找值为x的节点

6.构建一棵链式二叉树

假设给一个前序遍历的数组，将其构建成一棵二叉树

7.判断完全二叉树

完全二叉树的节点都是连续的，所以不可能出现一个NULL节点的后面存在非空节点的情况，我们用层序遍历的思路，入队列的时候不管是不是NULL节点都入队列，出队列的时候如果遇到NULL节点，则停止出队列，判断后面是否还有非空节点，我们用while循环来控制，如果队列不为空则出队列，如果队头数据有不为空的情况，则返回false

8.销毁二叉树

销毁我们为了防止形成野指针，从下往上，从左往右，即后序遍历依次销毁

代码示例

Queue

Queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
//创建
typedef struct BTNode* QDataType;
typedef struct QueueNode
{
  QDataType val;
  struct QueueNode* next;
}QNode;
typedef struct Queue
{
  QNode* phead;
  QNode* ptail;
  int size;
}Queue;
//把队列的头尾封装在一个结构体中
//初始化
void QInit(Queue* pq);
//销毁
void QDestroy(Queue* pq);
//入队列
void QPush(Queue* pq, QDataType x);
//出队列
void QPop(Queue* pq);
//取队头数据
QDataType QFront(Queue* pq);
//取队尾数据
QDataType QBack(Queue* pq);
//判空
bool QEmpty(Queue* pq);
//返回队列有效元素个数
int QSize(Queue* pq);

Queue.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
//初始化
void QInit(Queue* pq)
{
  assert(pq);
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
//销毁
void QDestroy(Queue* pq)
{
  assert(pq);
  QNode* cur = pq->phead;
  while (cur)
  {
    QNode* next = cur->next;
    free(cur);
    cur = next;
  }
  pq->phead = pq->ptail = NULL;
  pq->size = 0;
}
//入队列
void QPush(Queue* pq, QDataType x)
{
  assert(pq);
  //创建newnode
  QNode* newnode = (QNode*)malloc(sizeof(QNode));
  if (newnode == NULL)
  {
    perror("malloc fail");
    return;
  }
  newnode->val = x;
  newnode->next = NULL;
  if (pq->ptail == NULL)
  {
    pq->phead = pq->ptail = newnode;
  }
  else
  {
    pq->ptail->next = newnode;
    pq->ptail = newnode;
  }
  pq->size++;
}
//出队列
void QPop(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
  QNode* del = pq->phead;
  pq->phead = pq->phead->next;
  free(del);
  del = NULL;
  if (pq->phead == NULL)
  {
    pq->ptail = NULL;
    //防止ptail成为野指针
  }
  pq->size--;
}
//取队头数据
QDataType QFront(Queue* pq)
{
  assert(pq);
  assert(pq->phead);
  return pq->phead->val;
}
//取队尾数据
QDataType QBack(Queue* pq)
{
  assert(pq);
  assert(pq->ptail);
  return pq->ptail->val;
}
//判空
bool QEmpty(Queue* pq)
{
  assert(pq);
  return pq->phead == NULL;
}
//返回队列有效元素个数
int QSize(Queue* pq)
{
  assert(pq);
  return pq->size;
}

TreeNode

TreeNode.c

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
#include "Queue.h"
//创建
typedef char BTDataType;
typedef struct BTNode
{
  BTDataType data;
  struct BTNode* left;
  struct BTNode* right;
}BTNode;
//BTNode* BuyNode(BTDataType x)
//{
//  BTNode* node = (BTNode*)malloc(sizeof(BTNode));
//  node->data = x;
//  node->left = NULL;
//  node->right = NULL;
//  return node;
//}
//构建二叉树
BTNode* BTCreate(BTDataType*a,int*pi)
{
  if (a[*pi] == '#')
  {
    (*pi)++;
    return NULL;
  }
  BTNode* root = (BTNode*)malloc(sizeof(BTNode));
  if (root == NULL)
  {
    perror("malloc fail");
    exit(-1);
  }
  root->data = a[(*pi)++];
  root->left = BTCreate(a,pi);
  root->right = BTCreate(a,pi);
  return root;
}
//先序遍历
void BTPrevOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("# ");
    return;
  }
  printf("%c ", root->data);
  BTPrevOrder(root->left);
  BTPrevOrder(root->right);
}
//中序遍历
void BTInOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("# ");
    return;
  }
  BTInOrder(root->left);
  printf("%c ", root->data);
  BTInOrder(root->right);
}
//后序遍历
void BTPostOrder(BTNode* root)
{
  if (root == NULL)
  {
    printf("# ");
    return;
  }
  BTPostOrder(root->left);
  BTPostOrder(root->right);
  printf("%c ", root->data);
}
// 层序遍历
void BTLevelOrder(BTNode* root)
{
  Queue q;
  QInit(&q);
  if (root)
    QPush(&q, root);
  int levelsize = 1;
  while (!QEmpty(&q))
  {
    while (levelsize--)
    {
      BTNode* front = QFront(&q);
      QPop(&q);
      printf("%c ", front->data);
      if (front->left)
        QPush(&q, front->left);
      if (front->right)
        QPush(&q, front->right);
    }
    printf("\n");
    levelsize = QSize(&q);
  }
  printf("\n");
  QDestroy(&q);
}
//判断完全二叉树
bool BTComplete(BTNode* root)
{
  Queue q;
  QInit(&q);
  if (root)
    QPush(&q, root);
  int levelsize = 1;
  while (!QEmpty(&q))
  {
    BTNode* front = QFront(&q);
    QPop(&q);
    if (front == NULL)
      break;
    QPush(&q, front->left);
    QPush(&q, front->right);
  }
  while (!QEmpty(&q))
  {
    BTNode* front = QFront(&q);
    QPop(&q);
    if (front)
    {
      QDestroy(&q);
      return false;
    }
  }
  QDestroy(&q);
  return true;
}
//销毁
void BTDestroy(BTNode* root)
{
  if (root == NULL)
    return;
  BTDestroy(root->left);
  BTDestroy(root->right);
  free(root);
}
//二叉树结点个数
//static int size = 0;
int BTSize(BTNode* root)
{
  /*if (root == NULL)
  {
    return;
  }
  ++size;
  BTSize(root->left);
  BTSize(root->right);
  return size;*/
  return root == NULL ? 0 : 
    BTSize(root->left) + 
    BTSize(root->right)+1;
}
//叶子节点个数
int BTLSize(BTNode* root)
{
  /*if (root == NULL)
  {
    return 0;
  }
  return root->left == NULL && root->right == NULL ? 1:
    BTLSize(root->left) + BTLSize(root->right);*/
  return (root == NULL ? 0 : 
    (root->left == NULL && root->right == NULL ? 1 :
    BTLSize(root->left) + BTLSize(root->right)));
}
//求树的高度
int BTHeight(BTNode* root)
{
  if (root == NULL)
    return 0;
  int leftHeight = BTHeight(root->left);
  int rightHeight = BTHeight(root->right);
  return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
//求第k层的节点个数
int BTLKSize(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  return BTLKSize(root->left, k - 1) + BTLKSize(root->right, k - 1);
}
//查找值为x的节点
BTNode* BTFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->data == x)
    return root;
  BTNode* leftnode = BTFind(root->left, x);
  if (leftnode)
    return leftnode;
  BTNode* rightnode = BTFind(root->right, x);
  if (rightnode)
    return rightnode;
  return NULL;
}
int main()
{
  //char a[] = "ABD##E#H##CF##G##";
  char a[] = "ABC##D##EF##G##";
  int i = 0;
  BTNode* root = BTCreate(a,&i);
  BTPrevOrder(root);
  printf("\n");
  BTInOrder(root);
  printf("\n");
  BTPostOrder(root);
  printf("\n");
  int size1 = BTSize(root);
  printf("%d\n", size1);
  int size2 = BTSize(root);
  printf("%d\n", size2);
  int size3 = BTLSize(root);
  printf("%d\n", size3);
  int h = BTHeight(root);
  printf("%d\n", h);
  int s = BTLKSize(root, 3);
  printf("%d\n", s);
  BTLevelOrder(root);
  printf("%d\n", BTComplete(root));
  BTDestroy(root);
  root = NULL;
  return 0;
}

二叉树链式结构