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

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

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

4.3求二叉树第k层结点个数

求当前树的第k层结点个数=其左子树第k-1层结点个数+其右子树第k-1层结点个数,k=1时返回1

比如上图K=3,求A的第3层结点个数就是求B的第2层的节点+C的第2层的结点。

 
int TreeKLevelSize(BTNode* root, int  k) 
{
    assert(k > 0);
    if (root == NULL) //空结点返回0
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    return TreeKLevelSize(root->left, k - 1) 
        +  TreeKLevelSize(root->right, k - 1);
}

4.4查找树里面值为x的那个结点

思路:空就返回空,找到了就返回这个结点,没找到就到左子树和右子树去找,都没找到就返回空

 
BTNode* TreeFind(BTNode* root, BTDataType x) 
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x) 
    {
        return root;
    }
 
    BTNode* lret = TreeFind(root->left, x);
    if (lret) 
    {
        return lret;
    }
 
    BTNode* rret = TreeFind(root->right, x);
    if (rret) 
    {
        return rret;
    }
 
    return NULL;
}

比如要找E的位置:(找不到前都返回空)


4.5 二叉树销毁

这里采用后序遍历的销毁方式,因为用前序和中序要保存结点。

 
// 一般,如果选择一级指针,存在野指针问题,调用BinaryTreeDestory的人,把指针置空
// 这样保持接口的一致性
void BinaryTreeDestory(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
 
    //printf("%p %c\n", root, root->data);
    free(root);
    root = NULL;
}


前面函数的代码和测试:

 
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.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;
}
 
//二叉树前序遍历
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
}
 
//二叉树中序遍历
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
}
 
//二叉树后序遍历
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
}
 
int TreeSize(BTNode* root) 
{
    return root == NULL ? 0 
        : TreeSize(root->left) + TreeSize(root->right) + 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);
}
 
int TreeKLevelSize(BTNode* root, int  k) 
{
    assert(k > 0);
    if (root == NULL) 
    {
        return 0;
    }
    if (k == 1)
    {
        return 1;
    }
    return TreeKLevelSize(root->left, k - 1) 
        +  TreeKLevelSize(root->right, k - 1);
}
 
// 查找树里面值为x的那个节点
BTNode* TreeFind(BTNode* root, BTDataType x) 
{
    if (root == NULL)
    {
        return NULL;
    }
    if (root->data == x) 
    {
        return root;
    }
 
    BTNode* lret = TreeFind(root->left, x);
    if (lret) 
    {
        return lret;
    }
 
    BTNode* rret = TreeFind(root->right, x);
    if (rret) 
    {
        return rret;
    }
 
    return NULL;
}
 
// 一般,如果选择一级指针,存在野指针问题,调用BinaryTreeDestory的人,把指针置空
// 这样保持接口的一致性
void BinaryTreeDestory(BTNode* root)
{
    if (root == NULL)
    {
        return;
    }
    BinaryTreeDestory(root->left);
    BinaryTreeDestory(root->right);
 
    //printf("%p %c\n", root, root->data);
    free(root);
    root = NULL;
}
 
int main()
{
    BTNode* root = CreateBinaryTree();
    PreOrder(root);
    printf("\n");
 
    InOrder(root);
    printf("\n");
 
    PostOrder(root);
    printf("\n");
 
    printf("TreeSize:%d\n", TreeSize(root));
 
    printf("TreeLeafSize:%d\n", TreeLeafSize(root));
 
    printf("TreeKLevelSize:%d\n", TreeKLevelSize(root, 3));
 
    printf("TreeFind:%p\n", TreeFind(root, 'E'));
    printf("TreeFind:%p\n", TreeFind(root, 'F'));
    printf("TreeFind:%p\n", TreeFind(root, 'X'));//打印0 :找不到
 
    BinaryTreeDestory(root);
    root = NULL;
    return 0;
}


5.二叉树广度优先遍历

5.1层序遍历

层序遍历(Level Traversal):设二叉树的根节点所在的层数为1的情况下,

从二叉树的根节点出发,首先访问第1层的树根节点,然后再从左到右访问第2层上的节点。

接着是第3层的节点……以此类推,自上而下、从左向右地逐层访问树的节点。

该如何实现层序遍历呢? 可以利用队列的性质来实现。

之前再讲过队列,这里你可以选择自己实现一个队列。

如果不想实现就直接复制即可,因为这里重点要学的是层序遍历。

这里就先不实现了,下一篇写写二叉树OJ,下下篇再实现(最下面已附链接)

6.笔试选择题

练习1:

2-3树是一种特殊的树,它满足两个条件:

(1) 每个内部结点有两个或三个子结点

(2) 所有的叶结点到根的距离相同

如果一颗2-3树有10个结点,那么它有( )个叶结点。

A.7

B.8

C.7 或 8

D.6


练习2:

设某种二叉树有如下特点:每个结点要么是叶子结点,要么有2棵子树。假如一棵这样的二叉树中有m(m>0)个叶子结点,那么该二叉树上的结点总数为( )

A.2m+1

B.2(m-1)

C.2m-1

D.2m

练习3:

设根结点的深度为1,则一个拥有n个结点的二叉树的深度一定在( )区间内

A.[log(n + 1),n]

B.[logn,n]

C.[log(n + 1),n - 1]

D.[log(n + 1),n + 1]

练习4:

对任意一颗二叉树,设N0、N1、N2分别是度为0、1、2的结点数,则下列式子中一定正确的是( )

A.N0 = N2 + 1

B.N1 = N0 + 1

C.N2 = N0 + 1

D.N2 = N1 + 1

练习5:

二叉树的( )遍历相当于广度优先遍历,( )遍历相当于深度优先遍历

A.前序 中序

B.中序 前序

C.层序 后序

D.层序 前序


练习6:

如果一颗二叉树的前序遍历的结果是ABCD,则满足条件的不同的二叉树有( )种

A.13

B.14

C.15

D.16

答案:

1.答案:D

根据题目意思,每一个非叶子节点至少有两个孩子节点,并且叶子节点都在同一层,所以,假设树的高度为h, 则二三树种最小的节点个数为满二叉树的个数:2^h - 1, 最大个数: (3^h - 1) / 2。所以 2^h - 1 < 10 < (3^h - 1) / 2, h为3,结构是1(3(2,2,2))。所以叶节点个数为6


2.答案:C


根据二叉树的性质,在任意的二叉树中,度为0的节点比度为2的节点多了1个----见课件


现在叶子节点为m个,即度为0的节点有m个,那度为2的节点个数就为m-1个


而题目说该二叉树中只有度为2和度为0的节点 ,因此总的节点数就为:m+m-1 = 2m-1


3答案:A


最大深度: 即每次只有一个节点,次数二叉树的高度为n,为最高的高度


最小深度: 此树为完全二叉树, 如果是完全二叉树


根据二叉树性质,完全二叉树的高低为 h = log(n+1)向上取整


4答案:A


节点总数N: N = N0 + N1 + N2


度和边的关系: N - 1 = 0 * N0 + 1 * N1 + 2 * N2


上面两个式子可以推出: N0 + N1 + N2 - 1 = N1 + 2 * N2


可得: N0 = N2 + 1


5答案:D(前中后序遍历都可以称为深度优先遍历,但是单选的话就选前序)


广度优先需要把下一步所有可能的位置全部遍历完,才会进行更深层次的遍历,


层序遍历就是一种广度优先遍历。


深度优先是先遍历完一条完整的路径(从根到叶子的完整路径),才会向上层折返,


再去遍历下一个路径,前序遍历就是一种深度优先遍历。


6答案:B


首先这棵二叉树的高度一定在3~4层之间:


三层:


A(B(C,D),()), A((),B(C,D)), A(B(C,()),D), A(B((),C),D),


A(B,C(D,())), A(B,C((),D))


四层:


如果为四层,就是单边树,每一层只有一个节点,除过根节点,其他节点都有两种选择,


在上层节点的左边还是右边,所以2*2*2共8种,总共为14种。

本篇完

目录
相关文章
|
6天前
|
存储 SQL 算法
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
LeetCode力扣第114题:多种算法实现 将二叉树展开为链表
|
3天前
|
存储 机器学习/深度学习 缓存
【数据结构】布隆过滤器原理详解及其代码实现
【数据结构】布隆过滤器原理详解及其代码实现
|
6天前
|
存储 缓存 算法
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
LeetCode力扣题目111:多种算法对比实现二叉树的最小深度
|
6天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
6天前
|
存储 SQL 算法
LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历
LeetCode 题目 94:五种算法递归|迭代|莫里斯|线索二叉树|栈的迭代二叉树 实现中序遍历
|
9天前
|
算法 Java
JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)
JavaSE——算法(2/2):查找算法-二分查找(前言、详细图解、代码部分)
11 2
|
9天前
|
算法 搜索推荐 Java
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
JavaSE——算法(1/2):认识、冒泡排序、选择排序及优化(介绍、详细图解、代码)
9 0
|
10天前
|
算法 C语言
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
数据结构和算法——桶排序和基数排序(图示、伪代码、多关键字排序,基数排序代码)
9 0
|
10天前
|
算法 C语言
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
数据结构和算法——归并排序(有序子列的归并、递归算法、非递归算法、思路图解、C语言代码)
9 0
|
10天前
|
存储 算法 C语言
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
数据结构和算法——堆排序(选择排序、思路图解、代码、时间复杂度、堆排序及代码)
8 0