上一节:
下一节:

  数据结构&算法 树遍历

  • 树遍历

    遍历是访问树的所有节点并且也可以打印其值的过程。因为所有节点都是通过边（链接）连接的，所以我们总是从根（头）节点开始。也就是说，我们不能随机访问树中的节点。我们使用三种方式遍历树-
    • 中序遍历
    • 前序遍历
    • 后序遍历
    通常，我们遍历一棵树以搜索或定位树中的给定项或键，或打印其中包含的所有值。

  • 中序遍历

    在这种遍历方法中，首先访问左子树，然后访问根，然后再访问右子树。我们应该永远记住，每个节点本身都可以代表一个子树。
    如果按顺序遍历二叉树，则输出将产生升序排序的键值。
    tree
    我们从A开始，按照顺序遍历，移动到它的左子树B。B也是按顺序遍历的。这个过程一直进行，直到访问了所有节点。这个树的中序遍历的输出将是−
    D → B → E → A → F → C → G
    算法 
    
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

  • 前序遍历

    在这种遍历方法中，首先访问根节点，然后是左子树，最后是右子树。
    tree
    我们从A开始，并在进行预遍历之后，首先访问A本身，然后移至其左子树B。B也进行了预遍历。 一直进行到访问所有节点为止。 该树的预遍历的输出将是-
    A → B → D → E → C → F → G
    算法 
    
Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

  • 后序遍历

    在这种遍历方法中，根节点是最后访问的，因此是名称。首先，我们先遍历左侧子树，然后遍历右侧子树，最后遍历根节点。
    tree
    我们从A开始，然后经过后序遍历，首先访问左子树B。B也经过后序遍历。 一直进行到访问所有节点为止。 该树的后遍历的输出将是-
    D → E → B → F → G → C → A
    算法 
    
Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

  • 示例

    现在，我们将在这里使用以下二进制树查看C编程语言中树遍历的实现-
    tree
    
#include <stdio.h>
#include <stdlib.h>

struct node {
   int data; 
  
   struct node *leftChild;
   struct node *rightChild;
};

struct node *root = NULL;

void insert(int data) {
   struct node *tempNode = (struct node*) malloc(sizeof(struct node));
   struct node *current;
   struct node *parent;

   tempNode->data = data;
   tempNode->leftChild = NULL;
   tempNode->rightChild = NULL;

   //if tree is empty
   if(root == NULL) {
      root = tempNode;
   } else {
      current = root;
      parent = NULL;

      while(1) { 
         parent = current;
         
         //go to left of the tree
         if(data < parent->data) {
            current = current->leftChild;                
            
            //insert to the left
            if(current == NULL) {
               parent->leftChild = tempNode;
               return;
            }
         }  //go to right of the tree
         else {
            current = current->rightChild;

            //insert to the right
            if(current == NULL) {
               parent->rightChild = tempNode;
               return;
            }
         }
      }            
   }
}

struct node* search(int data) {
   struct node *current = root;
   printf("Visiting elements: ");

   while(current->data != data) {
      if(current != NULL)
         printf("%d ",current->data); 

      //go to left tree
      if(current->data > data) {
         current = current->leftChild;
      }
      //else go to right tree
      else {                
         current = current->rightChild;
      }

      //not found
      if(current == NULL) {
         return NULL;
      }
   }
   
   return current;
}

void pre_order_traversal(struct node* root) {
   if(root != NULL) {
      printf("%d ",root->data);
      pre_order_traversal(root->leftChild);
      pre_order_traversal(root->rightChild);
   }
}

void inorder_traversal(struct node* root) {
   if(root != NULL) {
      inorder_traversal(root->leftChild);
      printf("%d ",root->data);          
      inorder_traversal(root->rightChild);
   }
}

void post_order_traversal(struct node* root) {
   if(root != NULL) {
      post_order_traversal(root->leftChild);
      post_order_traversal(root->rightChild);
      printf("%d ", root->data);
   }
}

int main() {
   int i;
   int array[7] = { 27, 14, 35, 10, 19, 31, 42 };

   for(i = 0; i < 7; i++)
      insert(array[i]);

   i = 31;
   struct node * temp = search(i);

   if(temp != NULL) {
      printf("[%d] Element found.", temp->data);
      printf("\n");
   }else {
      printf("[ x ] Element not found (%d).\n", i);
   }

   i = 15;
   temp = search(i);

   if(temp != NULL) {
      printf("[%d] Element found.", temp->data);
      printf("\n");
   }else {
      printf("[ x ] Element not found (%d).\n", i);
   }            

   printf("\nPreorder traversal: ");
   pre_order_traversal(root);

   printf("\nInorder traversal: ");
   inorder_traversal(root);

   printf("\nPost order traversal: ");
   post_order_traversal(root);       

   return 0;
}
    尝试一下
    如果我们编译并运行上述程序，它将产生以下结果- 
    
Visiting elements: 27 35 [31] Element found.
Visiting elements: 27 14 19 [ x ] Element not found (15).

Preorder traversal: 27 14 10 19 35 31 42 
Inorder traversal: 10 14 19 27 31 35 42 
Post order traversal: 10 19 14 31 42 35 27
上一节:
下一节: