求数据结构(C语言版)建立二叉树的代码~~急~~谢谢了
发布网友
发布时间:2022-04-25 12:42
我来回答
共3个回答
热心网友
时间:2022-04-18 23:19
BT.H文件
#include
<stdio.h>
#include
<malloc.h>
#include
<conio.h>
#define
TRUE
1
#define
FALSE
0
#define
ERROR
0
#define
OK
1
#define
Stack_Size
50
#define
NUM
50
#define
MAXSIZE
50
//队列的最大长度
//定义二叉树
typedef
char
DataType;
typedef
struct
Node
{
DataType
data;
struct
Node
*LChild;
struct
Node
*RChild;
}BiTNode,
*BiTree;
//定义stack
typedef
BiTree
StackElementType;
typedef
struct
{
StackElementType
elem[Stack_Size];
int
top;
}SeqStack;
//定义队列
typedef
BiTree
QueueElementType;
typedef
struct
{
QueueElementType
element[MAXSIZE];
int
front;
int
rear;
}SeqQueue;
//队列的抽象
void
InitQueue(SeqQueue
*Q)
{
Q->front=Q->rear=0;
}
int
EnterQueue(SeqQueue
*Q,
QueueElementType
x)
{
if((Q->rear+1)%MAXSIZE==Q->front)
return(FALSE);
Q->element[Q->rear]=x;
Q->rear=(Q->rear+1)%MAXSIZE;
return(TRUE);
}
热心网友
时间:2022-04-19 00:37
c++的要不要
热心网友
时间:2022-04-19 02:11
二叉树具有以下重要性质:
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明:用数学归纳法证明:
归纳基础:i=1时,有2i-1=20=1。因为第1层上只有一个根结点,所以命题成立。
归纳假设:假设对所有的j(1≤j<i)命题成立,即第j层上至多有2j-1个结点,证明j=i时命题亦成立。
归纳步骤:根据归纳假设,第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子,故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时,该层上至多有2×2i-2=2i-1个结点,故命题成立。
性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明:在具有相同深度的二叉树中,仅当每一层都含有最大结点数时,其树中结点数最多。因此利用性质1可得,深度为k的二叉树的结点数至多为:
20+21+…+2k-1=2k-1
故命题正确。
性质3 在任意-棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则no=n2+1。
证明:因为二叉树中所有结点的度数均不大于2,所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和:
n=no+n1+n2 (式子1)
另一方面,1度结点有一个孩子,2度结点有两个孩子,故二叉树中孩子结点总数是:
nl+2n2
树中只有根结点不是任何结点的孩子,故二叉树中的结点总数又可表示为:
n=n1+2n2+1 (式子2)
由式子1和式子2得到:
no=n2+1
满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二又树称为满二叉树。
满二叉树的特点:
(1) 每一层上的结点数都达到最大值。即对给定的高度,它是具有最多结点数的二叉树。
(2) 满二叉树中不存在度数为1的结点,每个分支结点均有两棵高度相同的子树,且树叶都在最下一层上。
【例】图(a)是一个深度为4的满二叉树。
2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2,并且最下一层上的结点都集中在该层最左边的若干位置上,则此二叉树称为完全二叉树。
特点:
(1) 满二叉树是完全二叉树,完全二叉树不一定是满二叉树。
(2) 在满二叉树的最下一层上,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
(3) 在完全二叉树中,若某个结点没有左孩子,则它一定没有右孩子,即该结点必是叶结点。
【例】如图(c)中,结点F没有左孩子而有右孩子L,故它不是一棵完全二叉树。
【例】图(b)是一棵完全二叉树。
性质4 具有n个结点的完全二叉树的深度为
证明:设所求完全二叉树的深度为k。由完全二叉树定义可得:
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树,一共有2k-1-1个结点。
由于完全二叉树深度为k,故第k层上还有若干个结点,因此该完全二叉树的结点个数:
n>2k-1-1。
另一方面,由性质2可得:
n≤2k-1,
即:2k-1-l<n≤2k-1
由此可推出:2k-1≤n<2k,取对数后有:
k-1≤lgn<k
又因k-1和k是相邻的两个整数,故有
,
由此即得:
注意:
的证明【参见参考书目】
回答者:杰清 - 经理 五级 1-16 09:35
前序遍历
void preorder(btree *p)
{
if(p!=NULL)
{ printf("%d",p->data);
preorder(p->left);
preorder(p->right);
}
}
中序遍历
void inorder(btree *p)
{
if(p!=NULL)
{ inorder(p->left);
printf("%d",p->data);
inorder(p->right);
}
}
后序遍历
void postorder(btree *p)
{
if(p!=NULL)
{ postorder(p->left);
postorder(p->right);
printf("%d",p->data);
}
}
#include <stdio.h>
#include <iostream>
#include <queue>
#include <stack>
#include <malloc.h>
#define SIZE 100
using namespace std;
typedef struct BiTNode //定义二叉树节点结构
{
char data; //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
int visit(BiTree t);
void CreateBiTree(BiTree &T); //生成一个二叉树
void PreOrder(BiTree); //递归先序遍历二叉树
void InOrder(BiTree); //递归中序遍历二叉树
void PostOrder(BiTree); //递归后序遍历二叉树
void InOrderTraverse(BiTree T); //非递归中序遍历二叉树
void PreOrder_Nonrecursive(BiTree T);//非递归先序遍历二叉树
void LeverTraverse(BiTree T);//非递归层序遍历二叉树
//主函数
void main()
{
BiTree T;
char j;
int flag=1;
//---------------------程序解说-----------------------
printf("本程序实现二叉树的操作。\n");
printf("叶子结点以空格表示。\n");
printf("可以进行建立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。\n");
//----------------------------------------------------
printf("\n");
printf("请建立二叉树。\n");
printf("建树将以三个空格后回车结束。\n");
printf("例如:1 2 3 4 5 6 (回车)\n"); CreateBiTree(T); //初始化队列
getchar();
while(flag)
{
printf("\n");
printf("请选择: \n");
printf("1.递归先序遍历\n");
printf("2.递归中序遍历\n");
printf("3.递归后序遍历\n");
printf("4.非递归中序遍历\n");
printf("5.非递归先序遍历\n");
printf("6.非递归层序遍历\n");
printf("0.退出程序\n");
scanf(" %c",&j);
switch(j)
{
case '1':if(T)
{
printf("递归先序遍历二叉树:");
PreOrder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '2':if(T)
{
printf("递归中序遍历二叉树:");
InOrder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '3':if(T)
{
printf("递归后序遍历二叉树:");
PostOrder(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '4':if(T)
{
printf("非递归中序遍历二叉树:");
InOrderTraverse(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '5':if(T)
{
printf("非递归先序遍历二叉树:");
PreOrder_Nonrecursive(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
case '6':if(T)
{
printf("非递归层序遍历二叉树:");
LeverTraverse(T);
printf("\n");
}
else printf("二叉树为空!\n");
break;
default:flag=0;printf("程序运行结束,按任意键退出!\n");
}
}
}
//建立二叉树
void CreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch); //读入一个字符
if(ch==' ') T=NULL;
else
{
T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一个新结点
T->data=ch;
CreateBiTree(T->lchild); //生成左子树
CreateBiTree(T->rchild); //生成右子树
}
}
//先序遍历的递归
void PreOrder(BiTree T)
{
if(T)
{
printf("%c ",T->data); //访问结点
PreOrder(T->lchild); //遍历左子树
PreOrder(T->rchild); //遍历右子树
}
}
//中序遍历的递归
void InOrder(BiTree T)
{
if(T)
{
InOrder(T->lchild); //遍历左子树
printf("%c ",T->data); //访问结点
InOrder(T->rchild); //遍历右子树
}
}
//后序遍历的递归
void PostOrder(BiTree T)
{
if(T)
{
PostOrder(T->lchild); //遍历左子树
PostOrder(T->rchild); //访问结点
printf("%c ",T->data); //遍历右子树
}
}
//非递归中序遍历
void InOrderTraverse(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);//跟指针进栈
while(!S.empty())
{
p=new BiTNode;
while((p=S.top())&&p)
S.push(p->lchild);//向左走到尽头
S.pop(); //空指针退栈
if(!S.empty())
{
p=S.top();
S.pop();
cout<<p->data<<" ";
S.push(p->rchild);
}
}
}
//先序遍历的非递归
void PreOrder_Nonrecursive(BiTree T)
{
stack<BiTree> S;
BiTree p;
S.push(T);//根指针进栈
while(!S.empty())//栈空时结束
{
while((p=S.top())&&p)
{
cout<<p->data<<" ";
S.push(p->lchild);
}//向左走到尽头
S.pop();//弹出堆栈
if(!S.empty())
{
p=S.top();
S.pop();
S.push(p->rchild);//向右走一步
}
}
}
void LeverTraverse(BiTree T)
{//非递归层次遍历
queue <BiTree> Q;
BiTree p;
p = T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if(visit(p->lchild) == 1)
Q.push(p->lchild);
if(visit(p->rchild) == 1)
Q.push(p->rchild);
}
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
数据结构中用c语言建立二叉树的程序
include "stdio.h"include "stdlib.h"include "malloc.h"typedef struct Bnode //二叉树节点类型 { int m;struct Bnode *Lchild,*Rchild;}Btnode, *BTptr;typedef struct Dnode //队列节点类型 { Btnode *pr;struct Dnode *next;}Qnode,*Qlink;typedef struct //q节点类型 { Qnod...
数据结构中关于用c++语言建立二叉树的问题,求代码,急!!!
void preOrder(BiTree root)/*先序遍历二叉树, root为指向二叉树根结点的指针*/ { if (root!=NULL){ printf("%c",root->data); /*输出结点*/ preOrder(root ->LChild);/*先序遍历左子树*/ preOrder(root ->RChild); /*先序遍历右子树*/ } } void inOrder(BiTree root){ i...
c语言 关于二叉树的创建和遍历(中序遍历)
define MaxSize 10 define Number 30 struct BiTNode{//定义数据结构 char data;BiTNode *lchild,*rchild;};void InitBtree(BiTNode * &BT){//初始化二叉树 BT=NULL;} void CreateBiTree(BiTNode *&BT,char *str){//建立二叉树 BiTNode *s[MaxSize];//这里定义了一个数组用作堆栈方便检查输入...
关于数据结构C语言二叉树的程序,请人帮忙看看~谢谢
/*printf("Input the char\n"); //你把输出语句放到递归的函数里它会输出N多遍,所以,还是放到主函数里吧 */ scanf("%c",&ch); //你忘了取地址符了 /*if(ch == '#')T==NULL;*/ if(ch == '#')T=NULL;//是将T指针赋值为空,而不是T==NULL;else{ if(!(T=(BiTNode *)...
数据结构-二叉树的创建?
二叉树建立实现代码一,如下所示。//创建树//按先后次序输入二叉树中结点的值(一个字符),#表示空树//构造二叉链表表示的二叉树BiTree CreateTree(BiTree t){ char ch; scanf("%c", &ch); if(ch == '#') { t = NULL; } else { t = (BitNode *)malloc...
建立一棵二叉树,数据以字符串形式从键盘输入。
代码如下:char a[105];int len,i;//i逐渐增加 void build(int s){ if(i==len) return;//已经建完树了 char c=a[i];//当前的字符 i++;if(!tree[s].l) tree[s].l=c;//如果树的左边是空的,就给左边赋值 else tree[s].r=c;//反之 if(c!=' ') build(c);if(c...
请问C语言如何创建二叉树???
创建二叉树的源程序如下:include <cstdlib> include <stdio.h> typedef struct node { //树的结点 int data;struct node* left;struct node* right;} Node;typedef struct { //树根 Node* root;} Tree;void insert(Tree* tree, int value)//创建树 { Node* node=(Node*)malloc(sizeof(...
c语言数据结构 递归创建二叉树的函数如何输入退出?这个函数一直让输入...
递归创建二叉树的输入是有讲究的,可参考:网页链接中最后的输入示例:如果你用#作为结束,则对应输入:1 2 4 # 6 ###3 #5 #7 #8 再给个递归创建二叉树的例子:include <stdio.h>#include <stdlib.h>typedef struct Tree { int Val; struct Tree* left; struct Tree* right;}Tr...
数据结构二叉树的基本操作~~~
typedef struct BiTNode{ //定义链式二叉树结构体 char data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;BiTree T;char ch;int flag=0;int createBiTree(BiTree &T){ //按先序输入二叉树中结点的值(一个字符),空格表示空树 ch=getchar();if(ch==' ')T=NULL; //表示空树 else...
求数据结构高手编个程序搞定实验。二叉树创建、先序遍历读出、中序遍历...
/* 先序建立二叉树 */ BiTree *CreateBiTree(BiTree *T);//返回指向该树根节点的指针 /* 先序遍历二叉树 */ Status PreOrderTraverse(BiTree *head);/* 中序遍历二叉树 */ Status InOrderTraverse(BiTree *head);/* 后序遍历二叉树 */ Status PostOrderTraverse(BiTree *head);/* 求...