C 语言二叉树几种遍历方法详解及实例
二叉树的一些概念
二叉树就是每个结点最多有两个子树的树形存储结构。先上图,方便后面分析。
1 满二叉树和完全二叉树
上图就是典型的二叉树,其中左边的图还叫做满二叉树,右边是完全二叉树。然后我们可以得出结论,满二叉树一定是完全二叉树,但是反过来就不一定。满二叉树的定义是除了叶子结点,其它结点左右孩子都有,深度为k的满二叉树,结点数就是2的k次方减1。完全二叉树是每个结点都与深度为k的满二叉树中编号从1到n一一对应。
2 树的深度
树的最大层次就是深度,比如上图,深度是4。很容易得出,深度为k的树,拥有的最大结点数是2的k次方减1。
3 树的孩子,兄弟,双亲
上图中,B,C是A的孩子,B,C之间互为兄弟,A是B,C的双亲。
二如何创建二叉树
先说说二叉树的存储结构,跟很多其它模型一样,也有顺序和链式两种方式。前者虽然使用简单,但是存在浪费空间的问题,举个例子,下图的二叉树,用顺序的方式存储(0表示空,没有子树)是:
1 2 3 4 5 6 7 0 0 0 0 8 0 0 0
是不是相当浪费空间呢。
链式结构可以定义如下:
typedef struct _BiTNode { int data; _BiTNode *leftChild; _BiTNode *rightChild; }BiTNode, *pBiTree;
然后就可以写一个函数来创建二叉树,过程是在控制台输入a表示退出当前这一层,不再为该层创建左右孩子。输入其它字母表示继续创建。比如下面的输入序列:
创建了如下结构的二叉树,
每个结点里的数值是随机生成的小于100的数字。同时我也写了一个自动的命令序列函数,方便测试,不用手动输入,非自动和自动创建的函数如下:
//创建二叉树, 先序顺序 int CreateBiTree(pBiTree *root) { char ch = 0; fflush(stdin); if ((ch = getchar()) == 'a')//控制树的结构 { *root = NULL; } else { *root = (BiTNode *)malloc(sizeof(BiTNode)); if (!(*root)) { return RET_ERROR; } (*root)->data = GetRandom(); CreateBiTree(&(*root)->leftChild); CreateBiTree(&(*root)->rightChild); } return RET_OK; } int g_i = 0; //创建二叉树,自动执行,方便测试 int CreateBiTreeAuto(pBiTree *root) { char szOrder[] = "bbaabaa"; char ch = 0; if (szOrder[g_i++] == 'a')//控制树的结构 { *root = NULL; } else { *root = (BiTNode *)malloc(sizeof(BiTNode)); if (!(*root)) { return RET_ERROR; } (*root)->data = GetRandom(); CreateBiTreeAuto(&(*root)->leftChild); CreateBiTreeAuto(&(*root)->rightChild); } return RET_OK; }
三遍历顺序
先序遍历
先序遍历是先访问根结点,再左子树,再右子树,比如图1中的右图,先序遍历的输出如下:
A,B,D,H,I,E,J,K,C,F,G
根据上面的思想,很容易用递归的形式写出先序遍历的代码:
//先序遍历 int PreOrderVisitTree(pBiTree T, VisitType pFuncVisit) { if (T) { (*pFuncVisit)(T->data); if (PreOrderVisitTree(T->leftChild, pFuncVisit) == RET_OK) { if (PreOrderVisitTree(T->rightChild, pFuncVisit) == RET_OK) { return RET_OK; } } return RET_ERROR; } else { return RET_OK; } }
中序遍历和后序遍历
有了先序的经验,这两个就很好理解了,中序是先访问左子树, 再根结点,再右子树, 后序是先访问左子树, 再右子树,再根结点。代码更容易,只要改一下调用顺序就可以了。
不过我这里给出一种非递归的实现。递归固然是清晰明了,但是存在效率低的问题,非递归的方案用栈结构来存结点信息,通过出栈访问来遍历二叉树。它思想是这样的,当栈顶中的指针非空时,遍历左子树,也就是左子树根的指针进栈。当栈顶指针为空时,应退至上一层,如果是从左子树返回的,访问当前层,也就是栈顶中的根指针结点。如果是从右子树返回,说明当前层遍历完毕,继续退栈。代码如下:
//中序遍历, 非递归实现 int InOrderVisitTree(pBiTree T, VisitType pFuncVisit) { ponyStack binaryTreeStack; InitStack(&binaryTreeStack, 4); Push(&binaryTreeStack, &T); pBiTree pTempNode; while (!IsEmptyStack(binaryTreeStack)) { while((GetTop(binaryTreeStack, &pTempNode) == RET_OK) && (pTempNode != NULL)) { Push(&binaryTreeStack, &(pTempNode->leftChild)); } Pop(&binaryTreeStack, &pTempNode); if (!IsEmptyStack(binaryTreeStack)) { Pop(&binaryTreeStack, &pTempNode); (*pFuncVisit)(pTempNode->data); Push(&binaryTreeStack, &(pTempNode->rightChild)); } } return RET_OK; }
代码下载地址:http://xiazai.jb51.net/201701/yuanma/BinaryTreeDemo-master(jb51.net).rar
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关文章
- 这篇文章主要介绍了在C#中使用二叉树实时计算海量用户积分排名的实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2020-06-25
- 这篇文章主要介绍了举例讲解C语言程序中对二叉树数据结构的各种遍历方式,先序中序后序二叉树遍历几乎成了最老生常谈的数据结构基础知识,的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了一波二叉树遍历问题的C++解答实例分享,包括节点打印和转换为镜像等问题的解答,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言数据结构之二叉树的非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法,涉及C++二叉树的定义、遍历、统计相关操作技巧,需要的朋友可以参考下...2020-04-25
- 二叉树是数据结构中的树的一种特殊情况,有关二叉树的相关概念,这里不再赘述,如果不了解二叉树相关概念,建议先学习数据结构中的二叉树的知识点...2020-04-25
- 这篇文章主要介绍了php实现的二叉树遍历算法,结合具体实例形式分析了php针对二叉树的常用前序、中序及后序遍历算法实现技巧,需要的朋友可以参考下...2017-06-20
- 这篇文章主要介绍了如何在Python中创建二叉树,帮助大家更好的理解和学习使用python,感兴趣的朋友可以了解下...2021-03-30
- 这篇文章主要介绍了C语言 二叉查找树性质详解及实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++基于先序、中序遍历结果重建二叉树的方法,结合实例形式分析了基于C++构建二叉树的相关操作技巧,需要的朋友可以参考下...2020-04-25
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
这篇文章主要介绍了C++基于递归和非递归算法判定两个二叉树结构是否完全相同,若判断二叉树的结构和数据都相同则为完全相同.涉及C++二叉树的创建、遍历、比较等相关操作技巧,需要的朋友可以参考下...2020-04-25- 这篇文章主要为大家详细介绍了C++实现二叉树基本操作,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C语言实现二叉树遍历的迭代算法,包括二叉树的中序遍历、先序遍历及后序遍历等,是非常经典的算法,需要的朋友可以参考下...2020-04-25
- 在本篇文章里小编给大家分享了关于c++先序二叉树的构建的相关知识点,需要的朋友们跟着学习下。...2020-04-25
- 这篇文章主要介绍了平衡二叉树的实现实例,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了C++二叉树实现词频分析功能,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2020-04-25
- 这篇文章主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下...2020-04-25
C++实现LeetCode(105.由先序和中序遍历建立二叉树)
这篇文章主要介绍了C++实现LeetCode(105.由先序和中序遍历建立二叉树),本篇文章通过简要的案例,讲解了该项技术的了解与使用,以下就是详细内容,需要的朋友可以参考下...2021-07-23- 这篇文章主要介绍了C语言二叉树的非递归遍历,包括了先序遍历、中序遍历与后序遍历,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C++非递归建立二叉树的方法,实例分析了二叉树的原理与C++实现技巧,具有一定参考借鉴价值,需要的朋友可以参考下...2020-04-25