数据结构——二叉树的链式结构

简介: 数据结构——二叉树的链式结构


一、二叉树的创建

这里我们使用先序遍历的思想来创建二叉树,这里的内容对于刚接触二叉树的朋友可能有些难理解,不妨先看完下面的二叉树各种遍历再来看创建就会简单很多,为了保持文章的整体性,先讲二叉树的创建。

当然为了后续内容能够衔接,我们先手动创建一个固定的树,就是上面这棵树,后续内容全部围绕这棵树

typedef int DataType;
typedef struct TreeNode
{
  DataType data;
  struct  TreeNode* left;
  struct  TreeNode* right;
}TreeNode;
TreeNode* BuyNode(int x)
{
  TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
  if (node == NULL)
  {
    perror("malloc fail:");
    return NULL;
  }
  node->data = x;
  node->left = node->right = NULL;
}
  
TreeNode* CreatTree()
{
  TreeNode* node1 = BuyNode(1);
  TreeNode* node2 = BuyNode(2);
  TreeNode* node3 = BuyNode(3);
  TreeNode* node4 = BuyNode(4);
  TreeNode* node5 = BuyNode(5);
  TreeNode* node6= BuyNode(6);
  node1->left = node2;
  node1->right = node4;
  node2->left = node3;
  node4->left = node5;
  node4->right = node6;
  return node1;
}

现在开始讲如何用前序遍历方式来进行创建二叉树,这里给俩种创建方法。

1.1  返回根节点指针创建

注:我们用前序遍历方式输入数字,-1代表空,上面的二叉树可写为:1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1

TreeNode* CreatTree()
{
  int i;
  scanf("%d", &i);
  
  if (i == -1)
  {
    return NULL;
  }
  TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
  if (root == NULL)
  {
    perror("malloc fail:");
    exit(-1);
  }
  root->data = i;
  root->left =  CreatTree();
  root->right = CreatTree();
  return root;
}

注:return root 是不能省略的,递归返回时,遇到空返回;或者构建完子数,返回根节点,作为上一级左子树,构建完子树,返回根节点,作为上一级右子树,依次递归回去,直到返回整个数的根节点

1.2 二级指针传参创建

同样的,依然构建上面的而二叉树,用前序遍历方式输入数字,-1代表空,上面的二叉树可写为:1 2 3 -1 -1 -1 4 5 -1 -1 6 -1 -1

void CreatTree(TreeNode** root)
{
  int i;
  scanf("%d", &i);
  if (i == -1)
  {
    *root = NULL;
  }
  else
  {
    *root = (TreeNode*)malloc(sizeof(TreeNode));
    if (*root == NULL)
    {
      perror("malloc fail:");
      exit(-1);
    }
    (*root)->data = i;
    CreatTree(&((*root)->left));
    CreatTree(&((*root)->right));
  }
}

注:二级指针传参可以改变一级指针的指向,同样的,这里创建好根节点后,创造左子树,在创造右子树,依次递归下去。

二、二叉树的遍历

我们先从最简单的操作----遍历学起。所谓二叉树遍历(Traversal)就是按照某种特定的规则,依次对二叉树中的结点进行相应的操作,并且每个节点有且只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。二叉树的遍历分为四种:前序遍历、中序遍历、后序遍历和层序遍历。

2.1 前序遍历

前序遍历(Preorder Traversal)又称先根遍历,即先遍历根结点,再遍历左子树,最后遍历右子树。而对于子树的遍历,也服从上述规则。利用递归,我们可以很快地写出代码:

// 二叉树前序遍历
void PreOrder(TreeNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return ;
  }
  printf("%d ", root->data);
   PreOrder(root->left);
   PreOrder(root->right);
}

便于我们更好的理解,我们画出递归展开图

2.2 中序遍历

中序遍历(Inorder Traversal)又称中根遍历,即先遍历左子树,再遍历根结点,最后遍历右子树。同样,子树的遍历规则也是如此。递归代码如下:

// 二叉树中序遍历
void InOrder(TreeNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return ;
  }
  
  InOrder(root->left);
  printf("%d ", root->data);
  InOrder(root->right);
}

2.3 后序遍历

后序遍历(Inorder Traversal)又称后根遍历,即先遍历左子树,再遍历右子树,最后遍历根结点递归代码如下:

// 二叉树后序遍历
void PostOrder(TreeNode* root)
{
  if (root == NULL)
  {
    printf("NULL ");
    return ;
  }
  PostOrder(root->left);
  
  PostOrder(root->right);
  printf("%d ", root->data);
}

2.4  层序遍历

除了先序遍历、中序遍历、后序遍历外,还可以对二叉树进行层序遍历。设二叉树的根节点所在

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

层序遍历借助队列实现,思路解析图如下:

//层序遍历
void LevelOrder(TreeNode* root)
{
  Queue pq;
  QueueInit(&pq);
  if (root == NULL)
  {
     QueueDestroy(&pq);
    return;
  }
  QueuePush(&pq,root);
  while (!QueueEmpty(&pq))
  {
    TreeNode* front= QueueFront(&pq);
    printf("%d ", front->data);
     QueuePop(&pq);
     if (front->left!= NULL)
     {
       QueuePush(&pq, front->left);
       
     }
     if (front->right != NULL)
     {
       QueuePush(&pq, front->right);
     }
  }
  
  QueueDestroy(&pq);
}

思考:当然层序遍历这里有一个变形,我们能不能将二叉树每一层打印单独放一行,该怎么做呢?

思路:

(1)设二叉树的根节点所在层数为1,第一层根节点进队列,队列元素个数为1,size==1
(2)每出队列一次,size--,根节点出完队列,俩个子节点进队列,此时队列元素个数为第二层节点个数,size==2
(3)当我们出队列size次,把第二层元素出完,队列剩下的元素是第三层节点,size==QueueSize
以此类推,以size为循环条件,则可实现每层单独打印一行

void LevelOrder(TreeNode* root)
{
  Queue pq;
  QueueInit(&pq);
  if (root == NULL)
  {
    QueueDestroy(&pq);
    return;
  }
  QueuePush(&pq,root);
  int size = 1;
  while (!QueueEmpty(&pq))
  {
    while (size--)
    {
      TreeNode* front = QueueFront(&pq);
      printf("%d ", front->data);
      QueuePop(&pq);
      if (front->left != NULL)
      {
        QueuePush(&pq, front->left);
      }
      if (front->right != NULL)
      {
        QueuePush(&pq, front->right);
      }
    }
    size = QueueSize(&pq);
    printf("\n");
  }
  
  QueueDestroy(&pq);
}

三、二叉树的结点

3.1 二叉树的总结点数

一颗二叉树的结点数我们可以看作是根结点+左子树结点数+右子树结点数,那左右子树的结点数又是多少呢?按照相同的方法继续拆分,层层递归直到左右子树为空树,返回空树的结点数0即可。递归代码如下:

// 二叉树节点个数
int TreeSize(TreeNode* root)
{
  return root == NULL? 0 : TreeSize(root->left) + TreeSize(root->right) + 1;
}

3.2 二叉树的叶子结点数

左右子树都为空的结点即是叶子结点。这里分为两种情况:左右子树都为空和左右子树不都为空。

(1)当左右子树都为空时,则这颗树的叶子结点数为1(根节点)。

(2)当左右子树不都为空,即根结点不是叶子结点时,这棵树的叶子结点数就为左子树叶子结点数+右子树叶子结点数(空树没有叶子结点)。

 

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

3.3 二叉树第k层结点数

一颗树第k层的结点数我们可以拆分为其左子树第k-1层结点+右子树第k-1层结点(注:当前节点为第一层)

(1)若为空树,无论哪层节点数都是0

(2)若不是空树且k==1,则只有一个节点(根节点)

// 二叉树第k层节点个数
int TreeLevelKSize(TreeNode* root, int k)
{
  assert(k > 0);
  if (root!=NULL&&k == 1)
  {
    return 1;
  }
  if (root == NULL)
  {
    return 0;
  }
  if (k > 1)
  {
    return TreeLevelKSize(root->left, k - 1) + TreeLevelKSize(root->right, k - 1);
  }
}
// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{
  Queue pq;
  QueueInit(&pq);
  if (root == NULL)
  {
    QueueDestroy(&pq);
    return;
  }
  QueuePush(&pq, root);
  
  while (!QueueEmpty(&pq))
  {
    
      TreeNode* front = QueueFront(&pq);
      
      QueuePop(&pq);
      if (front == NULL)
      {
        break;
      }
        QueuePush(&pq, front->left);
      
        QueuePush(&pq, front->right);
      
  }
  while (!QueueEmpty(&pq))
  {
    TreeNode* front = QueueFront(&pq);
    QueuePop(&pq);
    if (front != NULL)
    {
      return false;
    }
  }
  QueueDestroy(&pq);
  return true;
}

四、二叉树的查找

二叉树的查找本质上就是一种遍历,只不过是将之前的打印操作换为查找操作而已。我们可以使用前序遍历来进行查找:

(1)先比较根结点是否为我们要查找的结点,如果是,返回根节点地址

(2)如果不是,遍历左子树,如果左子树是,直接返回节点地址;不是则遍历右子树,如果右子树是,直接返回节点地址,不是返回空,说明左右子树都没找到。

// 二叉树查找值为x的节点
TreeNode* TreeFind(TreeNode* root, DataType x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->data == x)
  {
    return root;
  }
  TreeNode* node1 = TreeFind(root->left, x);
  if (node1)
  {
    return node1;
  }
  TreeNode* node2 = TreeFind(root->right, x);
  if (node2)
  {
    return node2;
  }
  return NULL;
}

五、二叉树的高度/深度

树中结点的最大层次称为二叉树的高度。因此,一颗二叉树的高度我们可以看作是

1(根结点)+左右子树高度的较大值。层层递归下去直到遇到空树返回0即可,

这里值得注意的是:不要写成

return TreeHeight(root->left)>TreeHeight(root->right) ? 
    TreeHeight(root->left)+1:TreeHeight(root->right)+1;
}
这里比较好左右子树较大的一颗后,又会从新递归较大那颗子树高度,会造成重复计算,时间复杂度增高。

我们要保存好左右子树层数,避免重复计算,代码如下:

//二叉树的高度
int TreeHeight(TreeNode* root)
{
  if (root == NULL)
  {
    return 0;
  }
  int left = TreeHeight(root->left);
  int right = TreeHeight(root->right);
  return  left>right ? 
    left+1:right+1;
}

六、完全二叉树的判断

这里的思路利用了层序遍历,不同的是,将空节点指针也入队列,当我们遇到第一个空节点指针则退出循环,然后对队列进行检测,若第一个空节点指针以后全都是空,则为完全二叉树,反之,不为完全二叉树。

注:当在队列遇到第一个空节点指针时,二叉树中空节点指针之后所有非空节点指针全部进队列

思路解析图如下:

代码如下:

// 判断二叉树是否是完全二叉树
bool TreeComplete(TreeNode* root)
{
  Queue pq;
  QueueInit(&pq);
  if (root == NULL)
  {
    QueueDestroy(&pq);
    return;
  }
  QueuePush(&pq, root);
  
  while (!QueueEmpty(&pq))
  {
    
      TreeNode* front = QueueFront(&pq);
      
      QueuePop(&pq);
      if (front == NULL)
      {
        break;
      }
        QueuePush(&pq, front->left);
      
        QueuePush(&pq, front->right);
      
  }
  while (!QueueEmpty(&pq))
  {
    TreeNode* front = QueueFront(&pq);
    QueuePop(&pq);
    if (front != NULL)
    {
      return false;
    }
  }
  QueueDestroy(&pq);
  return true;
}

七、二叉树的销毁

7.1 一级指针传参销毁

同样的,和创建节点一样,我们给出俩个销毁方式:

(1)一种是传一级指针方式,这种方式不是改变根节点的指向,需要在销毁函数结束后,将root置为NULL

void TreeDestroy(TreeNode* root)//出来将root=NULL
{
  if (root == NULL)
  {
    return;
  }
  TreeDestroy(root->left);
  TreeDestroy(root->right);
  free(root);
}

7.2 二级指针传参销毁

(2)另一种是传二级指针,直接在函数内部将每一个销毁的节点指针置为NULL.

void TreeDestroy(TreeNode** root)
{
  if (*root == NULL)
  {
    return;
  }
  TreeDestroy(&(*root)->left);
  TreeDestroy(&(*root)->right);
  free(*root);
  *root = NULL;
}

总结:本篇文章将二叉树的基础知识差不多囊括了,后续的话还需要大量练习做巩固加强,递归比较抽象难以理解,需要动手画递归展开图进行帮助理解。

希望大家阅读完可以有所收获,同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言,百题一定会认真阅读!

相关文章
|
2天前
|
Java
JAVA数据结构刷题 -- 二叉树进阶
JAVA数据结构刷题 -- 二叉树进阶
8 0
|
2天前
|
存储 Java
JAVA数据结构刷题 -- 力扣二叉树
JAVA数据结构刷题 -- 力扣二叉树
8 0
TU^
|
3天前
|
存储 机器学习/深度学习 算法
数据结构~~二叉树-堆
树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因 为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
TU^
11 1
|
3天前
|
索引
[数据结构]——二叉树链式结构的实现
[数据结构]——二叉树链式结构的实现
|
3天前
|
算法
[数据结构]——二叉树——堆排序
[数据结构]——二叉树——堆排序
|
3天前
|
存储 算法 索引
[数据结构]——二叉树——堆的实现
[数据结构]——二叉树——堆的实现
|
3天前
|
存储 算法
[数据结构]—二叉树基本概念
[数据结构]—二叉树基本概念
|
3天前
|
存储 算法
数据结构实验(四)二叉树的基本操作
数据结构实验(四)二叉树的基本操作
|
3天前
|
存储
数据结构-二叉树
数据结构-二叉树
11 0
TU^
|
3天前
|
存储 调度 索引
数据结构~~栈和队列
在计算机科学中,数据结构是构建高效程序的基础。栈和队列是两种重要且常用的线性数据结构,它们在解决各种问题中发挥着关键作用。
TU^
13 1