这篇文章给大家分享的是有关C++如何实现树的遍历功能的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。
10年积累的成都网站建设、网站设计经验,可以快速应对客户对网站的新想法和需求。提供各种问题对应的解决方案。让选择我们的客户得到更好、更有力的网络服务。我虽然不认识你,你也不认识我。但先网站制作后付款的网站建设流程,更有梅县免费网站建设让你可以放心的选择与我们合作。
具体如下:
递归是把问题转化为规模缩小的同类问题,然后迭代调用函数(或过程)求得问题的解。递归函数就是直接或间接调用自身的函数。
递归两要素:递归关系和递归边界(终止条件),递归关系确定了迭代的层次结构,需要深入了解并分解问题;终止条件保证了程序的有穷性。
递归的应用有很多,常见的包括:阶乘运算、斐波那契数列、汉诺塔、数的遍历,还有大名鼎鼎的快排等等。理论上,递归问题都可以由多层循环来实现。递归的每次调用都会消耗一定的栈空间,效率要稍低于循环实现,但递归使函数更加简洁,极大地增加了程序的可读性。这里介绍汉诺塔和树的遍历两种应用。
汉诺塔(hanoi)
有三根相邻的柱子,标号为A,B,C,A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘,要把所有盘子一个一个移动到柱子C上,并且每次移动同一根柱子上都不能出现大盘子在小盘子上方。
递归规则:先把a上的n-1个搬到b上,再把a上第n个搬到c,然后把b上的n-1个搬到c上;终止条件是n=0。
/* *说明:目标:把n个盘子从a往c搬 */ void hanoi(int n, char a,char b,char c) { if(n>0) { hanoi(n-1,a,c,b); cout<"<这样程序便十分简洁的实现了看似复杂的功能,下面再看一个经典的问题:
遍历二叉树
二叉树的遍历是指从根节点出发,按照某种次序依次访问二叉树中的所有结点,使得每个结点被访问一次且仅被访问一次。遍历方法有四种:前序遍历(先访问根节点,然后前序遍历左子树,最后前序遍历右子树)、中序遍历(左子树->根节点->右子树)、后序遍历(左子树->右子树->根节点)和层序遍历(每一层自左向右,各层自上向下访问)。
可见前三种遍历方法的定义就体现了递归的思想,算法实现如下:
//前序遍历 void PreorderTra(BiTree T) { if(T == NULL) { return; } printf("%c",T->data);//输出结点数据,可更改为其他对结点的操作 PreorderTra(T->lchild);//前序遍历左子树 PreorderTra(T->rchild);//前序遍历右子树 } //中序遍历 void InorderTra(BiTree T) { if(T == NULL) { return; } InorderTra(T->lchild);//中序遍历左子树 printf("%c",T->data);//输出结点数据,可更改为其他对结点的操作 InorderTra(T->rchild);//中序遍历右子树 } //后序遍历 void PostorderTra(BiTree T) { if(T == NULL) { return; } PostorderTra(T->lchild);//后序遍历左子树 PostorderTra(T->rchild);//后序遍历右子树 printf("%c",T->data);//输出结点数据,可更改为其他对结点的操作 }其中二叉树的结构如下:
typedef struct BiTNode { ElemType data; struct BiTNode *lchild,*rchild; }BitNode,*BiTree;感谢各位的阅读!关于“C++如何实现树的遍历功能”这篇文章就分享到这里了,希望以上内容可以对大家有一定的帮助,让大家可以学到更多知识,如果觉得文章不错,可以把它分享出去让更多的人看到吧!
网页题目:C++如何实现树的遍历功能
标题来源:http://cdkjz.cn/article/jedppo.html