举例讲解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);
}

(0)

相关推荐

  • C语言二叉排序(搜索)树实例

    本文实例为大家分享了C语言二叉排序(搜索)树实例代码,供大家参考,具体内容如下 /**1.实现了递归 非递归插入(创建)二叉排序(搜索)树: 分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k); 2.实现了递归 非递归查找 二叉排序(搜索)树 : 分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNod

  • C语言实现二叉树遍历的迭代算法

    本文实例讲述了C语言实现二叉树遍历的迭代算法,是数据结构算法中非常经典的一类算法.分享给大家供大家参考. 具体实现方法如下: 二叉树中序遍历的迭代算法: #include <iostream> #include <stack> using namespace std; struct Node { Node(int i, Node* l = NULL, Node* r = NULL) : item(i), left(l), right(r) {} int item; Node* le

  • C语言二叉树的非递归遍历实例分析

    本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

  • C语言中计算二叉树的宽度的两种方式

    C语言中计算二叉树的宽度的两种方式 二叉树作为一种很特殊的数据结构,功能上有很大的作用!今天就来看看怎么计算一个二叉树的最大的宽度吧. 采用递归方式 下面是代码内容: int GetMaxWidth(BinaryTree pointer){ int width[10];//加入这棵树的最大高度不超过10 int maxWidth=0; int floor=1; if(pointer){ if(floor==1){//如果访问的是根节点的话,第一层节点++; width[floor]++; flo

  • c语言版本二叉树基本操作示例(先序 递归 非递归)

    复制代码 代码如下: 请按先序遍历输入二叉树元素(每个结点一个字符,空结点为'='):ABD==E==CF==G== 先序递归遍历:A B D E C F G中序递归遍历:D B E A F C G后序递归遍历:D E B F G C A层序递归遍历:ABCDEFG先序非递归遍历:A B D E C F G中序非递归遍历:D B E A F C G后序非递归遍历:D E B F G C A深度:请按任意键继续. . . 复制代码 代码如下: #include<stdio.h>#include&

  • 使用C语言求二叉树结点的最低公共祖先的方法

    算法分析 我们直接来分析O(n)的算法. 比如求节点F和节点H的最低公共祖先,先求出从根节点A到F的路径,再求出A到H的路径,那么最后一个相同的节点就是最低公共祖先.A->B->D->F和A->B->E->H,最后相同的节点事B,所以最低公共祖先是B节点.求根节点到指定节点的算法先前已经更新过了,复杂度是O(n),所以总的时间复杂度是O(n). 条件细化: (1)树如果是二叉树,而且是二叉排序树.              这中条件下可以使用二叉排序树的搜索功能找到最低

  • C语言 二叉树的链式存储实例

    二叉树的链式存储 实现二叉树的基本操作:建立.遍历.计算深度.结点数.叶子数等. 输入C,先序创建二叉树,#表示空节点: 输入H:计算二叉树的高度: 输入L:计算二叉树的叶子个数: 输入N:计算二叉树节点总个数: 输入1:先序遍历二叉树: 输入2:中序遍历二叉树: 输入3:后续遍历二叉树: 输入F:查找值=x的节点的个数: 输入P:以缩格文本形式输出所有节点. 很简单就不需要多解释了,代码贴上 #include <stdio.h> #include <stdlib.h> #incl

  • 用C语言判断一个二叉树是否为另一个的子结构

    1.问题描述: 如何判断一个二叉树是否是另一个的子结构?      比如: 2       /   \      9    8     / \    /    2  3  5   / 6 有个子结构是    9   / \ 2  3 2.分析问题:     有关二叉树的算法问题,一般都可以通过递归来解决.那么写成一个正确的递归程序,首先一定要分析正确递归结束的条件. 拿这道题来讲,什么时候递归结束. <1>第二个二叉树root2为空时,说明root2是第一棵二叉树的root1的子结构,返回tr

  • 使用C语言构建基本的二叉树数据结构

    二叉树结构常用的一些初始化代码 #include #include typedef struct Node{ int data; Node *leftchild; Node *rightchild; }Node; /* 初始化一棵二叉树排序树. */ void InitBinaryTree(Node**root,int elem) { *root=(Node*)malloc(sizeof(Node)); if(!(*root)) { printf("Memory allocation for r

  • C语言实现找出二叉树中某个值的所有路径的方法

    本文实例讲述了C语言实现找出二叉树中某个值的所有路径的方法,是非常常用的一个实用算法技巧.分享给大家供大家参考. 具体实现方法如下: #include <iostream> #include <vector> #include <iterator> #include <algorithm> using namespace std; vector<int> result; struct Node { Node(int i = 0, Node *pl

随机推荐