C语言数据结构二叉树简单应用

 C语言数据结构二叉树简单应用

在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree),接下来我就在这里给大家介绍一下二叉树在算法中的简单使用:

我们要完成总共有

(1)二叉树的创建

(2)二叉树的先中后序递归遍历

(3)统计叶子结点的总数

(4)求树的高度

(5)反转二叉树

(6)输出每个叶子结点到根节点的路径

(7)输出根结点到每个叶子结点的路径。

定义二叉树结点类型的结构体

typedef struct node{
  char data;
  struct node *Lchild;
  struct node *Rchild;
}BiTNode,*BiTree;
int cnt=0;//统计叶子节点个数

二叉树的创建

BiTNode *Create(){ //二叉树的先序建立
  char ch;
  BiTNode *s;
  ch=getchar();
  if(ch=='#')erchashu
    return NULL;
  s=(BiTNode *)malloc(sizeof(BiTNode));
  s->data=ch;
  s->Lchild=Create();
  s->Rchild=Create();
  return s;
}

二叉树的先序、中序、后序递归遍历

void PreOrder(BiTree root){   //前序遍历
  if(root){
    printf("%c ",root->data);
    PreOrder(root->Lchild);
    PreOrder(root->Rchild);
  }
} 

void InOrder(BiTree root){   //中序遍历
  if(root){
    InOrder(root->Lchild);
    printf("%c ",root->data);
    InOrder(root->Rchild);
  }
} 

void PostOrder(BiTree root){    //后序遍历
  if(root){
    PostOrder(root->Lchild);
    PostOrder(root->Rchild);
    printf("%c ",root->data);
  }
}

统计叶子结点个数:

void LeafCountNode(BiTree root){  //统计叶子结点个数
  if(root){
    if(!root->Lchild && !root->Rchild)
      cnt++;
    LeafCountNode(root->Lchild);
    LeafCountNode(root->Rchild);
  }
}

输出各个叶子结点值:

void IInOrder(BiTree root){ //输出各个叶子结点值
  if(root){
    IInOrder(root->Lchild);
    if(!root->Lchild && !root->Rchild)
      printf("%c ",root->data);
    IInOrder(root->Rchild);
  }
}

求树的高度:

int PostTreeDepth(BiTree root){       //求树的高度
  int h1,h2,h;
  if(root==NULL){
    return 0;
  }
  else{
    h1=PostTreeDepth(root->Lchild);
    h2=PostTreeDepth(root->Rchild);
    h=(h1>h2?h1:h2)+1;
    return h;
  }
}

反转二叉树:

void MirrorTree(BiTree root){        //二叉树镜像树
  BiTree t;
  if(root==NULL)
    return;
  else{
    t=root->Lchild;
    root->Lchild=root->Rchild;
    root->Rchild=t;
    MirrorTree(root->Lchild);
    MirrorTree(root->Rchild);
  }
}

输出每个叶子结点到根节点的路径:

void OutPutPath(BiTree root,char path[],int len){      //输出每个叶子结点到根节点的路径
  if(root){
    if(!root->Lchild && !root->Rchild){
      printf("%c ",root->data);
      for(int i=len-1;i>=0;i--)
        printf("%c ",path[i]);
      printf("\n");
    }
    path[len]=root->data;
    OutPutPath(root->Lchild,path,len+1);
    OutPutPath(root->Rchild,path,len+1);
  }
}

输出根到每个叶子结点的路径:

void PrintPath(BiTree root,char path[],int l){     //输出根到每个叶子结点的路径
  int len=l-1;
  if(root){
    if(root->Lchild==NULL && root->Rchild==NULL){
      path[len]=root->data;
      for(int i=9;i>=len;i--)
        printf("%c ",path[i]);
      printf("\n");
    }
    path[len]=root->data;
    PrintPath(root->Lchild,path,len);
    PrintPath(root->Rchild,path,len);
  }
}

测试代码:

int main(void){
  int h,len;
  char path[20];
  BiTree root;
  root=Create();
// PreOrder(root);
// printf("\n");
// InOrder(root);
// printf("\n");
// PostOrder(root);
// printf("\n");
// LeafCountNode(root);
// printf("叶子结点个数为:%d\n",cnt);
// IInOrder(root);
  h=PostTreeDepth(root);
  printf("树的高度为:High=%d\n",h);
// PrintTree(root,0);
// MirrorTree(root);
// PrintTree(root,0);
// OutPutPath(root,path,0);
// PrintPath(root,path,10);
  return 0;
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

时间: 2017-05-21

C语言实现线索二叉树的定义与遍历示例

本文实例讲述了C语言实现线索二叉树的定义与遍历.分享给大家供大家参考,具体如下: #include <stdio.h> #include <malloc.h> typedef char TElemType; // 二叉树的二叉线索存储表示 typedef enum{ Link, Thread }PointerTag; // Link(0):指针,Thread(1):线索 typedef struct BiThrNode { TElemType data; struct BiThrN

使用C语言构建基本的二叉树数据结构

二叉树结构常用的一些初始化代码 #include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* 初始化一棵二叉树排序树. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memory allocation for r

C语言 二叉树的链式存储实例

二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

举例讲解C语言程序中对二叉树数据结构的各种遍历方式

二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF 2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后输

C语言 数据结构平衡二叉树实例详解

数据结构平衡二叉树 参考代码如下: /* 名称:平衡二叉树 语言:数据结构C语言版 编译环境:VC++ 6.0 日期: 2014-3-26 */ #include <stdio.h> #include <malloc.h> #include <windows.h> #define LH +1 // 左高 #define EH 0 // 等高 #define RH -1 // 右高 #define N 5 // 数据元素个数 typedef char KeyType; /

C语言实现二叉树的搜索及相关算法示例

本文实例讲述了C语言实现二叉树的搜索及相关算法.分享给大家供大家参考,具体如下: 二叉树(二叉查找树)是这样一类的树,父节点的左边孩子的key都小于它,右边孩子的key都大于它. 二叉树在查找和存储中通常能保持logn的查找.插入.删除,以及前驱.后继,最大值,最小值复杂度,并且不占用额外的空间. 这里演示二叉树的搜索及相关算法: #include<stack> #include<queue> using namespace std; class tree_node{ public

c语言版本二叉树基本操作示例(先序 递归 非递归)

复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

C语言中计算二叉树的宽度的两种方式

C语言中计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo

详解python中字典的循环遍历的两种方式

开发中经常会用到对于字典.列表等数据的循环遍历,但是python中对于字典的遍历对于很多初学者来讲非常陌生,今天就来讲一下python中字典的循环遍历的两种方式. 注意: python2和python3中,下面两种方法都是通用的. 1. 只对键的遍历 一个简单的for语句就能循环字典的所有键,就像处理序列一样: d = {'name1' : 'pythontab', 'name2' : '.', 'name3' : 'com'} for key in d: print (key, ' value

Java web开发中加载图片路径的两种方式

(1)   src="/image/1_it.jpg" (2)   src="http://localhost:8080/image/1_it.jpg" 其中localhost可以换位你的电脑IP,端口号也要相应改变. 以上均在基于编译器idea以及tomcat服务器开发的web中测试可行!都是要先定位到项目的位置! 以上所述是小编给大家介绍的Java web开发加载图片路径的两种方式,希望对大家有所帮助,如果大家有任何疑问欢迎给我留言,小编会及时回复大家的!

Android中Rxjava实现三级缓存的两种方式

本文正如标题所说的用rxjava实现数据的三级缓存分别为内存,磁盘,网络,刚好最近在看Android源码设计模式解析与实战(受里面的ImageLoader的设计启发). 我把代码放到了我的hot项目中,github地址 源码下载地址:Rxjava_jb51.rar 1.使用concat()和first()的操作符. 2.使用BehaviorSubject. 先说BehaviorSubject的实现方法,废话不多说直接上代码, /** * Created by wukewei on 16/6/20

在AOP中Spring生成代理类的两种方式

Java 动态代理.具体有如下四步骤: 通过实现 InvocationHandler 接口创建自己的调用处理器: 通过为 Proxy 类指定 ClassLoader 对象和一组 interface 来创建动态代理类: 通过反射机制获得动态代理类的构造函数,其唯一参数类型是调用处理器接口类型: 通过构造函数创建动态代理类实例,构造时调用处理器对象作为参数被传入. 在AOP中,Spring通过生成代理类,来完成切面的织入. Spring生成代理类有2种方式. 如果目标对象实现的是一个接口,Sprin

Android中button实现onclicklistener事件的两种方式

复制代码 代码如下: package com.demos; import android.app.Activity; import android.os.Bundle; import android.view.View; import android.view.View.OnClickListener; import android.widget.Button; public class GetScreenActivity extends Activity { private Button fi

React中常见的动画实现的几种方式

现在,用户对于前端页面的要求已经不能满足于实现功能,更要有颜值,有趣味.除了整体 UI 的美观,在合适的地方添加合适的动画效果往往比静态页面更具有表现力,达到更自然的效果.比如,一个简单的 loading 动画或者页面切换效果不仅能缓解用户的等待情绪,甚至通过使用品牌 logo 等形式,默默达到品牌宣传的效果. React 作为最近几年比较流行的前端开发框架,提出了虚拟 DOM 概念,所有 DOM 的变化都先发生在虚拟 DOM 上,通过 DOM diff 来分析网页的实际变化,然后反映在真实 D

javaScript中定义类或对象的五种方式总结

第一种方式: 工厂方法 能创建并返回特定类型的对象的工厂函数(factory function). function createCar(sColor){ var oTempCar = new Object; oTempCar.color = sColor; oTempCar.showColor = function (){ alert(this.color); }; return oTempCar; } var oCar1 = createCar(); var oCar2 = createCa

Android 中Popwindow弹出菜单的两种方法实例

Android 中Popwindow弹出菜单的两种方法实例 1.popWindow就是对话框的一种方式! 此文讲解的android中对话框的一种使用方式,它叫popWindow. 2.popWindow的特性 Android的对话框有两种:PopupWindow和AlertDialog.它们的不同点在于: AlertDialog的位置固定,而PopupWindow的位置可以随意. AlertDialog是非阻塞线程的,而PopupWindow是阻塞线程的. PopupWindow的位置按照有无偏

mybatis 映射文件中if标签判断字符串相等的两种方式

mybatis 映射文件中,if标签判断字符串相等,两种方式: 因为mybatis映射文件,是使用的ognl表达式,所以在判断字符串sex变量是否是字符串Y的时候, <if test="sex=='Y'.toString()"> <if test = 'sex== "Y"'> 注意: 不能使用 <if test="sex=='Y'"> and 1=1 </if> 因为mybatis会把'Y'解析为字