`
- 浏览:
1003345 次
- 性别:
- 来自:
北京
-
这次是树的基本操作,包括生成树,求树深度,求叶子节点个数。。。
附上二叉树的几个重要性质及证明(考研必考)。
1.在二叉树的第i层至多有2^(i-1)个结点;
2.深度为k的二叉树至多有2^(k)-1 个结点;
3.对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1;(n=n0+n1+n2=n1+2n2+1);
4.具有n哥节点的完全二叉树深度为【log2n】+1;
#include <stdio.h>
#include<stdlib.h>
#define maxSize 20
#define maxWidth 20
typedef struct node
{
char data;
struct node *left,*right;
}Btree;
Btree* createNode(char ch,Btree *l,Btree *r);
//先序遍历
void preOrder(Btree *BT)
{
if(BT!=
NULL)
{
printf("%c",BT->data);
preOrder(BT->left);
preOrder(BT->right);
}
}
//中序遍历
void inOrder(Btree *BT)
{
if(BT!=
NULL)
{
inOrder(BT->left);
printf("%c",BT->data);
inOrder(BT->right);
}
}
//后序遍历
void postOrder(Btree *BT)
{
if(BT!=
NULL)
{
postOrder(BT->left);
postOrder(BT->right);
printf("%c",BT->data);
}
}
//从括号表达式生成树
void createTree(Btree **BT,char *str)//create a tree BT according by hollow function str
{
Btree *stack[maxSize],*p;
int top=-1,k,j=0;//top is the point of stack,k is the tab of son,j is the point of str;
char ch;
*BT=NULL;
ch=str[j];
while(ch!=NULL)
{
switch(ch)
{
case'(':top++;stack[top]=p;k=1;//left son,push to stack
break;
case')':top--;//pop stack
break;
case ',':k=2;//right son
break;
default:
/*p=(Btree *)malloc(sizeof(Btree));//set a node
if(!(p))
{
exit(0);
}
p->data=ch;
p->left=p->right=NULL;*/
p=createNode(ch,NULL,NULL);
if(*BT==NULL)//the root node
{
*BT=p;
}
else
{
switch(k)
{
case 1:stack[top]->left=p;
break;
case 2:stack[top]->right=p;
break;
default:
;
}
}
}
j++;
ch=str[j];//get next char
}
}
/*
void createTree(Btree **BT,char *str)
{
int j=0;//top is the point of stack,k is the tab of son,j is the point of str;
Btree *T;
char ch;
ch=str[j];
if(ch=='') *BT=NULL;
else
{
if(!(T=))
}
}
*/
//生成节点
Btree* createNode(char ch,Btree *l,Btree *r)
{
printf("Create now!\n");
Btree *p;
p=(Btree *)malloc(sizeof(Btree));//set a node
if(!(p))
{
exit(0);
}
p->data=ch;
p->left=l;
p->right=r;
return p;
}
//复制树
//copy a tree and return the new tree's point
Btree* copyTree(Btree *T)
{
Btree *newptl,*newptr,*newT;
if(!T) return NULL;
if(T->left!=NULL)
{
newptl=copyTree(T->left);
}
else newptl=NULL;
if(T->right!=NULL) newptr=copyTree(T->right);
else newptr=NULL;
newT=createNode(T->data,newptl,newptr);
//newT=createNode(T->data,NULL,NULL);
//newT=NULL;
return newT;
}
//层次法打印树
void disptree(Btree *BT)
{
Btree *stack[maxSize],*p;
int level[maxSize][2],top,n,i,width=4;
if(BT!=NULL)
{
printf("Display a tree by hollow means.\n");
top=1;
stack[top]=BT;//push root point to stack.
level[top][0]=width;
while(top>0)
{
p=stack[top];
n=level[top][0];
for(i=1;i<=n;i++)
printf(" ");
printf("%c",p->data);
for(i=n+1;i<maxWidth;i+=2)
printf("--");
printf("\n");
top--;
if(p->right!=NULL)
{
top++;
stack[top]=p->right;
level[top][0]=n+width;
level[top][1]=2;
}
if(p->left!=NULL)
{
top++;
stack[top]=p->left;
level[top][0]=n+width;
level[top][1]=1;
}
}
}
}
int TreeDepth(Btree *BT)//calculate the depth of tree
{
int leftDep,rightDep;
if(BT==NULL) return 0;
else
{
leftDep=TreeDepth(BT->left);
rightDep=TreeDepth(BT->right);
if(leftDep>rightDep) return(leftDep+1);
else return (rightDep+1);
}
}
int NodeCount(Btree *BT)//cout the nodes
{
if(BT==NULL) return 0;
else return (NodeCount(BT->left)+NodeCount(BT->right)+1);
}
int LeafCount(Btree *BT)//count the leafnodes
{
if(BT==NULL) return 0;
else if(BT->left==NULL&&BT->right==NULL) return 1;
else return (LeafCount(BT->left)+LeafCount(BT->right));
}
void PrintTree(Btree *BT)//print tree
{
if(BT!=NULL)
{
printf("%c",BT->data);
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintTree(BT->left);
if(BT->right!=NULL) printf(",");
PrintTree(BT->right);
printf(")");
}
}
}
main()
{
Btree *B,*C;
char *s="A(B(D,E(H,I)),C(G))";
createTree(&B,s);
printf("preOder:");
preOrder(B);
printf("\n");
printf("inOder:");
inOrder(B);
printf("\n");
printf("postOder:");
postOrder(B);
printf("\n");
printf("Display tree\n");
disptree(B);
printf("copy tree\n");
//disptree(B);
C=copyTree(B);
preOrder(C);
disptree(C);
printf("Deep: %d\n",TreeDepth(B));
printf("Sum of nodes: %d\n",NodeCount(B));
printf("Sum of leafnodes: %d\n",LeafCount(B));
PrintTree(B);
printf("\nHello,world!");
}
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 复习 课程 下载 数学考研 ...
天勤2019数据结构计算机考研复习指导电子版PDF 天勤2019操作系统计算机考研复习指导电子版PDF. 天勤2019计算机组成原理计算机考研复习指导无水印版. 天勤2019年计算机网络(高清版)
分享给时间不够又急于找资源的同学们,实在木有积分的可以私信。
王道2019年操作系统考研复习指导,考研复习,北站秋招,完美
《数据结构》 考研 复习 精编 pdf《数据结构》 考研 复习 精编 pdf《数据结构》 考研 复习 精编 pdf《数据结构》 考研 复习 精编 pdf《数据结构》 考研 复习 精编 pdf《数据结构》 考研 复习 精编 pdf《数据结构》 ...
校定操作系统考研复习提纲,很全面,共65页,内部资料。
数据结构考研复习资料数据结构考研复习资料
扫描版图书,用来复习操作系统原理核心知识点。
操作系统复习题 ,按照这个复习考研没问题。
王道的2019操作系统考研复习资料,希望对2019计算机考研的同学有帮助,绝对不存在欺骗,可能清晰度不够高,但是基本上不影响使用
考研复习方考研 复习 方法 考研 考研法考研 复习 方法 考研 考研
[计算机考研]《数据结构》考研复习精编.pdf 挺不错的 可以看下,祝大家考研顺利。计算机考研《数据结构》考研复习精编。计算机考研《数据结构》考研复习精编
操作系统考研复习PPT课件.pptx
数据结构考研复习重点归纳 数据结构考研复习重点归纳 数据结构考研复习重点归纳
考研计算机操作系统习题与解析 是一个很好的考研复习资料。
计算机组成原理考研复习课件 计算机组成原理考研复习课件
遥感导论考研复习资料 遥感导论考研复习资料 遥感导论考研复习资料 遥感导论考研复习资料 遥感导论考研复习资料 遥感导论考研复习资料 遥感导论考研复习资料
计算机网络 考研 复习 资料计算机网络 考研 复习 资料计算机网络 考研 复习 资料计算机网络 考研 复习 资料计算机网络 考研 复习 资料计算机网络 考研 复习 资料计算机网络 考研 复习 资料计算机网络 考研 复习 资料...
给16考研党:史上最全考研复习流程.pdf