文档章节

数据结构(算法)-树

ashuo
 ashuo
发布于 10/22 15:31
字数 355
阅读 9
收藏 0
#include <iostream>
#include <malloc.h>

using namespace std;


#define MaxSize 100
typedef char ElemType;

typedef struct node{
	ElemType data;
	struct node *left ,*right;
} BTree;

//先序
void preorder(BTree * bt){
	if(bt != NULL){
		printf("%c",bt->data);
		preorder(bt->left);
		preorder(bt->right);

	}
}

//中序
void inoder(BTree * bt){
	if(bt != NULL){
		inoder(bt->left);
		printf("%c",bt->data);
		inoder(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){
	BTree * stack[MaxSize] ,*p;
	int top=-1 , k, j=0;

	char ch;
	*bt =NULL;
	ch=str[j];
	while(ch !='\0'){
		switch(ch){
			case '(' :
				top++;
				stack[top]=p;
				k=1;
				break;
			case ')' :
				top--;
				break;
			case ',' :
				k=2;
				break;
			default:
				p=(BTree *)malloc(sizeof(BTree));
				p->data=ch;
				p->left=p->right=NULL;
				if(*bt ==NULL){
					*bt =p;
				}else{
					switch(k){
						case 1:
							stack[top]->left=p;
							break;
						case 2:
							stack[top]->right=p;
							break;
					}
				}
		}
		j++;
		ch=str[j];
	}
} 

//树的高度
int BTreeDepth(BTree * bt){
	int leftdep ,rightdep;
	if(bt ==NULL){
		return 0;
	}else {
		leftdep=BTreeDepth(bt->left);
		rightdep=BTreeDepth(bt->right);
		if(leftdep > rightdep){
			return leftdep +1;
		}else {
			return rightdep +1;
		}
	}
}

//树的叶子结点

int leafCout(BTree * bt){
	if(bt == NULL){
		return 0;
	}else if (bt ->left == NULL && bt ->right ==NULL){
		return 1;
	}else{
		return leafCout(bt->left) + leafCout(bt ->right) +1 ;
	}
}

void main(){
	BTree *b;
	char *s ="A(B(D,E(H,I)),C(G))";
	createTree(&b,s);
	printf("\n 先序遍历:");
	preorder(b);

	printf("\n 中序遍历:");
	inoder(b);
	
	printf("\n 后序遍历:");
	postorder(b);

	printf("\n树的高度:%d\n",BTreeDepth(b));

	printf("树的叶子结点:%d\n",leafCout(b));
	
}



 

测试结果


先序遍历:ABDEHICG
中序遍历:DBHEIAGC
后序遍历:DHIEBGCA
树的高度:4
树的叶子结点:8

 

© 著作权归作者所有

共有 人打赏支持
ashuo
粉丝 4
博文 62
码字总数 40987
作品 0
浦东
程序员
私信 提问
目录帖:​​​​​​​浅谈算法和数据结构

浅谈算法和数据结构: 一 栈和队列 浅谈算法和数据结构: 二 基本排序算法 浅谈算法和数据结构: 三 合并排序 浅谈算法和数据结构: 四 快速排序 浅谈算法和数据结构: 五 优先级队列与堆排序 浅谈...

安小乐
09/04
0
0
转行程序员?你可能忽略了一件事。

     程序 = 数据结构 + 算法   ——图灵奖得主,计算机科学家N.Wirth(沃斯)      作为程序员,我们做机器学习也好,做python开发也好,java开发也好。   有一种对所有程序员无一...

java进阶架构师
10/25
0
0
二叉树,排序二叉树

说到二叉树,这可是数据结构里面的非常重要的一种数据结构,二叉树是树的一种,本身具有递归性质,所以基于二叉树的一些算法很容易用递归算法去实现。作为一种非线性结构,比起线性结构还是相...

长平狐
2013/12/25
129
0
前端你应该了解的数据结构与算法

提到数据结构与算法都感觉这应该是后端要掌握的知识,对前端来说只要写写页面,绑定事件,向后台发发数据就好了,用不到数据结构与算法,也许对于一些数据查找 简单的for循环就能搞定,也许只...

幸福拾荒者
06/29
0
0
如何理解并掌握 Java 数据结构

一说起“数据结构”可能很多同学都又交给老师了。但是实际工作中如果做得深入一些,特别是越往上发展,越大公司越离不开数据结构。本场 Chat 作者将带领大家重温《Java 数据结构》,讲解的内...

valada
04/12
0
0

没有更多内容

加载失败,请刷新页面

加载更多

day150-2018-11-17-英语流利阅读-待学习

歪果仁也疯狂:海外版抖音的征途 毛西 2018-11-17 1.今日导读 海外版抖音 TikTok 于 2017 年 5 月上线海外,至今覆盖全球 150 多个国家和地区,月活跃用户数已突破 5 亿。然而,“出海”的抖...

飞鱼说编程
今天
10
0
分布式学习最佳实践:从分布式系统的特征开始(附思维导图)

什么是分布式系统 回到顶部   分布式系统是由一组通过网络进行通信、为了完成共同的任务而协调工作的计算机节点组成的系统。分布式系统的出现是为了用廉价的、普通的机器完成单个计算机无法...

dragon_tech
今天
4
0
TOKEN设计

TOKEN设计 Api_Token 首先需要知道API是什么? API(Application Programming Interface)即应用程序接口。你可以认为 API 是一个软件组件或是一个 Web 服务与外界进行的交互的接口。而我们在...

DrChenXX
今天
3
0
浅谈“李氏代换”——从纪念金庸和斯坦李说起

李氏代换(LSP)简介 李氏代换是软件设计的一个原则,又名依赖倒转原则或依赖倒置原则,其衍生原则有接口分离原则等。该原则由Barbara Liskov于1988年提出。 该原则指出,程序中高级别的元素...

SamYjy
今天
37
0
JavaScript实现在线websocket WSS测试工具 -toolfk程序员工具网

本文要推荐的[ToolFk]是一款程序员经常使用的线上免费测试工具箱,ToolFk 特色是专注于程序员日常的开发工具,不用安装任何软件,只要把内容贴上按一个执行按钮,就能获取到想要的内容结果。T...

toolfk
今天
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部