数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(上)

简介: 数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码

需要先创建一颗二叉树,然后才能学习其相关的基本操作,考虑到我们刚刚接触二叉树,

为了能够先易后难地进行讲解,这里将手动创建一颗简单的二叉树,用来方便大家学习。

等二叉树结构了解的差不多后,后期会研究二叉树的真正的创建方式。

(后面的层序遍历跟着的那篇OJ就是用前序遍历构建二叉树)

1.二叉树概念

二叉树是什么?① 空树 ② 非空:根节点、根节点的左子树与根节点的又子树组成的。

85ca08b0ce884b469769bc1248863c22.png


从概念中我们不难看出,二叉树的定义是递归式的。因此后续基本操作中,基本都是按照该概念来实现的,来看 A 的左子树,把 B 看作为根节点,又是颗二叉树。所以可以通过采用递归的手法来实现二叉树。

2.二叉树定义

 
#define _CRT_SECURE_NO_WARNINGS 1
 
#include<stdio.h>
 
typedef char BTDataType;
 
typedef struct BinaryTreeNode 
{
    struct BinaryTreeNode* left;       // 记录左节点
    struct BinaryTreeNode* right;      // 记录右节点
    BTDataType data;                   // 存储数据
} BTNode;
 
//创建新节点
BTNode* CreateNode(BTDataType x) 
{
    BTNode* new_node = (BTNode*)malloc(sizeof(BTNode));
    if (new_node == NULL)
    {
        printf("malloc failed!\n");
        exit(-1);
    }
    new_node->data = x;
    new_node->left = new_node->right = NULL;
 
    return new_node;
}
 
//手动创建二叉树 
BTNode* CreateBinaryTree() 
{
    BTNode* nodeA = CreateNode('A');
    BTNode* nodeB = CreateNode('B');
    BTNode* nodeC = CreateNode('C');
    BTNode* nodeD = CreateNode('D');
    BTNode* nodeE = CreateNode('E');
    BTNode* nodeF = CreateNode('F');
 
    nodeA->left = nodeB;         //           A
    nodeA->right = nodeC;        //       B        C
    nodeB->left = nodeD;         //    D        E    F
    nodeC->left = nodeE;       
    nodeC->right = nodeF;        
 
    return nodeA;
}
 
int main()
{
    BTNode* root = CreateBinaryTree();
}

3.二叉树深度优先遍历

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

二叉树遍历(Traversal):沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。 按照规则,二叉树的遍历有:前序 / 中序 / 后序 的递归或非递归遍历。除了前序、中序和后续遍历外,我们还可以对二叉树进行层序遍历

比如二叉树的中序遍历:

3.1二叉树前序遍历

前序遍历(Preorder Traversal):访问根节点的操作发生在遍历其右子树之前。即:首先访问根结点,然后遍历左子树,最后遍历右子树(根左右)。

代码实现前序遍历:

 
//二叉树前序遍历
void PreOrder(BTNode* root)
{
    //首先判断根是否为空,为空就返回
    if (root == NULL)
    {
        printf("NULL ");    // 暂时打印出来,便于观察       
        return;
    }
    //走到这里说明不为空,根据前序遍历,先访问根节点
    printf("%c ", root->data);
 
    //然后遍历左子树(利用递归)
    PreOrder(root->left);
 
    //最后遍历右子树(利用递归)
    PreOrder(root->right);
 
    //           A
    //       B        C
    //    D        E    F        前序:根 左 右
    //执行输出:  A B D NULL NULL NULL C E NULL NULL F NULL NULL
}

① 首先判断根是否为空,如果根为空,则返回。这里为了表示,我们把空节点以 " Ø " 打印出来。


② 如果跟不为空,这说明有数据。由于是前序遍历(Preorder),前序遍历是先访问根节点,然后遍历左子树,最后再遍历右子树。所以,我们这里先要访问的是根节点,我们把根节点的数据打印出来。


③ 然后我们需要遍历左子树,这时我们利用递归就可以实现。将根节点 root 的左数 left 传入 PreOrder 函数(将其左树看作根),一直递归下去,直到碰到 root == NULL 则返回。

④ 最后,遍历完左子树后遍历右子树。利用递归,方法同上。


3.2二叉树中序遍历

递归的中序和后序和前序差不多 顺序换一下就行

 
//二叉树中序遍历
void InOrder(BTNode* root) 
{
    if (root == NULL) 
    {
        printf("NULL ");  
        return;
    }
 
    InOrder(root->left);
 
    printf("%c ", root->data);
 
    InOrder(root->right);
    //           A
    //       B        C
    //    D        E    F         中序:左  根  右
    //执行输出:NULL D NULL B NULL A NULL E NULL C NULL F NULL
}

3.3二叉树后序遍历

 
void PostOrder(BTNode* root) 
{
    if (root == NULL) 
    {
        printf("NULL ");
        return;
    }
 
    PostOrder(root->left);
 
    PostOrder(root->right);
 
    printf("%c ", root->data);
    //           A
    //       B        C
    //    D        E    F        后序:左  右  根
    //执行输出:NULL NULL D NULL B NULL NULL E NULL NULL F C A
}

4.二叉树的几个接口函数

下面我们实现几个接口函数

 
// 二叉树结点个数
int BinaryTreeSize(BTNode* root);
// 二叉树叶子结点个数
int BinaryTreeLeafSize(BTNode* root);
// 二叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
// 二叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// 二叉树销毁
void BinaryTreeDestory(BTNode** root);

4.1 求二叉树结点个数

和上面遍历一样,采用分治的思想:是空就返回0,不是空就返回左子树的结点和右子树的结点+1(本身)。

 
int TreeSize(BTNode* root) 
{
    return root == NULL ? 0 
              : TreeSize(root->left) + TreeSize(root->right) + 1;
}

f66bcdf94f4b48b884b110105fbf1e78.png

4.2 求二叉树叶子结点个数

同理,是空返回1,是叶子返回0,不是空也不是叶子的话就求其左子树的叶子+右子树的叶子

 
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);
}

0425a2f1bb774c91b8a3fb3e0157135e.png


数据结构与算法⑭(第四章_下)二叉树的模拟实现和遍历代码(下):https://developer.aliyun.com/article/1513455

目录
相关文章
|
3天前
|
存储 算法 Java
Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。
【6月更文挑战第21天】Java中,树与图的算法涉及二叉树的前序、中序、后序遍历以及DFS和BFS搜索。二叉树遍历通过访问根、左、右子节点实现。DFS采用递归遍历图的节点,而BFS利用队列按层次访问。以下是简化的代码片段:[Java代码略]
10 4
|
6天前
|
算法 Java 索引
【算法】重建二叉树并进行后序遍历的Java实现
【算法】重建二叉树并进行后序遍历的Java实现
17 5
|
6天前
|
存储 算法 Java
广度优先搜索(Breadth-First Search,BFS)是一种用于图的遍历或搜索的算法。
广度优先搜索(Breadth-First Search,BFS)是一种用于图的遍历或搜索的算法。
|
7天前
|
搜索推荐 算法
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
【排序】数据结构——排序算法概念及代码详解(插入、冒泡、快速、希尔)
|
7天前
|
存储 算法
【树】数据结构——树和二叉树的概念&笔记
【树】数据结构——树和二叉树的概念&笔记
|
18小时前
|
算法
数据结构和算法常见的问题和代码
数据结构和算法常见的问题和代码
|
3天前
|
存储
数据结构===二叉树
数据结构===二叉树
|
3天前
|
存储 算法 Java
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
面试高频算法题汇总「图文解析 + 教学视频 + 范例代码」之 二分 + 哈希表 + 堆 + 优先队列 合集
|
6天前
|
人工智能 算法 Java
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
深度优先搜索(Depth-First Search,DFS)是一种用于遍历或搜索树或图的算法。
|
7天前
|
存储 算法
【二叉树】数据结构——BST二叉树基本概念及算法设计(插入、删除、遍历操作)
【二叉树】数据结构——BST二叉树基本概念及算法设计(插入、删除、遍历操作)

热门文章

最新文章