树遍历

树遍历 首页 / 结构和算法入门教程 / 树遍历

遍历是访问树的所有节点并且也可以打印其值的过程,因为所有节点都是通过边(链接)连接的,所以我们总是从根节点开始。也就是说,我们不能随机访问树中的节点。我们使用三种方式遍历树-

  • 前序遍历
  • 中序遍历
  • 后序遍历

通常,我们遍历一棵树以搜索或找到树中的给定项目或键,或打印其中包含的所有值。

前序遍历

在这种遍历方法中,首先访问左子树,然后访问根,然后再访问右子树。我们应该永远记住,每个节点都可能代表一个子树本身。

如果对二叉树进行顺序遍历,则输出将按升序生成排序的键值。

In Order Traversal

我们从 A 开始,然后按顺序遍历,移至其左侧的子树 B 。 B 也按顺序遍历。一直进行到访问所有节点为止。该树的有序遍历的输出为-

D→B→E→A→F→C→G

中序遍历

在这种遍历方法中,首先访问根节点,然后是左子树,最后是右子树。

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/tree-traversal.html

来源:LearnFk无涯教程网

Pre Order Traversal

我们从 A 开始,并在进行预遍历之后,首先访问 A 本身,然后移至其左侧的子树 B 。 B 也已遍历。一直进行到访问所有节点为止。该树的预遍历的输出将是-

A→B→D→E→C→F→G

后序遍历

在这种遍历方法中,根节点是最后访问的,因此是名称。首先,我们先遍历左侧子树,然后遍历右侧子树,最后遍历根节点。

无涯教程网

Post Order Traversal

我们从 A 开始,然后遍历Post-order,首先访问左侧的子树 B 。 B 也被遍历。一直进行到访问所有节点为止。该树的后遍历的输出将是-

D→E→B→F→G→C→A

C实现树遍历代码

Binary Search 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

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

算法面试通关40讲 -〔覃超〕

NLP实战高手课 -〔王然〕

Linux内核技术实战课 -〔邵亚方〕

玩转Vue 3全家桶 -〔大圣〕

eBPF核心技术与实战 -〔倪朋飞〕

遗留系统现代化实战 -〔姚琪琳〕

Kubernetes入门实战课 -〔罗剑锋〕

深入拆解消息队列47讲 -〔许文强〕

结构沟通力 -〔李忠秋〕

好记忆不如烂笔头。留下您的足迹吧 :)