舉例講解C語言程序中對二叉樹數據結構的各種遍歷方式

2020-01-26 14:39:37

字體：大中小

來源：轉載

供稿：網友

二叉樹遍歷的基本思想

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

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)