二叉树遍历的递归算法
递归问题总会成为我们的难点,代码量少,思维量确是很大,难是在所难免的,所以,在思维理解的同时结合实现代码理解,这样就很有可能让我们打开思路,理解的更深,本次实践将在二叉树算法的基础上进行遍历二叉树递归运算实现,旨在结合实现代码,能够更好的理解,同时可以实际应用。(编译环境:VC++6.0)
本次运用到的二叉树算法库点击此处参考。
注:在main函数中,创建的用于测试的二叉树如下——
实现源代码如下:
//*Copyright (c)2017,烟台大学计算机与控制工程学院* //*All rights reservrd.* //*文件名称 :main.cpp* //*作者:田长航* //*完成时间:2017年10月26日* //*版本号:v1.0* //*问题描述:测试函数* //*输入描述:无* //*程序输出:无* #include <stdio.h> #include "btree.h" void PreOrder(BTNode *b) //先序遍历的递归算法 { if (b!=NULL) { printf("%c ",b->data); //访问根节点 PreOrder(b->lchild); //递归访问左子树 PreOrder(b->rchild); //递归访问右子树 } } void InOrder(BTNode *b) //中序遍历的递归算法 { if (b!=NULL) { InOrder(b->lchild); //递归访问左子树 printf("%c ",b->data); //访问根节点 InOrder(b->rchild); //递归访问右子树 } } void PostOrder(BTNode *b) //后序遍历的递归算法 { if (b!=NULL) { PostOrder(b->lchild); //递归访问左子树 PostOrder(b->rchild); //递归访问右子树 printf("%c ",b->data); //访问根节点 } } int main() { BTNode *b; CreateBTNode(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"); printf("二叉树b:"); DispBTNode(b); printf("\n"); printf("先序遍历序列:\n"); PreOrder(b); printf("\n"); printf("中序遍历序列:\n"); InOrder(b); printf("\n"); printf("后序遍历序列:\n"); PostOrder(b); printf("\n"); DestroyBTNode(b); return 0; }
测试结果截图如下: