数据结构第六课 -----链式二叉树的实现

简介: 数据结构第六课 -----链式二叉树的实现

二叉树

前面粗略的介绍了二叉树

二叉树主要有两种 空树和非空树

而非空树拆分为 : 根节点 和左子树和右子树

二叉树的性质


  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有 2^(i-1)个结点.
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h -1 .
  3. 对任何一棵二叉树, 如果度为0其叶结点个数为n0 , 度为2的分支结点个数为n2 ,则有 n0= n2+1
  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度,h=log(n+1) . (ps: 是log以2为底,n+1为对数)
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:


  1. 若i>0,i位置节点的双亲序号:(i-1)/2;i=0,i为根节点编号,无双亲节点
  2. 若2i+1<n,左孩子序号:2i+1,2i+1>=n否则无左孩子
  3. 若2i+2<n,右孩子序号:2i+2,2i+2>=n否则无右孩子


二叉树的遍历

学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。


按照规则,二叉树的遍历有:前序/中序/后序的递归结构遍历:


  1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。(根 ->左 ->右)
  2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。(左->根->右)
  3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。(左->右->根)

为此特意构建一个二叉树

#include<stdio.h>
#include<stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
  BTDataType* val;
  struct BinaryTreeNode* left;
  struct BinaryTreeNode* rigth;

}BinaryTreeNode;
BinaryTreeNode* CreateNode(BTDataType elemest)
{
  BinaryTreeNode* p = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
  if (p == NULL)
  {
    perror("malloc");
    return -1;
  }
  p->val = elemest;
  return p;
}
int main()
{
  BinaryTreeNode* n1 = CreateNode(1);
  BinaryTreeNode* n2 = CreateNode(2);
  BinaryTreeNode* n3 = CreateNode(3);
  BinaryTreeNode* n4 = CreateNode(4);
  BinaryTreeNode* n5 = CreateNode(5);
  BinaryTreeNode* n6 = CreateNode(6);
  n1->left = n2;
  n1->rigth = n4;
  n2->left = n3;
  n2->rigth = NULL;
  n3->left = NULL;
  n3->rigth = NULL;
  n4->left = n5;
  n4->rigth = n6;
  n5->left = NULL;
  n5->rigth = NULL;
  n6->left = NULL;
  n6->rigth = NULL;
  return 0;
}

前序遍历

我们以上面图片为例

我们可以写成:

1 2 3 N N N 4 5 N N 6 N N

代码:

void PreOrder(BinaryTreeNode* n1)
{
  if (n1 == NULL)
  {
    printf("NULL ");
    return;
  }
    

  printf("%d ", n1->val);
  PreOrder(n1->left);
  PreOrder(n1->rigth);
}

中序遍历

我们可以写成:N 3 N 2 N 1 N 5 N 4 N 6 N

代码:

void InOrdef(BinaryTreeNode* n1)
{
  if (n1 == NULL)
  {
    printf("NULL ");
    return;
  }
  PreOrder(n1->left);
  printf("%d ", n1->val);
  PreOrder(n1->rigth);
}

后序遍历

我们可以写成: N N 3 N 2 N N 5 N N 6 4 1

代码:

void PostOrder(BinaryTreeNode* n1)
{
  if (n1 == NULL)
  {
    printf("NULL ");
    return;
  }
  PreOrder(n1->left);
  PreOrder(n1->rigth);
  printf("%d ", n1->val);
}

小例子

叶子节点个数

思路:左子树的节点个数加上右子树的节点个数加上根节点

//节点个数
int TreeSize(BinaryTreeNode* n1)
{
  if (n1 == NULL)
    return 0;
  return 1 + TreeSize(n1->left) + TreeSize(n1->rigth);
}

叶节点个数

思路:左子树的叶节点个数加上右子树的叶节点个数加上根节点 需要注意的是为空树.和只有根节点的情况

//叶节点的个数
int TreeLeafSize(BinaryTreeNode* n1)
{
  //为空树
  if (n1 == NULL)
    return 0;
  //只有一个节点
  if (n1->left == NULL && n1->rigth == NULL)
    return 1;
  return TreeLeafSize(n1->left) + TreeLeafSize(n1->rigth);
}

树的高度

思路:左子树的高度和右子树高度比较,大的高度加上1就是整个二叉树的高度,需要注意的是空树情况下

int TreeHeigth(BinaryTreeNode* n1)
{
  if (n1 == NULL)
    return 0;
  if (n1->left == NULL && n1->rigth == NULL)
    return 1;
  int a = TreeHeigth(n1->left);
  int b = TreeHeigth(n1->rigth);
  return (a > b ? a : b) + 1;
}

#第k层的节点

思路: 左子树的第k-1层的节点个数 加上右子树的第k-1层的节点个数,如果k为0就是空,k=1,就是1

int NodeNum(BinaryTreeNode* n1, int k)
{
  if (n1 == NULL)
    return 0;
  if (k == 0)
    return 0;
  if (k == 1)
    return 1;
  return NodeNum(n1->left, k - 1) + NodeNum(n1->rigth, k - 1);
}

层次遍历

思路:层次遍历就是从第一层开始横向遍历

我们可以借助队列的性质,先进先出,我们先开始插入根节点,然后开始进行循环判断,只要出去的节点的左右孩子不为NULL就插入到队列,直到队列为空

// 层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode* root)
{
  //创建一个队列
  Queue Qu;
  //初始化
  QueueInit(&Qu);
  //插入的是节点,
  if (root != NULL)
    QueuePush(&Qu, root);
  while (QueueSize(&Qu))
  {
    BinaryTreeNode* from = QueueFront(&Qu);
    
    
    printf("%d ", from->val);
    //删除
    QueuePop(&Qu);
    //需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点
    if (from->left != NULL)
    {
      QueuePush(&Qu, from->left);
    }
    if (from->rigth != NULL)
    {
      QueuePush(&Qu, from->rigth);
    }
    
  }
  printf("\n");
  QueueDestroy(&Qu);
  
  
  
}

这个是打印全部的

如果要一层层的打印

思路: 我们可以定义一个变量,用来统计当前队列的个数,也就是当层的节点个数,然后每出列一个就把对应的左右孩子插入进去,然后该变量减1,直到为0,也就是该层的节点全部出列了,然后再计算出队列的长度,也就是下一层的节点个数,然后继续,直到队列的长度为0


68904d0114346b7fa666566cdf09c916_1c96ba32b4574a2b9edda794e23ca0f7.png


// 层序遍历
void BinaryTreeLevelOrder(BinaryTreeNode* root)
{
  //创建一个队列
  Queue Qu;
  //初始化
  QueueInit(&Qu);
  //插入的是节点,
  if (root != NULL)
    QueuePush(&Qu, root);
  int size = QueueSize(&Qu);
  while (QueueSize(&Qu))
  {
    while (size--)
    {
      BinaryTreeNode* from = QueueFront(&Qu);


      printf("%d ", from->val);
      //删除
      QueuePop(&Qu);
      //需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点
      if (from->left != NULL)
      {
        QueuePush(&Qu, from->left);
      }
      if (from->rigth != NULL)
      {
        QueuePush(&Qu, from->rigth);
      }
    }
    printf("\n");
    size = QueueSize(&Qu);
    
  }
  printf("\n");
  QueueDestroy(&Qu);
  
  
  
}

判断是否是完全二叉树

思路:我们和上面的层次遍历一样,先找一个队列进行一层层的入队和出队,如果遇见节点为NULL的就判断后面是否还有节点存在

// 判断二叉树是否是完全二叉树
int BinaryTreeComplete(BinaryTreeNode* root)
{
  //创建一个队列
  Queue Qu;
  //初始化
  QueueInit(&Qu);
  //插入的是节点,
  if (root != NULL)
    QueuePush(&Qu, root);
  while (QueueSize(&Qu))
  {
    
    BinaryTreeNode* from = QueueFront(&Qu);
    if (from == NULL)
      break;
    //删除
        QueuePop(&Qu);
    //需要注意的是删除只是释放掉存储了二叉树节点的地址的空间,并没有释放二叉树节点
    QueuePush(&Qu, from->left);
    QueuePush(&Qu, from->rigth);
  }
  //判断后面是否还有非空
  while (!QueueEmtry(&Qu))
  {
    BinaryTreeNode* from = QueueFront(&Qu);
    if (from != NULL)
      return 0;
    //删除
    QueuePop(&Qu);
  }
  QueueDestroy(&Qu);
  return 1;

}

知识点

前序:深度优先遍历

层序: 广度优先遍历

相关文章
|
28天前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
17 0
|
28天前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
18 0
|
4天前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
23 3
【数据结构】树和二叉树的概念及结构
|
28天前
【数据结构】判断二叉树是否是完全二叉树
【数据结构】判断二叉树是否是完全二叉树
17 5
|
28天前
【数据结构】链式二叉树的层序遍历
【数据结构】链式二叉树的层序遍历
22 5
|
28天前
|
存储 测试技术
【数据结构】手把手分析:链式二叉树的实现
【数据结构】手把手分析:链式二叉树的实现
21 5
|
28天前
|
算法 分布式数据库
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
16 1
|
28天前
|
算法
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
【数据结构和算法】--- 二叉树(3)--二叉树链式结构的实现(1)
7 0
|
28天前
|
存储 算法
【数据结构和算法】---二叉树(2)--堆的实现和应用
【数据结构和算法】---二叉树(2)--堆的实现和应用
12 0
|
4天前
|
存储 前端开发 DataX
【数据结构】栈和队列
数据结构中的栈和队列
10 1
【数据结构】栈和队列