Heim > Backend-Entwicklung > C++ > Spiraldurchquerung des Binärbaums gegen den Uhrzeigersinn?

Spiraldurchquerung des Binärbaums gegen den Uhrzeigersinn?

PHPz
Freigeben: 2023-08-30 10:49:10
nach vorne
1279 Leute haben es durchsucht

Hier sehen wir eine interessante Frage. Wir haben einen Binärbaum. Wir müssen den Baum gegen den Uhrzeigersinn durchqueren. Die Durchlaufreihenfolge ist wie folgt: -

Spiraldurchquerung des Binärbaums gegen den Uhrzeigersinn?

Die Durchlaufreihenfolge ist 1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7

Algorithmus

antiClockTraverse (root)

Begin
   i := 1, j := height of the tree
   flag := false
   while i <= j, do
      if flag is false, then
         print tree elements from right to left for level i
         flag := true
         i := i + 1
      else
         print tree elements from left to right for level j
         flag := false
         j := j - 1
      end if
   done
End
Nach dem Login kopieren

Example

#include<iostream>
using namespace std;
class Node {
   public:
      Node* left;
      Node* right;
      int data;
   Node(int data) { //constructor to create node
      this->data = data;
      this->left = NULL;
      this->right = NULL;
   }
};
int getHeight(Node* root) {
   if (root == NULL)
   return 0;
   //get height of left and right subtree
   int hl = getHeight(root->left);
   int hr = getHeight(root->right);
   return 1 + max(hl, hr); //add 1 for root
}
void printLeftToRight(class Node* root, int level) {
   if (root == NULL)
      return;
   if (level == 1)
      cout << root->data << " ";
   else if (level > 1) {
      printLeftToRight(root->left, level - 1);
      printLeftToRight(root->right, level - 1);
   }
}
void printRightToLeft(struct Node* root, int level) {
   if (root == NULL)
      return;
   if (level == 1)
      cout << root->data << " ";
   else if (level > 1) {
      printRightToLeft(root->right, level - 1);
      printRightToLeft(root->left, level - 1);
   }
}
void antiClockTraverse(class Node* root) {
   int i = 1;
   int j = getHeight(root);
   int flag = 0; //flag is used to change direction
   while (i <= j) {
      if (flag == 0) {
         printRightToLeft(root, i);
         flag = 1; //set flag to print from left to right
         i++;
      }else {
         printLeftToRight(root, j);
         flag = 0; //set flag to print from right to left
         j--;
      }
   }
}
int main() {
   struct Node* root;
   root = new Node(1);
   root->left = new Node(2);
   root->right = new Node(3);
   root->left->left = new Node(4);
   root->left->right = new Node(5);
   root->right->left = new Node(6);
   root->right->right = new Node(7);
   root->left->left->left = new Node(8);
   root->left->left->right = new Node(9);
   root->left->right->left = new Node(10);
   root->left->right->right = new Node(11);
   root->right->left->left = new Node(12);
   root->right->left->right = new Node(13);
   root->right->right->left = new Node(14);
   root->right->right->right = new Node(15);
   antiClockTraverse(root);
}
Nach dem Login kopieren

Output

1 8 9 10 11 12 13 14 15 3 2 4 5 6 7
Nach dem Login kopieren

Das obige ist der detaillierte Inhalt vonSpiraldurchquerung des Binärbaums gegen den Uhrzeigersinn?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!

Verwandte Etiketten:
Quelle:tutorialspoint.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage