#include<stdio.h>
#include<iostream.h>
#include<conio.h>
#include<malloc.h>
#include<stdlib.h>
#define ERROR 0
#define STACK_INIT_SIZE 100
#define OVERFLOW -1
#define FALSE 0
#define TRUE 1
#define OK 1
int i=0;
struct tree{
char data;
struct tree *Lchild,*Rchild;
};
typedef struct tree SElemType;
typedef int Status ;
struct STACK
{
SElemType *base;
SElemType *top;
int stacksize;
};
typedef struct STACK *pSqstack;
typedef struct STACK SqStack;
Status InitStack(SqStack **S)
{
(*S)=(SqStack *)malloc(sizeof(SqStack));
(*S)->base=(SElemType *)malloc(STACK_INIT_SIZE *sizeof(SElemType));
if(!(*S)->base) exit (OVERFLOW);
(*S)->top=(*S)->base;
(*S)->stacksize=STACK_INIT_SIZE;
return OK;
}
Status StackEmpty(SqStack S)
{
if(S.top==S.base) return TRUE;
else
return FALSE;
}
Status Push(SqStack *S,SElemType e)
{
*(S->top++)=e;
return OK;
}
Status Pop(SqStack *S,SElemType *e)
{
if(S->top==S->base) return ERROR;
e=--S->top;
return OK;
}
void Visite(struct tree *t)
{
if(t) printf("%c",t->data);
}
struct tree *create_btree(struct tree *t,struct tree *r,char data)//创建二叉树
{
if (r ==0 )
{
r=new (struct tree);
if ( r == 0)
{
printf("Out of memory/n"); return 0 ;
}
r->Lchild= 0; r->Rchild=0; r->data=data;
if (t)
{
if(data<t->data) t->Lchild=r;
else
t->Rchild=r;
}
else
{
r->Rchild=0; r->Lchild = 0;
}
return r;
}
if(data<r->data)
create_btree(r,r->Lchild,data);
else
create_btree(r,r->Rchild,data);
return t;
}
void PreOrderUnrec(struct tree *t,SqStack *s)//前序遍历二叉树
{
InitStack(&s);
struct tree *p,*q;
p=t;
while (p!=0||!StackEmpty(*s))
{
while (p!=0) //遍历左子树
{
Visite(p);
if((p->Lchild==0||p->Rchild==0)&&(p->Lchild!=p->Rchild))
{printf(" o ");
i++;};
Push(s,*p);
p=p->Lchild;
};//endwhile
while (!StackEmpty(*s)) //通过下一次循环中的内嵌while实现右子树遍历
{
Pop(s,p);
q=s->top;
//Pop(s,p);
p=q->Rchild;
Visite(p);
printf("?");
};//endif
};//endwhile
}//PreOrderUnrec
void main()
{
char s[100], e;
SqStack *Sa;
struct tree *t=0;
printf("Input a letter for Creating the Binary_Tree ( Directly press <Enter> to stop ):/n");
while (*s){
printf("/nInput a letter: ");
e=getch(); /*#include<conio.h>*/
putch(e); /*#include<conio.h>*/
if(e==13) break;
if (!t)
t=create_btree(t,t,e);
else
create_btree(t,t,e);
};
printf("/n");
PreOrderUnrec(t,Sa);
printf("度数为一的结点数为:%d",i);
printf("结束请按q!");
if(getchar()=='q') printf("再见");
else {while(1);};
}
分享到:
相关推荐
建立二叉树 能够求叶子结点个数 和度为2的结点个数
c 数据结构课程设计 通过先序遍历求二叉树各节点的度数。。。。。。
三角矩阵中的重复元素c可共享一个存储空间,其余的元素正好有n×(n+1)/2个,因此,三角矩阵可压缩到向量Sa[0……n×(n+1)/2]中,其中c存放在向量的最后一个分量中。用向量Sa[0……n×(n+1)/2]压缩存储下三角矩阵,...
本文实例讲述了C语言二叉树常见操作。分享给大家供大家参考,具体如下: 一、基本概念 ...对于完全二叉树,设一个结点为i则其父节点为i/2,2i为左子节点,2i+1为右子节点。 二、存储结构 顺序存储:
对于任意一棵二叉树,如果其叶结点为N0,而度数为2的结点总数为N2,则N0=N2+1 具有n个结点的完全二叉树的深度必为 log2(n+1) 对完全二叉树,若从上至下、从左只右编号,则编号为i的节点,其左孩子编号必为2i,其有...
e. 如有可能,请建立一个存储商品名称和数量的文本文件,并为二叉搜索树建立一个成员函数SetupInventory(),用于从该文本文件中读取库存商品的数据, 实验报告要求: 1、 按要求记录下二叉搜索树的完整实验...
1、假定在一棵二叉树中,度为2的分支结点个数为15,度为1的分支结点个数为30个,则叶子结点数为( B )。 A、15 B、16 C、17 D、47 1、在一个图中,所有顶点的度数之和等于所有边数的( B )倍。 A、1 B、2 C、3 D、...
定义:树是一个n(n>=0)个结点的有序合集 名词理解: ...数的度:指树中的最大结点度数; 叶子:度为0的结点,也称为终端结点; 高度:叶子节点的高度为1,根节点高度最高; 层:根在第一层,以此类推;
书中每一章都给出了一个算法、一种算法设计技术、一个应用领域或一个相关的主题。算法是用英语和一种“伪代码”来描述的,任何有一点程序设计经验的人都能看得懂。书中给出了230多幅图,说明各个算法的工作过程。...
性质3: 对于任意一棵二叉树,如果其叶结点数为N0,而度数为2的结点总数为N2,则N0=N2+1; 性质4: 具有n个结点的完全二叉树的深度必为 log2(n+1) 性质5: 对完全二叉树,若从上至下、从左至右编号,则编号为i 的结点,...
在一个图中,所有顶点的度数之和等于图的边数的 倍。 A.1/2 B. 1 C. 2 D. 4 ( B )2. 在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和的 倍。 A.1/2 B. 1 C. 2 D. 4 ( B )3. 有8个结点的无向图...
2.在一个无向图中,所有顶点的度数之和等于所有边数的 2 倍。 3. 由带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树,该树的带权路径长度为 44 。 4.由a,b,c三个结点构成的二叉树,共有 5 种不同形态。
书中每一章都给出了一个算法、一种算法设计技术、一个应用领域或一个相关的主题。算法是用英语和一种“伪代码”来描述的,任何有一点程序设计经验的人都能看得懂。书中给出了230多幅图,说明各个算法的工作过程。...
19.3 关键字减值和删除一个结点 19.4 最大度数的界 思考题 本章注记 第20章 van Emde Boas树 20.1 基本方法 20.2 递归结构 20.2.1 原型van Emde Boas结构 20.2.2 原型van Emde Boas结构上的...