• 2.20数据结构与算法学习日记(二叉树第一部分)


    1.树的表示

    1. typedef int DadaType;
    2. struct Node{
    3. struct Node* firstChild;
    4. struct Node* pnextBrother
    5. DataType data;
    6. };//树的表示

    2.二叉树的简介

    二叉树是一种树形数据结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树具有以下特点:

    1. 根节点:二叉树的顶端节点称为根节点,它没有父节点。
    2. 子节点:每个节点最多有两个子节点,分别称为左子节点和右子节点。
    3. 叶节点:没有子节点的节点称为叶节点。
    4. 深度:从根节点到某个节点的唯一路径上的节点数称为该节点的深度。
    5. 高度:从某个节点到叶节点的最长路径上的节点数称为该节点的高度。
    6. 完全二叉树:除了最底层之外,每一层的节点都是满的,并且最底层的节点都靠左排列。
    7. 满二叉树:每个节点要么没有子节点,要么有两个子节点。

    二叉树可以用来表示表达式、文件系统、数据库索引等各种数据结构和算法问题。常见的二叉树遍历方式有前序遍历、中序遍历和后序遍历。

    3.二叉树图例(部分)

    1.普通二叉树

    普通二叉树是一种最基本的二叉树,每个节点最多有两个子节点,分别称为左子节点和右子节点。普通二叉树没有特定的规则或性质,节点的插入和删除可以任意进行,因此它的形态和结构比较灵活。

    以下是一个示例普通二叉树的图示:

    ```
            1
           / \
          2   3
         / \    / \
        4  5 6  7
    ```

    在这个例子中,这是一个普通二叉树,每个节点最多有两个子节点,节点的插入和删除可以随意进行,没有特定的规则限制。普通二叉树常用于表示一般的树形结构,如文件系统、家谱等。

    2.完全二叉树 

    完全二叉树是一种特殊的二叉树,除了最底层之外,每一层的节点都是满的,并且最底层的节点都靠左排列。在完全二叉树中,如果某个节点的索引为i(从1开始),则它的左子节点的索引为2i,右子节点的索引为2i+1。

    以下是一个示例完全二叉树的图示:

    ```
            1
           / \
          2   3
         / \    / 
        4  5 6  
    ```

    在这个例子中,这是一个完全二叉树,因为每一层的节点都是满的,除了最底层的节点6之外,其他节点都是靠左排列的。完全二叉树常用于堆数据结构的实现,具有较好的性能特性。

    3.满二叉树

    满二叉树是一种特殊的二叉树,每个节点要么没有子节点,要么有两个子节点。除了叶节点外,每个节点都有两个子节点。满二叉树的叶节点都在同一层,且所有非叶节点的度都是2。

    以下是一个示例满二叉树的图示:

            1
           / \
          2   3
         / \    / \
        4  5 6  7
     

    在这个例子中,这是一个满二叉树,每个节点要么没有子节点,要么有两个子节点,所有非叶节点的度都是2。满二叉树在计算机科学中常用于堆数据结构的实现,具有一些特殊的性质和应用。

    4.二叉树遍历

    1.前序遍历

    在前序遍历中,对于任意节点,先访问该根节点,然后递归地对其左子树进行前序遍历,最后递归地对其右子树进行前序遍历。

    以下是一个示例二叉树的前序遍历顺序(节点值用数字表示):

            1
           / \
          2   3
         / \ / \
        4  5 6  7
    

    前序遍历的结果为:1, 2, 4, 5, 3, 6, 7。

    在这个例子中,前序遍历先访问根节点1,然后递归地对左子树进行前序遍历(2, 4, 5),最后递归地对右子树进行前序遍历(3, 6, 7)。

    2.中序遍历

    在中序遍历中,对于任意节点,先递归地对其左子树进行中序遍历,然后访问该节点,最后递归地对其右子树进行中序遍历。

    以下是一个示例二叉树的中序遍历顺序(节点值用数字表示):

            1
           / \
          2   3
         / \    / \
        4  5 6  7

    中序遍历的结果为:4, 2, 5, 1, 6, 3, 7。

    在这个例子中,中序遍历先递归地对左子树进行中序遍历(4, 2, 5),然后访问根节点1,最后递归地对右子树进行中序遍历(6, 3, 7)。

    3.后序遍历

    它的遍历顺序是先递归地对左子树进行后序遍历,然后递归地对右子树进行后序遍历,最后访问根节点。(左,右,根)

    在后序遍历中,对于任意节点,先递归地对其左子树进行后序遍历,然后递归地对其右子树进行后序遍历,最后访问该根节点。

    以下是一个示例二叉树的后序遍历顺序(节点值用数字表示):

    ```
            1
           / \
          2   3
         / \    / \
        4  5 6  7
    ```

    后序遍历的结果为:4, 5, 2, 6, 7, 3, 1。

    在这个例子中,后序遍历先递归地对左子树进行后序遍历(4, 5, 2),然后递归地对右子树进行后序遍历(6, 7, 3),最后访问根节点1。

    代码示例(单纯只是定义了函数)

    1. #include
    2. using namespace std;
    3. typedef int DadaType;
    4. struct Node{
    5. struct Node* firstChild;
    6. struct Node* pnextBrother
    7. DataType data;
    8. };//树的表示
    9. //二叉链
    10. struct binaryTreeNode{
    11. struct binaryTreeNode* pleft;
    12. struct binaryTreeNode* pright;
    13. }BTnode;
    14. void PreOrder(BTnode *root){//前序遍历(根,左,右)
    15. if(root==NULL)
    16. {
    17. printf("NULL");
    18. return;
    19. }
    20. printf("%d",root->data);
    21. PreOrder(root->pleft);
    22. PreOrder(root->pright);
    23. }
    24. void Inorder(BTnode *root){//中序遍历(左,根,右)
    25. if(root==NULL){
    26. printf("NULL");
    27. return;
    28. }
    29. Inorder(root->pleft);
    30. printf("%d",root->data);
    31. Inorder(root->pright);
    32. }
    33. void PostOrder(Btnode *root){//后序遍历(左,右,根)
    34. if(root==NULL){
    35. printf("NULL");
    36. }
    37. PostOrder(root->pleft);
    38. printf("%d",root->data);
    39. PostOrder(root->pright);
    40. }
    41. void destroyOrder(BTnode *root){
    42. if(root==NULL){
    43. return;
    44. }
    45. destroyOrder(root->pleft);
    46. destroyOrder(root->pright);
    47. free(root);
    48. root=NULL;
    49. }

  • 相关阅读:
    mysql varchar和bigint比较的坑
    结合手工注入编写一个SQL盲注脚本——以SQLi-Labs less16为例
    nodejs:path路径模块
    基于java的乡村图书馆管理系统的设计与实现毕业设计-附源码191505
    《算法导论》第14章-数据结构的扩张 14.1-动态顺序统计 14.2-如何扩张数据结构
    【建站教程】使用阿里云服务器怎么搭建网站?
    Logstash8.4在Linux系统上的安装以及配置Tomcat日志(ELK安装part2)
    Day07 待办事项功能页面设计
    华为配置CAPWAP双栈覆盖业务示例
    校准周期好复杂,不过这样理解就简单多了
  • 原文地址:https://blog.csdn.net/weixin_64589886/article/details/136199599