文档章节

数据结构(算法)-树

ashuo
 ashuo
发布于 2018/10/22 15:31
字数 355
阅读 10
收藏 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
博文 63
码字总数 46928
作品 0
浦东
程序员
私信 提问
目录帖:​​​​​​​浅谈算法和数据结构

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

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

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

java进阶架构师
2018/10/25
0
0
如何理解并掌握 Java 数据结构

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

valada
2018/04/12
0
0
二叉树,排序二叉树

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

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

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

幸福拾荒者
2018/06/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

XML

学习目标  能够说出XML的作用  能够编写XML文档声明  能够编写符合语法的XML  能够通过DTD约束编写XML文档  能够通过Schema约束编写XML文档  能够通过Dom4j解析XML文档 第1章 xm...

stars永恒
14分钟前
0
0
RabbitMQ学习(2)

1. 生产者客户端 void basicPublish(String exchange, String routingKey, boolean mandatory, boolean immediate, BasicProperties props, byte[] body) 1. 在生产者客户端发送消息时,首先......

江左煤郎
14分钟前
1
0
day23:curl判断网站状态码|打包压缩家目录小于5k文件|

1、写一个shell 脚本,通过curl -l 返回的状态码来判断访问的网站是否正确(状态码为 200 则正常); 首先如何过滤出来 状态码了; curl -I http://www.yuanhh.com/index.php 2>/dev/null|head...

芬野de博客
36分钟前
1
0
从 for of 聊到 Generator

你能学到什么 对 for of 更深入的理解 iterator 到底是何方神圣? 数组也是对象,为什么不能用 for of 来遍历对象呢? 如何实现对象的 for of? Generator 又是何方神圣? Generator 有什么用呢...

Jack088
48分钟前
3
0
怎么判断go-sql-driver 安装成功

.下载安装   执行下面两个命令:     下载:go get github.com/Go-SQL-Driver/MySQL     安装:go install github.com/Go-SQL-Driver/MySQL   怎么判断go-sql-driver 安装成功 ...

dragon_tech
56分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部