二叉树遍历在数据结构中用得多,这种算法是从kb时代的内存来的,主要用于理解概念,提升编程时的思想用。
实际用途中
如果用于商业一般用数据库代替,根本用不到二叉树,是用存储代替计算。速度快,可以用内存数据库,如我用h2 database的Memory Mode 在java下可以实现1秒1百万次插入。用sqlite内存模式代替以前在c++需要手工管理的数据结构。数据量大一个电脑存不下时,用hadoop/spark/redis,对分布式大数据支持比较好。
如果用于计算量大的任务或内核结构,可以用矩阵数组,链表,k/v这种比较直观模式存储。
对于树和图这种在内存中复杂的数据结构,尽量不要在生产环境下使用,容易内存泄露,用简单方式代替。对于图结构,可以使用图数据库,如neo4j。对于树结构,可以在数据库中存储一棵树。实际上数据库的存储多用树,如B树、B-树、B+树、B*树。
当然如果你写加密算法,这种要求极高的程序时,还是需要考虑性能最大化的,否则一般用存储代替遍历计算,因为内存和硬盘,现在很便宜了,而cpu还是一种宝贵的资源。
递归和非递归只是解决问题的方法的不同,本质还是一样的。
2. 递归算法相对于非递归算法来说效率通常都会更低
2.1 递归算法会有更多的资源需要压栈和出栈操作(不仅仅是参数,还有函数地址等)
2.2 由于编译器对附加的一些栈保护机制会导致递归执行的更加低效
3. 使用循环代替递归算法,通常可以获得更好的执行效率和空间效率,在二叉树层次较深的情况下,采用非递归方式遍历能够有效的提升遍历的性能。
#define MAXNODE 100 //二叉树最大节点数//定义二叉树链式结构
typedef struct BitNode
{
char data //数据域
struct BitNode *lchild,*rchild//左右指针域
}BitNode,*BiTree
//二叉树进行中序非递归遍历
void NRInorder(BiTree t)
{
BiTree s //s-指向当前节点
BiTree stack[MAXNODE] //定义栈
inttop=-1 //初始化栈顶指针
if(t==NULL)
return
stack[++top]=t//根指针入栈
s=t->lchild //s指向左子树
while(s!=NULL||top!=-1)//当存在节点(涉及到根下右子树)或者栈不为空,进行遍历
{
while(s!=NULL) //如果存在节点,寻找最左子树并入栈
{
if(top>=MAXNODE-1)
{
printf("栈为满\n")
return
}
stack[++top]=s//当前节点入栈
s=s->lchild //左子树进行遍历
}
if(top==-1)
{
printf("栈为空\n")
return
}
s=stack[top--] //弹出栈顶元素到s中
printf("%c ",s->data) //输出当前节点元素值
s=s->rchild //遍历右子树
}
}