二叉树(链式结构存储)

简介: 二叉树(链式结构存储)

1.二叉树的前,中,后序

前序:按照访问顺序依次访问根,左子树,右子树

中序:按照访问顺序依次访问左子树,根,右子树

后序:按照访问顺序依次访问左子树,右子树,根

层序:一层一层的挨着遍历;

以上图为例:(N 表示NULL)

前序:1     2     4     N      N     5     N      N     3      6      N     N    7    N     N

中序:N    4     N     2      N      5     N     1      N      6     N     3     N    7     N

后序:N    N     4     N     N      5     2      N      N     6      N     N    7     3     1

层序:1     2     3     4      5      6      7

2.二叉树的前,中,后序遍历代码实现(递归)

前序遍历代码:

void PrevPrintf(BTNode* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  printf("%d ",root->val);
  PrevPrintf(root->left);
  PrevPrintf(root->right);
}

中序遍历代码:

void InPrintf(BTNode* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  InPrintf(root->left);
  printf("%d ", root->val);
  InPrintf(root->right);
}

后序遍历代码:

void PostPrintf(BTNode* root)
{
  if (root == NULL)
  {
    printf("N ");
    return;
  }
  PostPrintf(root->left);
  PostPrintf(root->right);
  printf("%d ", root->val);
}

2.实现几个函数

1.求树中结点个数

int    TreeSize(BTNode*  root);

代码思想:

要求树的结点,可以先求左右子树结点相加,求左右子树结点又可以先求左右子树的左右子树的结点相加;

实现代码:
//结点的个数
int TreeSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  return TreeSize(root->left) + TreeSize(root->right) + 1;
}

2.求树中叶子结点的个数

int    TreeLeafSize(BTNode*  root);

代码思想:

叶子结点的特点是:左右子树都为NULL;

当根结点为NULL时,直接返回0;

当左右子树都为NULL时,返回1,

不满足上面条件就继续递归当前结点的左右子树;

实现代码:
// 叶子节点个数
int TreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->left == NULL && root->right == NULL)
    return 1;
  return TreeLeafSize(root->left)+TreeLeafSize(root->right);
}

3.求树中第k层结点的个数

int    TreeKLevel(BTNode*  root);

代码思想:

对于第一层来说时求第k层的结点个数,但是对于第二层来说是求第k-1层的节点个数,对于第二层来说求第k-层的结点数目,以此类推,对于k-1层来说是求第二层结点数;

实现代码:
//第k层的结点
int TreeKLevel(BTNode* root, int k)
{
  assert(k > 0);
  if (root == NULL)
    return 0;
  if (k == 1)
    return 1;
  return TreeKLevel(root->left, k - 1) + TreeKLevel(root->right, k - 1);
}

4.查找树中的值

BTNode*  TreeFind(BTNode* root)

代码思想:

先与根比较,不是根再到左子树去找,左子树没有找到再到右子树中找

代码实现:
BTNode* FindBinaryTreeX(BTNode* root, int x)
{
  if (root == NULL)
    return;
  if (root->val == x)
    return root;
  BTNode* ret = NULL;
  ret = FindBinaryTreeX(root->left, x);
//如果ret不为空,就说明找到了,直接返回,不用到另一边去找
  if (ret)
    return ret;
  ret = FindBinaryTreeX(root->right, x);
  if (ret)
    return ret;
//找完了,没找到,返回空
  return NULL;
}

5.二叉树的层序遍历

void  BinaryTreeLevelOrder(BTNode* root)

代码思想:

利用队列先进先出的特点,先将根结点入进去,取出队列最前面的数,进行打印,再将根结点Pop出队列时,再将该结点的左右子树入进去,如图解:

 

代码实现:
void BinaryTreeLevelOrder(BTNode* root)
{
  Qu1 p;
//队列的初始化
  QueueInit(&p);
//如果根结点不为空,将根入队列
  if (root)
    QueuePush(&p, root);
  while (!QueueEmpty(&p))
  {
    BTNode* front = QueueFront(&p);
    QueuePop(&p);
    printf("%d ",front->val);
    if(front->left!=NULL)
      QueuePush(&p, front->left);
    if (front->right!= NULL)
      QueuePush(&p, front->right);
  }
//队列的销毁
  QueueDestory(&p);
}

6.二叉树的销毁

void BinaryTreeDestory(BTNode** root)

代码实现
// 二叉树销毁
void BinaryTreeDestory(BTNode* root)
{
  if (root == NULL)
    return;
  BinaryTreeDestory(root->left);
  BinaryTreeDestory(root->right);
  free(root);
  //这里root是形参,对它改变不会改变实参;
  root = NULL;
}
目录
相关文章
|
数据采集 自然语言处理
传统的序列模型CRF原理
传统的序列模型CRF原理
|
设计模式 前端开发 Java
SpringMvc框架入门使用(详细教程)
SpringMvc框架入门使用(详细教程)
369 0
|
存储 Cloud Native Linux
windows检测进程是否存在?强制杀死进程
windows检测进程是否存在?强制杀死进程
|
人工智能 芯片
通义千问上新,可一键免费解析超万页文档、速读百份文档
通义千问上新,可一键免费解析超万页文档、速读百份文档
1628 0
|
9月前
|
数据采集 SQL Oracle
从ORACLE源进行批量数据迁移到GBase8a参考示例
从ORACLE源进行批量数据迁移到GBase8a参考示例
从ORACLE源进行批量数据迁移到GBase8a参考示例
|
7月前
|
图形学
Unity UGUI拖拽移动
本文介绍了两种UI拖拽实现方式:精准拖拽和克隆拖拽。精准拖拽通过计算鼠标点击点与UI中心的偏移量,使UI跟随鼠标移动,适用于需要精确控制的场景。代码中通过`IBeginDragHandler`、`IDragHandler`和`IEndDragHandler`接口实现拖拽逻辑。克隆拖拽则在拖拽时克隆一个UI对象,使其跟随鼠标移动,适合视觉效果需求较高的场景。代码中同样使用上述接口,并在拖拽结束时销毁克隆对象。具体实现可参考提供的代码示例。
299 10
|
存储 算法 Linux
CTF—GIF文件格式、隐写方法及案例
CTF—GIF文件格式、隐写方法及案例
513 0
|
11月前
|
机器学习/深度学习 自然语言处理 自动驾驶
神经网络有哪些应用场景呢
【10月更文挑战第14天】神经网络有哪些应用场景呢
|
JavaScript 网络安全 开发工具
对象存储oss使用问题之文件上传在暂停时报错:ResponseError: socket hang up如何解决
《对象存储OSS操作报错合集》精选了用户在使用阿里云对象存储服务(OSS)过程中出现的各种常见及疑难报错情况,包括但不限于权限问题、上传下载异常、Bucket配置错误、网络连接问题、跨域资源共享(CORS)设定错误、数据一致性问题以及API调用失败等场景。为用户降低故障排查时间,确保OSS服务的稳定运行与高效利用。
1569 0