定义二叉树存储结构的代码 编写二叉树深度的递归算法
- tfy.com.cnzb
- 2024-04-21
- 测评资讯
- 6浏览
- 0评论
一、以二叉链表为存储结构,写出求二叉树高度和宽度的算法
树的高度:对非空二叉树,其深度等于左子树的大深度加1。
Int Depth(BinTree*T){int dep1,dep2;
if(T==Null) return(0);
else{dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);}
树的宽度:按层遍历二叉树,采用一个队列q,让根结点入队列,后出队列,若有左右子树,则左右子树根结点入队列,如此反复,直到队列为空。
int Width(BinTree*T){intfront=-1,rear=-1;
/*队列初始化*/int flag=0,count=0,p;
/* pint CountNode(BTNode*t)
//节点总数{int num;if(t== NULL)num= 0;
elsenum= 1+ CountNode(t->lch)+ CountNode(t->rch);
return(num);}void CountLeaf(BTNode*t)
//叶子节点总数{if(t!= NULL){if(t->lch== NULL&& t->rch== NULL)count++;
//全局变量CountLeaf(t->lch);CountLeaf(t->rch);}}。
扩展资料
方法:
求二叉树的高度的算法基于对二叉树的三种遍历,可以用后序遍历的算法加上记录现在的高度和已知的高的叶子的高度,当找到一个比已知高度还要高的叶子,刷新高高度。
后遍历下来就是树的高度,至于后序遍历的算法,是一本数据结构或者算法的书中都有介绍和参考代码
二、请问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(Node));//创建一个节点
node->data= value;
node->left= NULL;
node->right= NULL;
if(tree->root== NULL)//判断树是不是空树
{
tree->root= node;
}
else
{//不是空树
Node* temp= tree->root;//从树根开始
while(temp!= NULL)
{
if(value< temp->data)//小于就进左儿子
{
if(temp->left== NULL)
{
temp->left= node;
return;
}
else
{//继续判断
temp= temp->left;
}
}
else{//否则进右儿子
if(temp->right== NULL)
{
temp->right= node;
return;
}
else{//继续判断
temp= temp->right;
}
}
}
}
return;
}
void inorder(Node* node)//树的中序遍历
{
if(node!= NULL)
{
inorder(node->left);
printf("%d",node->data);
inorder(node->right);
}
}
int main()
{
Tree tree;
tree.root= NULL;//创建一个空树
int n;
scanf("%d",&n);
for(int i= 0; i< n; i++)//输入n个数并创建这个树
{
int temp;
scanf("%d",&temp);
insert(&tree, temp);
}
inorder(tree.root);//中序遍历
getchar();
getchar();
return 0;
}
扩展资料:
简单二叉树定义范例:此树的顺序结构为:ABCDE
#include<cstdlib>
#include<stdio.h>
#include<string>
int main()
{
node* p= newnode;
node* p= head;
head= p;
string str;
cin>> str;
creat(p, str, 0)//默认根结点在str下标0的位置
return 0;
}
//p为树的根结点(已开辟动态内存),str为二叉树的顺序存储数组ABCD##E或其他顺序存储数组,r当前结点所在顺序存储数组位置
void creat(node* p, string str, int r)
{
p->data= str[r];
if(str[r* 2+ 1]=='#'|| r* 2+ 1> str.size()- 1)p->lch= NULL;
else
{
p->lch= newnode;
creat(p->lch, str, r* 2+ 1);
}
if(str[r* 2+ 2]=='#'|| r* 2+ 2> str.size()- 1)p->rch= NULL;
else
{
p->rch= newnode;
creat(p->rch, str, r* 2+ 2);
}
}
三、以二叉链表作存储结构***编写二叉树深度的递归算法***c******语言***
给你一个完整的例子吧。学习一下#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define OVERFLOW-2
#define MAX(a,b)(a>b?a:b)typedef char TElemType;
typedef int Status;//二叉树的二叉链表存储结构
typedef struct BiTNode{
TElemType data;
struct BiTNode*lchild,*rchild;
}BiTNode,*BiTree;//先序遍历生成二叉树
Status CreatBiTree(BiTree&T){
TElemType ch,temp;
printf("输入一个元素:");
scanf("%c",&ch);
temp=getchar();//结束回车
if(ch=='') T=NULL;//输入空格表示结点为空树
else{
if(!(T=(BiTree)malloc(sizeof(BiTNode)))) exit(OVERFLOW);
T->data=ch;//生成根结点
CreatBiTree(T->lchild);//构造左子树
CreatBiTree(T->rchild);//构造右子树
}
return OK;
}//打印元素
Status PrintElem(TElemType e){
printf("%c",e);
return OK;
}//先序遍历二叉树
Status PreOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
if(T){//二叉树不为空时
if(Visit(T->data))//访问根结点
if(PreOrderTraverse(T->lchild,Visit))//先序遍历左子树
if(PreOrderTraverse(T->rchild,Visit)) return OK;//先序遍历右子树
return ERROR;
}
else return OK;
}//中序遍历二叉树
Status InOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
if(T){
if(InOrderTraverse(T->lchild,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->rchild,Visit)) return OK;
else return ERROR;
}
return OK;
}//后序遍历二叉树
Status PostOrderTraverse(BiTree T,Status(* Visit)(TElemType e)){
if(T){
if(PostOrderTraverse(T->lchild,Visit))
if(PostOrderTraverse(T->rchild,Visit))
if(Visit(T->data)) return OK;
else return ERROR;
}
return OK;
}//求二叉树的深度
int BiTreeDepth(BiTree T){
if(!T) return 0;//二叉树为空树时
int Dl=0,Dr=0;
if(T->lchild) Dl=BiTreeDepth(T->lchild);//求左子树深度
if(T->rchild) Dr=BiTreeDepth(T->rchild);//求右子树深度
return MAX(Dl,Dr)+1;
}//主函数
void main()
{
BiTree T;
Status(* Visit)(TElemType);
Visit=PrintElem;
CreatBiTree(T);
printf("\n先序遍历:");
PreOrderTraverse(T,Visit);
printf("\n中序遍历:");
InOrderTraverse(T,Visit);
printf("\n后序遍历:");
PostOrderTraverse(T,Visit);
printf("\n二叉树深度为%d",BiTreeDepth(T));
printf("\n程序结束.\n");
}
本站文章除注明转载/出处外,均为本站原创或翻译。若要转载请务必注明出处,尊重他人劳动成果共创和谐网络环境。
转载请注明 : 文章转载自 » 大智测评网 » 测评资讯 » 定义二叉树存储结构的代码 编写二叉树深度的递归算法