• 二叉树详解(求二叉树的结点个数、深度、第k层的个数、遍历等)


    二叉树,是一种特殊的树,特点是树的度小于等于2(树的度是整个树的结点的度的最大值),由于该特性,构建二叉树的结点只有三个成员,结点的值和指向结点左、右子树的指针。

    1. typedef int DateType;
    2. typedef struct TreeNode
    3. {
    4. DateType val;//结点的值
    5. struct TreeNode*left;//指向左结点
    6. struct TreeNode*right;//指向右节点
    7. }Node;

    对于二叉树,有一种特殊的情况,即一共有k层,前k-2层每个结点的度都是2,第k-1层若有个结点有子树,则其左侧的结点均有子树,这种情况被称为完全二叉树。若第k-1层也是所有结点的度都是2,则为满二叉树。

    二叉树的遍历:

    1.前序遍历:对于二叉树的每个结点,都是先访问根节点,再访问其左子树,访问完再访问右子树。前序遍历可以用于深度搜索

    2.中序遍历:对于二叉树的每个结点,都是先访问其左子树,再访问根节点,访问完再访问右子树。中序遍历就是把二叉树的每个结点垂直投影到同一水平的序列。

    3.后序遍历:对于二叉树的每个结点,都是先访问其左子树,再访问访问右子树,访问完再访问根节点。

    4.层序遍历:一层一层的访问,每一层都是先访问左侧的结点再访问右侧的。层序遍历可以用于广度搜索

    知道前序遍历和后序遍历的其中一个结果,再知道中序遍历的结果,可以唯一确定一颗二叉树,但只知道前序遍历和后序遍历的结果不能唯一确定。

    求树的深度:

    思路:化成求子树的深度,找出其中的最大值,再加上根节点这一层(即加1),就是当前结点的深度。

    1. int maxdepth(TNode *root)
    2. {
    3. if(root==NULL)
    4. {
    5. return 0;
    6. }
    7. return max(maxdepth(root->left),maxdepth(root->right))+1;
    8. }

    求结点的个数:

    思路:对于每个结点,求左子树的结点的个数和右子树的结点的个数,再加上根节点,就是以当前结点为根的树的结点的个数。

     

    1. int Nodenum(Node*root)
    2. {
    3. if(root==NULL)
    4. {
    5. return 0;
    6. }
    7. return Nodenum(root->left)+Nodenum(root->right)+1;
    8. }

    求叶子结点的个数:

    思路:对每个结点,判断其是不是叶子结点,若不是则找左子树和右子树的叶子结点的个数,若是则返回1.

    1. int NodeLeaveNum(Node*root)
    2. {
    3. if(root==NULL)
    4. return 0;
    5. if(root->left==NULL&&root->right==NULL)
    6. return 1;
    7. return NodeLeaveNum(root->left)+ NodeLeaveNum(root->right);
    8. }

    求第k层结点的个数:

    思路:对于第m层的结点找第n层,就是第m层的子节点找第n-1层。

    1. int NodeKNum(Node*root, int k)
    2. {
    3. if(root==NULL)
    4. return 0;
    5. if(k==1)
    6. return 1;
    7. //上述两个判断位置不能颠倒,否则会出错
    8. return NodeKNum(root->left,k-1)+ NodeKNum(root->right,k-1);
    9. }

     

     

  • 相关阅读:
    Java之字符流的详细解析
    Java 并发编程解析 | 如何正确理解Java领域中的并发锁,我们应该具体掌握到什么程度?
    Linux笔记之Bash脚本中的EOF
    gradle学习笔记(六) 官方文档笔记+理解
    技术分享 | mysqlreplicate 源码分析
    jdk8更新到333了,你确定不更新你的Java吗
    Java中接口间的继承
    谷歌浏览器HttpOnly跨域请求
    【Nuxt】04 Nuxt2-SEO: sitemap.xml、seo优化、robots.txt
    期末复习总结【MySQL】五种约束类型, 主键和外键的使用方式(重点)
  • 原文地址:https://blog.csdn.net/yyssas/article/details/132865363