举例讲解C语言程序中对二叉树数据结构的各种遍历方式
二叉树遍历的基本思想
二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧。接下来根据下图讲讲树的遍历。
1、先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树。上图的先序遍历结果就是:ABCDEF
2、中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树。上图的中序遍历结果就是:CBDAEF
3、后序遍历:后序遍历是先输出左子树,再输出右子树,最后输出根节点。上图的后序遍历结果就是:CDBFEA
其中,后序遍历的非递归算法是最复杂的,我用了一个标识符isOut来表明是否需要弹出打印。因为只有当节点的左右子树都打印后该节点 才能弹出栈打印,所以标识isOut为1时打印,isOut初始值为0,这主要是为了处理非叶子节点。由后序遍历的原理决定,左右子树都被打印该节点才能打印,所以该节点肯定会被访问2次,第一次的时候不要打印,第二次打印完右子树的时候打印。叶子节点打印完后将isOut置为1。(纯粹是自己想的,应该还有逻辑更简单的算法)
实例
构造和遍历
#include <stdio.h> #include <stdlib.h> typedef struct _NODE//节点结构 { struct _NODE* leftChild; int value; struct _NODE* rightChild; } NODE, *PNODE; PNODE createNode(int value){//创建一个新节点 PNODE n = (PNODE)malloc(sizeof(NODE)); n->value = value; n->leftChild = NULL; n->rightChild = NULL; return n; } PNODE insertLeftChild(PNODE parent, int value){//在指定节点上插入左节点 return (parent->leftChild = createNode(value)); } PNODE insertRightChild(PNODE parent, int value){//在指定节点上插入左节点 return (parent->rightChild = createNode(value)); } void createBTree(PNODE root, int i){//向树中插入一些元素 if (i == 0) { return; } else{ PNODE l = insertLeftChild(root, i * 10 + 1); PNODE r = insertRightChild(root, i * 10 + 2); createBTree(l, --i); createBTree(r, i); } } void printDLR(PNODE root){//先序遍历:对每一刻子树都是根->左->右的顺序 if (root == NULL) { return; } printf("%-4d", root->value); printDLR(root->leftChild); printDLR(root->rightChild); } void printLDR(PNODE root){//中序遍历: if (root == NULL) { return; } printLDR(root->leftChild); printf("%-4d", root->value); printLDR(root->rightChild); } void printLRD(PNODE root){//后序遍历 if (root == NULL) { return; } printLRD(root->leftChild); printLRD(root->rightChild); printf("%-4d", root->value); } void main(){ PNODE root = createNode(0);//创建根节点 createBTree(root, 3); printf("先序遍历: "); printDLR(root);//遍历 printf("\n中序遍历: "); printLDR(root); printf("\n后序遍历: "); printLRD(root); printf("\n"); }
执行结果:
先序遍历:
中序遍历:
后序遍历:
C++中可以使用类模板,从而使节点值的类型可以不止限定在整型:
#include <iostream.h> template <class T> class Node//节点类模板 { public: Node(T value):value(value)//构造方法 { leftChild = 0; rightChild = 0; } Node* insertLeftChild(T value);//插入左孩子,返回新节点指针 Node* insertRightChild(T vallue);//插入右孩子 void deleteLeftChild();//删左孩子 void deleteRightChild();//删右孩子 void showDLR();//先序遍历 void showLDR();//中序遍历 void showLRD();//后序遍历 protected: T value;//节点值 Node* leftChild;//左孩子指针 Node* rightChild;//右孩子指针 private: }; template <class T> Node<T>* Node<T>::insertLeftChild(T value){//插入左孩子 return (this->leftChild = new Node(value)); } template <class T> Node<T>* Node<T>::insertRightChild(T value){//插入右孩子 return (this->rightChild = new Node(value)); } template <class T> void Node<T>::deleteLeftChild(){//删除左孩子 delete this->leftChild; this->leftChild = 0; } template <class T> void Node<T>::deleteRightChild(){//删除右孩子 delete this->rightChild; this->rightChild = 0; } template <class T> void Node<T>::showDLR(){//先序遍历 cout<<this->value<<" "; if (leftChild) { leftChild->showDLR(); } if (rightChild) { rightChild->showDLR(); } } template <class T> void Node<T>::showLDR(){//中序遍历 if (leftChild) { leftChild->showLDR(); } cout<<this->value<<" "; if (rightChild) { rightChild->showLDR(); } } template <class T> void Node<T>::showLRD(){//后序遍历 if (leftChild) { leftChild->showLRD(); } if (rightChild) { rightChild->showLRD(); } cout<<this->value<<" "; } template <class T> void createSomeNodes(Node<T>* root, int i, T base){//构建一个二叉树 if (i == 0) { return; } Node<T>* l = root->insertLeftChild(i + base); Node<T>* r = root->insertRightChild(i + base); createSomeNodes(l, --i, base); createSomeNodes(r, i, base); } template <class T> void showTest(Node<T>* root){//显示各种遍历方式结果 cout<<"先序遍历: "; root->showDLR(); cout<<endl<<"中序遍历: "; root->showLDR(); cout<<endl<<"后序遍历: "; root->showLRD(); cout<<endl; } void main(){ Node<int> *root1 = new Node<int>(0); createSomeNodes(root1, 3, 0); cout<<"整型:"<<endl; showTest(root1); Node<char> *root2 = new Node<char>('a'); createSomeNodes(root2, 3, 'a'); cout<<"字符型:"<<endl; showTest(root2); Node<float> *root3 = new Node<float>(0.1f); createSomeNodes(root3, 3, 0.1f); cout<<"浮点型:"<<endl; showTest(root3); }
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- 下面小编就为大家带来一篇js遍历json的key和value的实例。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2017-01-26
JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍
下面小编就为大家带来一篇JavaScript中的数组遍历forEach()与map()方法以及兼容写法介绍。小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-05-20- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结
借助jQuery我们可以轻松地堆DOM元素进行向上、向下遍历以及同级的遍历,本文我们即来整理jQuery遍历DOM的父级元素、子级元素和同级元素的方法总结:...2016-07-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 这篇文章主要介绍了c# 遍历 Dictionary的四种方式,帮助大家更好的理解和使用c#,感兴趣的朋友可以了解下...2020-12-08
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 下面就为大家带来一篇jquery对Json的各种遍历方法总结(必看篇)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2016-10-02
- 这篇文章主要介绍了C# 遍历datatable字段名和value的案例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2021-01-19
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 这篇文章主要为大家详细介绍了JS中的二叉树遍历,何为二叉树,什么是二叉树的遍历,感兴趣的小伙伴们可以参考一下...2016-03-22
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要给大家介绍了关于JavaScript循环遍历的24个方法,文中对每种方法都给出了详细的实例代码,方便大家理解学习,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下...2021-09-15