数据结构之二叉树的基本实现

2023-08-19 41

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 数据结构之二叉树的基本实现

在我们之前已经了解的堆这样的完全二叉树的实现，也对树型结构有了一些了解，那么今天我们来看看二叉树的一些性质。

因为二叉树是一种每个节点至多只有两个子树（即二叉树的每个节点的度不大于2），并且二叉树的子树有左右之分，其次序不能任意颠倒，因此它的结构也是比较独特的。

1.二叉树的结构定义

二叉树是一种每个节点至多只有两个子树（即二叉树的每个节点的度不大于2），并且二叉树的子树有左右之分，其次序不能任意颠倒。

//定义树的节点
typedef int DATAtype;
typedef struct TreeNode
{
  DATAtype data;
  struct TreeNode* leftchild;
  struct TreeNode* rightchild;
}BTnode;

2.节点构造

简单的节点构造，如同链表的结点，不同的是这里有两个节点表示左孩子与右孩子。

//构造树的节点
BTnode* CreateNode(DATAtype x)
{
  BTnode* newnode = (BTnode*)malloc(sizeof(BTnode));
  if (newnode == NULL)
  {
    perror("malloc fali");
    return NULL;
  }
  newnode->data = x;
  newnode->leftchild = NULL;
  newnode->rightchild = NULL;
  return newnode;
}

3.节点生成树

我们是通过链接节点之间形成树的逻辑关系，这里的树如图：

先链接了六个节点，之后又添加了一个节点

//利用节点生成一个树
BTnode* TreeCreat()
{
  BTnode* node1=CreateNode(1);
  BTnode* node2=CreateNode(2);
  BTnode* node3=CreateNode(3);
  BTnode* node4=CreateNode(4);
  BTnode* node5=CreateNode(5);
  BTnode* node6=CreateNode(6);
  BTnode* node7 = CreateNode(6);
  //建立连接关系
  node1->leftchild = node2;
  node1->rightchild = node4;
  node2->leftchild = node3;
  node4->leftchild = node5;
  node4->rightchild = node6;
  node6->leftchild = node7;
  //返回根
  return node1;
}

3.二叉树的遍历方式

二叉树的遍历方式主要有四种，分别是先序遍历、中序遍历、后序遍历和层次遍历。123

先序遍历：

先访问根节点，再访问左子树，最后访问右子树。

//前序遍历
void Preverorder(BTnode*root)
{
  //根 左子树 右子树
  if (root == NULL)
  {
    return;
  }
  printf("%d ", root->data);
  Preverorder(root->leftchild);
  Preverorder(root->rightchild);
}

中序遍历：

先访问左子树，再访问根节点，最后访问右子树。

void Inorder(BTnode* root)
{
  // 左子树 根  右子树
  if (root == NULL)
  {
    return;
  }
  Preverorder(root->leftchild);
  printf("%d ", root->data);
  Preverorder(root->rightchild);
}

后序遍历

：先访问左子树，再访问右子树，最后访问根节点。

void Postorder(BTnode* root)
{
  // 左子树 右子树 根 
  if (root == NULL)
  {
    return;
  }
  Preverorder(root->leftchild);
  Preverorder(root->rightchild);
  printf("%d ", root->data);
}

层次遍历：

按照从上到下、从左到右的顺序依次访问每个节点。

层序遍历我们使用队列实现，思路：先进先出，上一层出队时带下一层节点入队。

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include"queue.h"
#define CRT_SECURE_NO_WARNINGS 1
//定义树的节点
typedef int DATAtype;
typedef struct TreeNode
{
  DATAtype data;
  struct TreeNode* leftchild;
  struct TreeNode* rightchild;
}BTnode;
//构造树的节点
BTnode* CreateNode(DATAtype x)
{
  BTnode* newnode = (BTnode*)malloc(sizeof(BTnode));
  if (newnode == NULL)
  {
    perror("malloc fali");
    return NULL;
  }
  newnode->data = x;
  newnode->leftchild = NULL;
  newnode->rightchild = NULL;
  return newnode;
}
//利用节点生成一个树
BTnode* TreeCreat()
{
  BTnode* node1=CreateNode(1);
  BTnode* node2=CreateNode(2);
  BTnode* node3=CreateNode(3);
  BTnode* node4=CreateNode(4);
  BTnode* node5=CreateNode(5);
  BTnode* node6=CreateNode(6);
  BTnode* node7 = CreateNode(6);
  //建立连接关系
  node1->leftchild = node2;
  node1->rightchild = node4;
  node2->leftchild = node3;
  node4->leftchild = node5;
  node4->rightchild = node6;
  node6->leftchild = node7;
  //返回根
  return node1;
}

层序遍历：

//层序遍历
void leverorder(BTnode* root)
{
  LTnode p;
  Queueinit(&p);
  Queuedestroy(&p);
  //先入根节点
  if (root)
  {
    LTpush(&p, root);
  }
  while (!LTempety(&p))
  {
    //队中数据全是树节点指针型
    BTnode* front = LTfront(&p);
      LTpop(&p);//出队头
      printf("%d", front->data);
         //判断孩子节点
      if (front->leftchild)
      {
        LTpush(&p, front->leftchild);
      }
      if (front->rightchild)
      {
        LTpush(&p, front->rightchild);
      }
  }
  printf("\n");
}

4.求树的所有节点个数

这里有两种方法，除了定义全局变量利用计数的方法来计算树的节点个数，但还需注意全局变量使用后需置零，其次我们也是利用递归的返回值累加计算出节点个数。

//求树的所有节点个数
int size = 0;
int Binarytreesize(BTnode* root)
{
  /*分治思想  从左子树到右子树再到根*/
  if (root == NULL)
  {
    return 0;
  }
  return (1 + Binarytreesize(root->leftchild) + Binarytreesize(root->rightchild));
  /*if (root)
  {
    size++;
    Binarytreesize(root->leftchild);
    Binarytreesize(root->rightchild);
  }
  return size;*/
}

5.求叶子节点个数

寻找递归条件，叶子节点没有左右孩子，否则就不返回一，符合条件的返回一相加。注意递归中返回值的设定。

//求叶子节点个数
int BTreeleavessize(BTnode* root)
{
  //自己的左子树与左右子树为空
  if (root == NULL)
  {
    return 0;
  }
  if (root->leftchild == NULL && root->rightchild == NULL)
  {
    return 1;
  }
  else
  {
    return BTreeleavessize(root->leftchild) + BTreeleavessize(root->rightchild);
  }
}

6.求二叉树树深度

分治思想，两边同时遍历，每有一层加一，左孩子层数与右孩子层数中较大的那个就是深度。

//求二叉树的深度
int BTreeheight(BTnode* root)
{
  //左右同时遍历，选最大的哪一个
  if (root == NULL)
  {
    return 0;
  }
  //这里注意用变量保存一下左 右子树的数目
  int left = BTreeheight(root->leftchild) + 1;
  int right= BTreeheight(root->rightchild) + 1;
  if (left > right)
  {
    return left;
  }
  else
  {
    return right;
  }
}

7.二叉树第K层节点个数

这里的递归主要是找的第k层，利用k==1作为递归返回条件。

//二叉树第k层结点的个数
int BTree_knumber(BTnode* root,int k)
{
  //分情况讨论
  if (root == NULL)
  {
    return 0;
  }
  if (k==1)
  {
    return 1;
  }
  return  BTree_knumber(root->leftchild, k - 1) +
      BTree_knumber(root->rightchild, k - 1);
}

8.返回值为x的节点

这里的难度在与返回值，我们知道在递归里面函数返回值不能直接返回，我们需要判断，对于返回值是需要我们好好检查的，在这里，我们从根，左孩子，右孩子的顺序逐个判断，对于左右孩子并保存返回值，来确定是当前节点。

//返回为x的树节点
BTnode* BTreenode(BTnode* root, DATAtype x)
{
  if (root == NULL)
  {
    return NULL;
  }
  if (root->data == x)
  {
    return root;
  }
  BTnode* left = BTreenode(root->leftchild,x);
  if (left->data==x)
  {
    return left;
  }
  BTnode* right = BTreenode(root->rightchild,x);
  if (right->data==x)
  {
    return right;
  }
  return NULL;
}

一些测试用例：

int main()
{
  BTnode* root = TreeCreat();
  /*Preverorder(root);
  printf("\n");
  Inorder(root);
  printf("\n");
  Postorder(root);*/
  //Binarytreesize(root);
  // BTreeleavessize(root);//BTreeheight(root);
  int x = BTree_knumber(root, 2);
  printf("%d ", BTreenode(root, 2)->data);
  //printf("%d", x);
  return 0;
}