快捷導(dǎo)航

舉例講解C語言程序中對(duì)二叉樹數(shù)據(jù)結(jié)構(gòu)的各種遍歷方式

更新時(shí)間：2016年04月09日 15:28:29 作者：cqnuztq

這篇文章主要介紹了舉例講解C語言程序中對(duì)二叉樹數(shù)據(jù)結(jié)構(gòu)的各種遍歷方式,先序中序后序二叉樹遍歷幾乎成了最老生常談的數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí),的朋友可以參考下

二叉樹遍歷的基本思想

二叉樹的遍歷本質(zhì)上其實(shí)就是入棧出棧的問題，遞歸算法簡單且容易理解，但是效率始終是個(gè)問題。非遞歸算法可以清楚的知道每步實(shí)現(xiàn)的細(xì)節(jié)，但是乍一看不想遞歸算法那么好理解，各有各的好處吧。接下來根據(jù)下圖講講樹的遍歷。

201649152648498.jpg (456×317)

1、先序遍歷：先序遍歷是先輸出根節(jié)點(diǎn)，再輸出左子樹，最后輸出右子樹。上圖的先序遍歷結(jié)果就是：ABCDEF

2、中序遍歷：中序遍歷是先輸出左子樹，再輸出根節(jié)點(diǎn)，最后輸出右子樹。上圖的中序遍歷結(jié)果就是：CBDAEF

3、后序遍歷：后序遍歷是先輸出左子樹，再輸出右子樹，最后輸出根節(jié)點(diǎn)。上圖的后序遍歷結(jié)果就是：CDBFEA

其中，后序遍歷的非遞歸算法是最復(fù)雜的，我用了一個(gè)標(biāo)識(shí)符isOut來表明是否需要彈出打印。因?yàn)橹挥挟?dāng)節(jié)點(diǎn)的左右子樹都打印后該節(jié)點(diǎn) 才能彈出棧打印，所以標(biāo)識(shí)isOut為1時(shí)打印，isOut初始值為0，這主要是為了處理非葉子節(jié)點(diǎn)。由后序遍歷的原理決定，左右子樹都被打印該節(jié)點(diǎn)才能打印，所以該節(jié)點(diǎn)肯定會(huì)被訪問2次，第一次的時(shí)候不要打印，第二次打印完右子樹的時(shí)候打印。葉子節(jié)點(diǎn)打印完后將isOut置為1。（純粹是自己想的，應(yīng)該還有邏輯更簡單的算法）

實(shí)例
構(gòu)造和遍歷

#include <stdio.h> 
#include <stdlib.h> 
 
typedef struct _NODE//節(jié)點(diǎn)結(jié)構(gòu) 
{ 
  struct _NODE* leftChild; 
  int value; 
  struct _NODE* rightChild; 
} NODE, *PNODE; 
 
PNODE createNode(int value){//創(chuàng)建一個(gè)新節(jié)點(diǎn) 
  PNODE n = (PNODE)malloc(sizeof(NODE)); 
  n->value = value; 
  n->leftChild = NULL; 
  n->rightChild = NULL; 
  return n; 
} 
 
PNODE insertLeftChild(PNODE parent, int value){//在指定節(jié)點(diǎn)上插入左節(jié)點(diǎn) 
  return (parent->leftChild = createNode(value)); 
} 
 
PNODE insertRightChild(PNODE parent, int value){//在指定節(jié)點(diǎn)上插入左節(jié)點(diǎn) 
  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){//先序遍歷：對(duì)每一刻子樹都是根->左->右的順序 
  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);//創(chuàng)建根節(jié)點(diǎn) 
  createBTree(root, 3); 
   
  printf("先序遍歷: "); 
  printDLR(root);//遍歷 
  printf("\n中序遍歷: "); 
   
  printLDR(root); 
  printf("\n后序遍歷: "); 
   
  printLRD(root); 
  printf("\n"); 
}

201649152221356.jpg (546×169)

執(zhí)行結(jié)果：

201649152333006.jpg (570×119)

先序遍歷：

201649152351080.jpg (546×169)

中序遍歷：

201649152406969.jpg (546×169)

后序遍歷：

201649152423441.jpg (546×169)

C++中可以使用類模板，從而使節(jié)點(diǎn)值的類型可以不止限定在整型：

#include <iostream.h> 
 
template <class T> class Node//節(jié)點(diǎn)類模板 
{ 
public: 
  Node(T value):value(value)//構(gòu)造方法 
  { 
    leftChild = 0;  
    rightChild = 0; 
  } 
  Node* insertLeftChild(T value);//插入左孩子,返回新節(jié)點(diǎn)指針 
  Node* insertRightChild(T vallue);//插入右孩子 
  void deleteLeftChild();//刪左孩子 
  void deleteRightChild();//刪右孩子 
  void showDLR();//先序遍歷 
  void showLDR();//中序遍歷 
  void showLRD();//后序遍歷 
protected: 
  T value;//節(jié)點(diǎn)值 
  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){//構(gòu)建一個(gè)二叉樹 
  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){//顯示各種遍歷方式結(jié)果 
  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<<"浮點(diǎn)型:"<<endl; 
  showTest(root3); 
}

201649152439055.jpg (578×259)