文档章节

二叉树的性质以及二叉树的遍历(非递归)(c语言)(一)

奔跑的码农
 奔跑的码农
发布于 2016/05/14 15:37
字数 897
阅读 325
收藏 7

二叉树的性质:

性质 1 在二叉树的第i层上至多有2^(i-1)个结点(i>=1)。

性质 2 深度为k的二叉树至多有2^k-1个结点,(k>=1)。

性质 3 任何一颗二叉树,终端结点为n0,度为2的结点为n2,那么n0=n2+1。

性质 4  具有n个结点的完全二叉树的深度为└㏒2 n┘+1。

性质 5 完全二叉树按层次从上到下从左到右依次编号。编号为n的节点的左孩子为2n。

二叉树的储存结构

lchild data rchild
/*---------二叉树的二叉链表储存表示----------*/
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode ,*BiTree;

非递归遍历需要栈:栈的实现过程:栈的线性储存结构与链式储存结构的实现(C语言)

栈部分的内容:

typedef BiTree pElemType;
typedef struct Snode //栈的储存结构 
{
    pElemType data;	//数据域 

    struct Snode *next; //指针域 
}Snode,*LinkStack;
void Init_StackL(LinkStack *S)	//初始化院栈 
{
    *S=NULL;
}
Status Push_L(LinkStack *S,pElemType x) 	//压栈 
{
    LinkStack p;
    p=(LinkStack)malloc(sizeof(Snode)); 
    p->data=x;

    p->next=*S;

    *S=p;
    return 1;
}
Status Pop_L(LinkStack *S,pElemType *temp_) //出栈 
{
    LinkStack p;
    pElemType temp;
    if(*S==NULL) return 0;

    temp=(*S)->data;

    p=*S;

    *S=p->next;
    free(p);

    *temp_=temp;
    return 1;
}
Status StackEmpty(LinkStack *S) 	//判断栈顶是否为空 如果为空返回 0 
{
    if(*S==NULL) return 0;

    else
        return 1;
}

以下为二叉树部分:

Status CreateBiTree(BiTNode **T)	//先序生成二叉树 
{
    int ch;

    scanf("%d",&ch);
    if(ch==0) *T=NULL;
    else{
        if(!(*T=(BiTNode *)malloc(sizeof(BiTNode))))exit(0);
        (*T)->data=ch;
        CreateBiTree(&(*T)->lchild);
    
        CreateBiTree(&(*T)->rchild);
    }
    return 1;
}
}
Status preOrderTraverse(BiTNode *T)//前序遍历二叉树,并统计总结点 
{
	int i=0;
    LinkStack S;
    BiTNode *p;
    p=T;
    Init_StackL(&S);
    while(p||StackEmpty(&S)){//StackEmpty(&S)判断栈顶是否为空 如果为空返回 0 
        if(p){
            Push_L(&S,p);
      		     printf("%d\t",p->data);
      		     i++;
            p=p->lchild; 

        }
        else{
            Pop_L(&S,&p);
 
            if(!(p->data)) return 0;
       
            p=p->rchild;
        }
    }
  //  return 1;
	printf("\n所有生成节点的总数为:%d\n",i);//总结点	
} 
Status InOrderTraverse(BiTNode *T)	//中序遍历二叉树 
{

    LinkStack S;
    BiTNode *p;
    p=T;
    Init_StackL(&S);
    while(p||StackEmpty(&S)){//StackEmpty(&S)判断栈顶是否为空 如果为空返回 0 
        if(p){
            Push_L(&S,p);
      
            p=p->lchild; 

        }
        else{
            Pop_L(&S,&p);
 
            if(!(p->data)) return 0;
            printf("%d\t",p->data);
            p=p->rchild;
        }
    }
    return 1;
}
void postorder(BiTNode *T)//用递归的方法后续遍历二叉树 
{
	if(T!=NULL)
	{
		postorder(T->lchild);
		postorder(T->rchild);
		printf("%d\t",T->data);
	}
}

以下为测试函数,先序生成二叉树:如果为结点空则输入 0。

我们输入的数据为:1 2 4 0 0 5 0 0 3 0 0 ;

void main()
{
    BiTNode *T;
        printf("请按如下图案先序生成链表,0代表为空:\n");
	printf("        ①\n");
	printf("      ╱   ╲\n");
	printf("    ②       ③ \n");
	printf("  ╱   ╲\n");
	printf("④       ⑤ \n");
	printf("输入的数字是1 2 4 0 0 5 0 0 3 0 0 "); 
    CreateBiTree(&T);
   	printf("        ①\n");
	printf("      ╱   ╲\n");
	printf("    ②       ③ \n");
	printf("  ╱   ╲\n");
	printf("④       ⑤ \n");
   	printf("中序遍历二叉树的结果为:");
    InOrderTraverse(T);
	printf("\n后续遍历二叉树的结果为:");
    postorder(T);//用递归的方法后续遍历二叉树 
   	printf("\n前序遍历二叉树的结果为: ");
   	preOrderTraverse(T);
   	printf("\n");
}

程序运行的结果为:

正在加载图片


学习数据结构记录,如有错误欢迎指正。

参考书:数据结构 c语言版

© 著作权归作者所有

共有 人打赏支持
奔跑的码农

奔跑的码农

粉丝 15
博文 31
码字总数 37901
作品 0
海淀
程序员
私信 提问
数据结构-二叉树的存储结构与遍历

定义 一个有穷的结点集合,可以为空。若不为空,则它是由根结点和称为其左子树和右子树的两个互不相交的二叉树组成。 二叉树的五种基本形态: tree_state 二叉树的子树是有顺序之分的,称为左...

IAM四十二
2017/10/24
0
0
数据结构分析之二叉树

概述 在分析树形结构之前,先看一下树形结构在整个数据结构中的位置 数据结构 当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说...

wustor
2017/11/06
0
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0
python环境下使用mysql数据及数据结构和二叉树算法(图)

python环境下使用mysql数据及数据结构和二叉树算法(图): 1 python环境下使用mysql 2使用的是 pymysql库 3 开始-->创建connection-->获取cursor-->操作-->关闭cursor->关闭connection->结束......

原创小博客
2018/08/26
0
0
数据结构之树

数据结构之树 目录: 二叉树的结构 二叉树的性质 二叉树的遍历 二叉树的特例 二叉树典型程序 树是一种编程中常常用到的一种数据结构,它的逻辑是:除了根结点之外每个结点只有一个父结点,根...

花开半夏qb
2016/11/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

听说拼多多因漏洞被薅了200亿?- 谈谈软件测试

昨天看到一个大新闻:拼多多在20日凌晨出现漏洞,用户可以领100元无门槛优惠券。一夜之间,被黑产、羊毛党和闻讯而来的吃瓜群众薅了个底朝天,直到第二天上午9点才将优惠券下架。网上传言这一...

crossin
31分钟前
2
0
微服务架构有毒,何时不使用微服务?

在过去的四年中,使用微服务来构建应用程序似乎成了一种标准。大多数我所合作过的团队也对此表现出了不同程度的兴趣。 微服务所承诺的弹性、高可用、低耦合、敏捷,以及能够解决单体架构带来...

架构师springboot
37分钟前
2
0
日志服务Python消费组实战(三):实时跨域监测多日志库数据

摘要: 本文主要介绍如何使用消费组实时监控多个域中的多个日志库中的异常数据,并进行下一步告警动作。具备配置简单、逻辑灵活、支持跨域多Region、实时监测,无需配置索引等特点,并且性能...

阿里云云栖社区
37分钟前
2
0
常用css动效

1.列表浮层变化动效 demo地址 下载地址 2.js动画库 github地址 3.滚动加载 Scrollreveal 4.其他动效 tobiasahlin

chinahufei
38分钟前
3
0
Coding and Paper Letter(四十六)

资源整理。 1 Coding: 1.卫星影像深度学习资源。 satellite image deep learning 2.runoff tools为MOM生成径流文件的一些工具变得轻而易举。 runoff tools 3.NOAA-GFDL海冰模拟器V2.0。 SIS2...

胖胖雕
40分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部