二叉树的递归算法例题_递归算法统计二叉树的宽度-程序员宅基地

技术标签:   算法与数据结构  

二叉树递归算法:
1. 统计二叉树中,度为0的结点个数

2. 统计二叉树中,度为1的结点个数

3. 统计二叉树中,度为2的结点个数

4. 统计二叉树高度

5. 统计二叉树宽度度

6. 删除二叉树中所有叶子节点

7. 交换每个节点的左右子女

8.  判断一棵树是否为二叉排序树

9. 找出给定结点在二叉树中的层次

10. 判断二叉树是否为平衡二叉树

首先,创建二叉树

BiTree CreateBiTree( ){
    char ch;
    scanf("%c",&ch);
    if(ch=='#') return NULL;
    else{
        BiTree T = (BiTree)malloc(sizeof(BiTNode));
        T -> lchild  = T -> rchild = NULL;
        T->data = ch;
        T->lchild = CreateBiTree();
        T->rchild = CreateBiTree();
        return T;
    } 
}

1.统计二叉树中,度为0的结点个数

int Degree_0(BiTree T){
    if(T==NULL) return 0 ;
    if( T->lchild==NULL && T->rchild == NULL )
        return 1 + Degree_0(T->lchild )+ Degree_0(T->rchild) ;
    else
        return Degree_0(T->lchild )+ Degree_0(T->rchild) ;
}

2.统计二叉树中,度为1的结点个数

int Degree_1(BiTree T){
    if(T==NULL) return 0 ;
    if(( T->lchild!=NULL && T->rchild == NULL ) ||( T->lchild==NULL && T->rchild != NULL ) )
        return 1 + Degree_1(T->lchild )+ Degree_1(T->rchild) ;
    else
        return Degree_1(T->lchild )+ Degree_1(T->rchild) ;
}

3.统计二叉树中,度为2的结点个数

int Degree_2(BiTree T){
    if(T==NULL) return 0 ;
    if( T->lchild!=NULL && T->rchild != NULL )
        return 1 + Degree_2(T->lchild )+ Degree_2(T->rchild) ;
    else
        return Degree_2(T->lchild )+ Degree_2(T->rchild) ;
}

4.统计二叉树高度

int Depth( BiTree T ){ 
    if(T == NULL) return 0;
    else return max(Depth(T->lchild),Depth(T->rchild))+1;     
}

5.统计二叉树宽度

void Width( BiTree T ,int deep){
    if(T == NULL) return ;
    else{
        s[deep]++ ;
        Width( T->lchild , deep +1 );
        Width( T->rchild , deep +1 );
    }
}

6.删除二叉树中所有叶子节点

void Delete_leaves(BiTree T){
    if( T ){
        if(T->lchild){
            if(T->lchild->lchild==NULL&&T->lchild->rchild==NULL){
                free(T->lchild);
                T->lchild=NULL ;
            }
            else
                Delete_leaves(T->lchild);
        }
        if(T->rchild){
            if(T->rchild->lchild==NULL&&T->rchild->rchild==NULL){
                free(T->rchild);
                T->rchild=NULL ;
            }
            else
                Delete_leaves(T->rchild);
        }
    }
}

7.交换每个节点的左右子女

void swap(BiTree T){
    BiTNode *p ;
    if(T){
        swap(T->lchild);
        swap(T->rchild);
        p = T->lchild ;
        T->lchild = T->rchild ;
        T->rchild = p ;
    }
}

8.判断一棵树是否为二叉排序树

二叉排序树的中序遍历是递增有序序列。因此,对于给定的二叉树进行中序递归遍历,如果能保持前一个值始终比后一个值小,而说明二叉树是一颗二叉排序树。

1)设置全局变量max为无穷小。 
2)若树为空,则返回true。 
3)否则递归判断左子树是否为二叉排序树,并用bst_l保存结果。 
3)若flag1为假或者根节点关键字小于等于左子树的关键字,则返回false。 
4)否则递归判断右子树是否为二叉排序树,并用bst_r保存结果。 
5)返回 bst_r。

//判断是否为二叉排序树 
bool Judge(BinaryTree* root,int& MAX){
    if(root == NULL)  //树为空则为二叉排序树 
        return true;
    bool bst_l,bst_r;
    bst_l = Judge(root->lchild,MAX);//判断左子树是否为二叉排序树
    if(!bst_l || MAX >= root->data)
        return false;
    MAX = root->data;  //保存当前结点关键字
    bst_r = Judge(root->rchild,MAX);//判断右子树是否为二叉排序树
    return bst_r;
}

9. 找出给定结点在二叉树中的层次

假设二叉树采用二叉链表存储。每查找一次就下降一层,因此查找该节点所用的次数就是该节点在二叉排序树中的层次。采用二叉树非递归查找,用n保存查找层次,,每查找一次,n++,直到找到相应节点。

int level(Bitree bt,BSTNode *p){
    //计算给定结点在二叉树的层次
    int n=0;     // 统计查找次数
    Bitree t=bt;
    if(bt!=NULL){
         n++;
         while(t->data!=p->data){
              if(t->data<p->data)
                  t=t->rchild;
              else 
                  t=t->lchild;
              n++;
         }
     }
     return n;
}

10. 判断二叉树是否为平衡二叉树

根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是一颗平衡二叉树。

bool isBalanced(BiTree root){
    if(!root) 
        return true; // 空树是平衡二叉树
    int Ldepth= Depth(root->Left);
    int Rdepth= Depth(root->Right);
    int diff=Ldepth-Rdepth;
    if(abs(diff)>1)
        return false;
    return isBalanced(root->Left) && isBalanced(root->Right);
}

 

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_41317652/article/details/88807049

智能推荐

用c++理解python的reduce函数_reduce sumop<lable> c++-程序员宅基地

文章浏览阅读664次。作为对一个平时靠c++吃饭的程序员来说,偶尔也想写点python程序,要想写就得要学,要学就得要总结和关联,把要学的知识与已学的知识相关联起来,可以更快地学习和理解新的知识。 首先看一下reduce()函数吧,http://www.cnblogs.com/lonkiss/p/understanding-python-reduce-function.html 有对reduce()函数的详细介绍和使用说明,下面的python代码都是参考的这个页面上的。 reduce() 函数在..._reduce sumop c++

WM8978学习_pz-wm8978-程序员宅基地

文章浏览阅读1w次,点赞2次,收藏7次。WM8978是一个低功耗的CODEC编解码芯片,输入支持line、MIC和输出处理。1、MIC输入两对立体MIC输入,信号的路径可以手动控制,或者ALC循环去控制MIC信号的电压。最大增益55.25db。ADC的输入支持可编程的增益放大 LINE输入(AUXL AUXR),可以做为背景输入。_pz-wm8978

Java Web 开发遇到的坑和注意点 涉及Jquery,Servlet等等_java web 遇过的坑-程序员宅基地

文章浏览阅读1.7k次。1.如果前端页面中使用表单的action和method的方式提交请求到后台的servlet,则在servlet处理完请求后,使用RequestDiapatcher.forward()或则Response.sendRediret()方法都可以实现跳转页面。但是请注意,如果前端页面中使用ajax的方式提交请求,则在servlet处理完请求后,使用RequestDiapatcher.forward()或_java web 遇过的坑

用css3实现ps蒙版效果+动画-程序员宅基地

文章浏览阅读397次。说实话,css3越来越强大,使用css也可以做越来越多意想不到的效果。今天,见到有人用css3实现了ps的蒙版效果,如下所示:实现原理这个动画,其实也并不复杂。它使用background-clip实现了文字蒙版的效果,然后结合了背景图片的animation实现了如上图所示的文字蒙版动画。用css3做蒙版效果常见的有两种,一种是..._ps中 视频中间轴 图形蒙版动画

React父子间通信_react父子通信-程序员宅基地

文章浏览阅读83次。父组件与子组件间的通信子组件获取父组件的信息父组件:<div className="father"> <Child age={this.state.age} name={this.state.name}></Child></div>子组件:出入的值存在this.props中this.props.agethis.props.name父组件获取子组件的信息1、回调函数的方式子组件:可直接调用子组件的propsthis.props_react父子通信

c++ builder在调试过程中捕获异常_cbuild 捕获异常不生效-程序员宅基地

文章浏览阅读2.2k次。一个困扰我N久的问题解决了,郁闷死我一直以来,用builder在调试时都不能捕获异常,一旦有异常发生,程序直接中断,trycatch放那儿跟没放一样但是直接运行程序时没有问题,今天受不了,到网上找了一下,NND郁闷死人原来在tools/debugger options/language exception/里可以设置真让人抓狂_cbuild 捕获异常不生效

随便推点

【Android】Android2D图像之Canvas_shapes redraw-程序员宅基地

文章浏览阅读942次。源代码下载:http://download.csdn.net/detail/yigelangmandeshiren/4989125package com.manning.aip.canvasdemo;import android.app.Activity;import android.content.Intent;import android.os.Bundle;import a_shapes redraw

Python之文件操作大全_python中关于文件的所以操作-程序员宅基地

文章浏览阅读10w+次,点赞3次,收藏63次。在日常工作或生活中,总避免不了需要操作文件或文件夹,比如希望找出电脑中所有临时文件并清除,或者找到指定文件夹内所有图片文件并进行重新命名等等,如果能通过Python脚本的方式解决,会大大提升相关操作效率,本文即总结使用Python进行常见操作相关知识点,方便用到的人随时查阅,不用再每次使用都要花费时间检索或查阅文档。本文主要使用os、shutil、pathlib三个包。一、文件操作1.1 文件常规操作操作 代码 说明/示例 新建文件 os.mknod(dir..._python中关于文件的所以操作

用python在excel表格中加入超链接图片_python在excel中给文件加超链接-程序员宅基地

文章浏览阅读988次。python在excel表格中加入超链接_python在excel中给文件加超链接

spring.sleuth.sampler.percentage=1采样率问题解决-程序员宅基地

文章浏览阅读4.6k次。spring.sleuth.sampler.percentage=1采样率问题解决spring.sleuth.sampler.probability=1,这是spring-cloud低版本配置的参数。高版本改成spring.sleuth.sampler.rate=1即可,亲测有效!..._spring.sleuth.sampler.percentage

elementUI——el-table组件滚动条的宽度设置——css基础_el-table滚动条宽度-程序员宅基地

文章浏览阅读1w次。今天在看后台管理系统时,领导发现表格中的横向和纵向的滚动条宽度不一致,导致页面看上去很不协调:如下:根据上图效果:会发现:横向滚动条的高度与纵向滚动条的宽度不一致:修改页面滚动条的宽高可以通过如下的css样式来处理:::-webkit-scrollbar { width: 7px; height: 7px; background-color: transparent;}只要将上面css中的width和height设置成一个数值,就可以保证横向滚动条的高度与纵向滚动条的_el-table滚动条宽度

java下划线转驼峰_java 下划线转驼峰-程序员宅基地

文章浏览阅读631次。写文档时需要用到下划线转驼峰的情况,在线工具不好用,自己写了一个可以批量转换的函数。_java 下划线转驼峰

推荐文章

热门文章

相关标签