C语言程序中对二叉树数据结构的各种遍历方式

  • 更新时间:2021-05-22 08:44:18
  • 编辑:蒋羽莹
为网友们分享了C语言遍历相关的编程文章,网友糜月灵根据主题投稿了本篇教程内容,涉及到C语言、二叉树、数据结构、遍历、C语言二叉树各种遍历相关内容,已被885网友关注,涉猎到的知识点内容可以在下方电子书获得。

参考资料

正文内容

C语言二叉树各种遍历

二叉树遍历的基本思想

二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题。非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧。接下来根据下图讲讲树的遍历。

201649152648498.jpg (456×317)

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"); 
} 

201649152221356.jpg (546×169)

执行结果:

201649152333006.jpg (570×119)

先序遍历:

201649152351080.jpg (546×169)

中序遍历:

201649152406969.jpg (546×169)

后序遍历:

201649152423441.jpg (546×169)

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); 
} 

201649152439055.jpg (578×259)

C语言遍历相关教程

  • Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例

    这篇文章主要介绍了Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作,涉及Python基于先序遍历和中序遍历构造二叉树,再后序遍历输出相关操作技巧,需要的朋友可以参考下

    发布时间:2019-06-03

  • 总结python3实现二叉树的遍历及递归算法

    这篇文章主要介绍了python3实现二叉树的遍历与递归算法解析(小结),文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习

    发布时间:2020-03-13

  • STM8 C语言精品编程100例

    STM8 C语言精品编程100例

    《 STM8 C语言精品编程100例 》教程是关于100例关于STM8单片机的例程,从基础到各个模块的实践再到综合项目的实践,在于给您一个大体的程序编写思路,项目结构安排的大体构架等,可用于项目开发等,代码多且详细,需要的朋友可下载试试! 精准定位于初级学习目的,搭配丰富的代码注解,大幅提高开发技能,可以看得出作者真的很用心.这也让我们学习单片机基础更加的容易理解。 目录 实例1点亮三个发光二极管(LED) 实例2流水(LED)灯向左移动

    大小:9.58 MBC语言

  • 数据结构:用C语言描述

    数据结构:用C语言描述 课后答案

    本书系统地介绍了各种常用的数据结构以及排序、查找的各种算法。阐述了各种数据结构的逻辑关系、存储表示及运算操作,并对C语言描述的算法作了详细的注解和简要的性能分析。全书既注重原理又注重实践,配有大量图表、例题和习题,内容丰富,概念讲解清楚,逻辑性强,可读性好。各章的小结可以使读者抓住本章重点。书中针对不同层次教学的特点和需要用*号标明。每章备有习题。 本书可作为高等院校计算机有关专业本科生、专科生的教材,

    大小:1.21 MB数据结构课后答案

  • C语言从入门到精通

    C语言从入门到精通

    C语言从入门到精通(第3版) 从初学者的角度出发,以通俗易懂的语言,丰富多彩的实例,详细介绍了使用C语言进行程序开发需要掌握的各方面知识。《c语言从入门到精通(第3版)》共分为

    大小:38.9 MBC语言电子书

用户留言