C語言中怎么實(shí)現(xiàn)中序二叉樹

C語言中怎么實(shí)現(xiàn)中序二叉樹，針對(duì)這個(gè)問題，這篇文章詳細(xì)介紹了相對(duì)應(yīng)的分析和解答，希望可以幫助更多想解決這個(gè)問題的小伙伴找到更簡單易行的方法。

C語言數(shù)據(jù)結(jié)構(gòu) 中序二叉樹

前言：

線索二叉樹主要是為了解決查找結(jié)點(diǎn)的線性前驅(qū)與后繼不方便的難題。它只增加了兩個(gè)標(biāo)志性域，就可以充分利用沒有左或右孩子的結(jié)點(diǎn)的左右孩子的存儲(chǔ)空間來存放該結(jié)點(diǎn)的線性前驅(qū)結(jié)點(diǎn)與線性后繼結(jié)點(diǎn)。兩個(gè)標(biāo)志性域所占用的空間是極少的，所有充分利用了二叉鏈表中空閑存的儲(chǔ)空間。

   要實(shí)現(xiàn)線索二叉樹，就必須定義二叉鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下（定義請(qǐng)看代碼）：

說明：

1.       leftTag=false時(shí)，表示left指向該結(jié)點(diǎn)的左孩子；

2.       leftTag=true時(shí)，表示left指向該結(jié)點(diǎn)的線性前驅(qū)結(jié)點(diǎn)；

3.       rightTag=false時(shí)，表示right指向該結(jié)點(diǎn)的右孩子；

4.       rightTag=true時(shí)，表示right指向該結(jié)點(diǎn)的線性后繼結(jié)點(diǎn)；

     以二叉鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)所構(gòu)成的二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做線索二叉鏈表；指向結(jié)點(diǎn)的線性前驅(qū)或者線性后繼結(jié)點(diǎn)的指針叫做線索；加上線索的二叉樹稱為線索二叉樹；對(duì)二叉樹以某種次序遍歷將其變?yōu)榫€索二叉樹的過程叫做線索化。

中序次序線索化二叉樹算法：

  中序次序線索化是指用二叉鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)建立二叉樹的二叉鏈表，然后按照中序遍歷的方法訪問結(jié)點(diǎn)時(shí)建立線索；(具體看代碼)

檢索中序二叉樹某結(jié)點(diǎn)的線性前驅(qū)結(jié)點(diǎn)的算法：

1.       如果該結(jié)點(diǎn)的leftTag=true,那么left就是它的線性前驅(qū)；

2.       如果該結(jié)點(diǎn)的leftTag=false，那么該結(jié)點(diǎn)左子樹最右邊的尾結(jié)點(diǎn)就是它的線性前驅(qū)點(diǎn)；

（具體請(qǐng)看代碼）

檢索中序二叉樹某結(jié)點(diǎn)的線性后繼結(jié)點(diǎn)和算法：

1.       如果該結(jié)點(diǎn)的right=true,那么right就是它的線性后繼結(jié)點(diǎn)；

2.       如果該結(jié)點(diǎn)的right=false,那么該結(jié)點(diǎn)右子樹最左邊的尾結(jié)點(diǎn)就是它的線性后繼結(jié)點(diǎn)

（具體請(qǐng)看代碼）

圖：后繼線索

圖：前驅(qū)線索

 節(jié)點(diǎn)定義：

struct Node 
{ 
  int data; 
  bool leftTag; 
  bool rightTag; 
  Node* left; 
  Node* right; 
  Node(int _data):data(_data),left(0),right(0),leftTag(false),rightTag(false){} 
};

類定義：

class BinaryTree 
{ 
private: 
  Node* root; 
private: 
  Node* head; 
  Node* pre; 
  void makeThread(Node* node); 
public: 
  void buildThread(); 
  void traverseBySuccessor(); 
  void traverseByPredecessor(); 
 
// helper methods 
private: 
  static inline bool visit(Node* T) 
  { 
    if (T) 
    { 
      printf("data:%c, left:%c, right:%c\n", 
        (char)T->data, 
        (T->left!=0) ? (char)T->left->data : '#', 
        (T->right!=0) ? (char)T->right->data : '#'); 
      return true; 
    } 
    else return false; 
  } 
};

方法定義：

void BinaryTree::makeThread(Node* node) 
{ 
  if (node!=NULL) 
  { 
    makeThread(node->left); 
    if (pre!= NULL) 
    { 
      if (pre->right==NULL) // 如果前驅(qū)節(jié)點(diǎn)的右子樹為空, 那么把前驅(qū)節(jié)點(diǎn)的右子樹用作線索 
      { 
        pre->rightTag = true;  
        pre->right = node; 
      } 
      else pre->rightTag = false; 
    } 
    if (node->left==NULL) // 如果當(dāng)前結(jié)點(diǎn)的左子樹為空, 那么把當(dāng)前結(jié)點(diǎn)的左子樹用作線索 
    { 
      node->leftTag = true; 
      node->left = pre; 
    } 
    else node->leftTag = false; 
    pre = node; 
    makeThread(node->right); 
  } 
} 
 
void BinaryTree::traverseBySuccessor() 
{ 
  Node* p = head->left; //first find the root node 
  // 親測表明 如果不使用head啞節(jié)點(diǎn) 就要設(shè)三道卡, 防止p訪問到NULL,  
  // 分別在主while處, 第二個(gè)visit處和下面的p=p->right處 
  while (p!=head) 
  { 
    while (!p->leftTag) 
      p = p->left; 
    visit(p); 
 
    while (p->rightTag && p->right!=head) 
    { 
      p = p->right; 
      visit(p); 
    } 
    p = p->right; 
  } 
  cout<<endl; 
} 
 
void BinaryTree::traverseByPredecessor() 
{ 
  Node* p = head->left; //first find the root node 
  while (p!=head) 
  { 
    while (!p->rightTag) 
      p = p->right; 
    visit(p); 
    if (p!=NULL) 
    { 
      while (p->leftTag && p->left!=head) 
      { 
        p = p->left; 
        visit(p); 
      } 
      p = p->left; 
    } 
  } 
  cout<<endl; 
} 
 
void BinaryTree::buildThread() 
{ 
  pre = NULL; 
  head = new Node('@'); 
  head->left = root; 
  head->right = head; 
  makeThread(root); 
  // 經(jīng)過了makeThread過程之后, pre必然指向中序遍歷最晚的結(jié)點(diǎn). 
  // 把pre的右子樹指向head, 就構(gòu)成了一個(gè)雙向循環(huán)鏈表 
  // 
  pre->rightTag = 1; 
  pre->right = head; 
  pre = NULL; 
  Node* p = root; 
  /* 
   * 在建立前驅(qū)線索的時(shí)候，最左邊的結(jié)點(diǎn)沒有和head結(jié)點(diǎn)連接。要在這里補(bǔ)上 
   */ 
  while (p->left!=NULL) 
    p = p->left; 
  p->left = head; 
}

關(guān)于C語言中怎么實(shí)現(xiàn)中序二叉樹問題的解答就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，如果你還有很多疑惑沒有解開，可以關(guān)注億速云行業(yè)資訊頻道了解更多相關(guān)知識(shí)。