二叉树的实现(前中后层序四种遍历)

简介: 二叉树的实现(前中后层序四种遍历)

二叉树的创建和销毁


1.创建二叉树


创建一个二叉树,我们需要创建一个结构体,里面两个结构体指针分别存放左子树和右子树:

typedef char BTDataType; //typedef 便于后续修改数据类型
typedef struct BinaryTreeNode
{
  BTDataType _data;
  struct BinaryTreeNode* _left;
  struct BinaryTreeNode* _right;
}BTNode;


通过前序遍历的数组"ABD##E#H##CF##G##"构建二叉树

BTNode *BinaryTreeCreate(BTDataType * src, int n, int* pi)
{
  if (*pi >= n || src[*pi] == '#')
  {
    (*pi)++;
    return NULL;
  }
  BTNode * cur = (BTNode *)malloc(sizeof(BTNode));
  cur->_data = src[*pi];
  (*pi)++;
  cur->_left = BinaryTreeCreate(src, n, pi);
  cur->_right = BinaryTreeCreate(src, n, pi);
  return cur;
}


2.销毁二叉树

二叉树的销毁

void BinaryTreeDestory(BTNode** root)
{
  if (*root)
  {
    BinaryTreeDestory(&(*root)->_left);
    BinaryTreeDestory(&(*root)->_right);
    free(*root);
        *root = NULL;
  }
}


二叉树的遍历

// 二叉树前序遍历 
void BinaryTreePrevOrder(BTNode* root);
// 二叉树中序遍历
void BinaryTreeInOrder(BTNode* root);
// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root);
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root);


对于二叉树的四种遍历 :


前序遍历:当前结点(根节点 ), 左子树, 右子树 即访问根结点的操作发生在遍历其左右子树之前

中序遍历:左子树,根节点,右子树 访问根结点的操作发生在遍历其左右子树之中(间)。

后序遍历:左子树,右子树,根节点 访问根结点的操作发生在遍历其左右子树之后。

层序遍历:从所在二叉树的根节点出发,从上到下按层遍历,每层从左到右遍历


前中后序遍历实现:

void BinaryTreePrevOrder(BTNode* root)
{
  if (root)
  { 
    putchar(root->_data);
    BinaryTreePrevOrder(root->_left);
    BinaryTreePrevOrder(root->_right);
  }
}
void BinaryTreeInOrder(BTNode* root)
{
  if (root)
  {
    BinaryTreeInOrder(root->_left);
    putchar(root->_data);
    BinaryTreeInOrder(root->_right);
  }
}
void BinaryTreePostOrder(BTNode* root)
{
  if (root)
  {
    BinaryTreePostOrder(root->_left);
    BinaryTreePostOrder(root->_right);
    putchar(root->_data);
  }
}


层序遍历实现


对于层序遍历,我们不能简单的调用递归来遍历,这里我们利用队列其先进先出的性质,实现层序遍历:

#include "queue.h"
void BinaryTreeLevelOrder(BTNode* root)
{
  Queue qu;
  BTNode * cur;
  QueueInit(&qu);
  QueuePush(&qu, root);
  while (!QueueIsEmpty(&qu))
  {
    cur = QueueTop(&qu);
    putchar(cur->_data);
    if (cur->_left)
    {
      QueuePush(&qu, cur->_left);
    }
    if (cur->_right)
    {
      QueuePush(&qu, cur->_right);
    }
    QueuePop(&qu);
  }
  QueueDestory(&qu);
}


二叉树的相关计算

1.二叉树节点个数


我们递归调用将左子树的结点加上右子树的结点再加上根结点


int BinaryTreeSize(BTNode* root)
{
//巧用三目运算符
return root == NULL ? 0 : BinaryTreeSize(root->_left) + BinaryTreeSize(root->_right) + 1;
}


2.二叉树叶子节点个数

叶子节点:度为0的节点

int BinaryTreeLeafSize(BTNode* root)
{
  if (root == NULL)
    return 0;
  if (root->_left == NULL && root->_right == NULL)
    return 1; //只有根结点就返回1个叶子数
  //递归调用遍历左子树和右子树的叶子数相加
  return BinaryTreeLeafSize(root->_left) + BinaryTreeLeafSize(root->_right);
}


3.二叉树第k层节点个数

int BinaryTreeLevelKSize(BTNode* root, int k)
{
  if (root == NULL) //若二叉树为空或者K小于0,返回0
    return 0;
  if (k == 1) //若K等于1,第1层就是树根,根只有一个,返回1
    return 1;
  //递归调用返回左子树中第K-1层结点个数 加上 右子树中第K-1层结点的个数
  return BinaryTreeLevelKSize(root->_left, k - 1) + BinaryTreeLevelKSize(root->_right, k - 1);
}


4.二叉树查找值为x的节点


思路:先对左子树递归查找,如果未找到x,则返回NULL,如果找到x,便返回x所在节点。根据返回值判断是否需要进行右递归查找操作。


BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{
  if (root == NULL)
    return NULL;
  if (root->_data == x)
    return root;
  BTNode* ret1 = BinaryTreeFind(root->_left, x);
  if (ret1)
    return ret1;
  BTNode* ret2 = BinaryTreeFind(root->_right, x);
  if (ret2)
    return ret2;
  return NULL;
}


本节完

相关文章
【LeetCode】105. 从前序与中序遍历序列构造二叉树
题目描述: 给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 示例:
61 0
|
6月前
|
C++ 索引 Python
leetcode-105:从前序与中序遍历序列构造二叉树
leetcode-105:从前序与中序遍历序列构造二叉树
46 0
|
存储 算法
二叉树的创建和遍历
二叉树(Binary tree)是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显得特别重要。二叉树特点是每个节点最多只能有两棵子树,且有左右之分
91 0
|
存储 算法
二叉树的三序遍历
简要介绍二叉树的三序遍历和重构和代码实现。
102 0
二叉树四种遍历的实现
二叉树四种遍历的实现
100 0
|
机器学习/深度学习 C++ 容器
二叉树创建和遍历(C++实现)
树(Tree)是n(n≥0)个节点的有限集。在任意一棵树中有且仅有一个特定的称为根(Root)的节点;当n>1时,其余节点可分m(m>0)为个互不相交的有限集T1,T2,...,Tm;其中每一个集合本身又是一棵树,并且称为根的子树(SubTree)。 二叉树(Binary Tree)是一种特殊的有序树型结构,所有节点最多只有2棵子树。
657 0
二叉树的三种遍历方式
二叉树的三种遍历方式
232 0
二叉树的三种遍历方式
【LeetCode】-- 105. 从前序与中序遍历序列构造二叉树
【LeetCode】-- 105. 从前序与中序遍历序列构造二叉树
135 0
【LeetCode】-- 105. 从前序与中序遍历序列构造二叉树
|
算法 Python
LeetCode 987. 二叉树的垂序遍历
给你二叉树的根结点 root ,请你设计算法计算二叉树的 垂序遍历 序列。
97 0