遍历是访问树的所有节点并且也可以打印其值的过程,因为所有节点都是通过边(链接)连接的,所以我们总是从根节点开始。也就是说,我们不能随机访问树中的节点。我们使用三种方式遍历树-
通常,我们遍历一棵树以搜索或找到树中的给定项目或键,或打印其中包含的所有值。
在这种遍历方法中,首先访问左子树,然后访问根,然后再访问右子树。我们应该永远记住,每个节点都可能代表一个子树本身。
如果对二叉树进行顺序遍历,则输出将按升序生成排序的键值。
我们从 A 开始,然后按顺序遍历,移至其左侧的子树 B 。 B 也按顺序遍历。一直进行到访问所有节点为止。该树的有序遍历的输出为-
D→B→E→A→F→C→G
在这种遍历方法中,首先访问根节点,然后是左子树,最后是右子树。
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/tree-traversal.html
来源:LearnFk无涯教程网
我们从 A 开始,并在进行预遍历之后,首先访问 A 本身,然后移至其左侧的子树 B 。 B 也已遍历。一直进行到访问所有节点为止。该树的预遍历的输出将是-
A→B→D→E→C→F→G
在这种遍历方法中,根节点是最后访问的,因此是名称。首先,我们先遍历左侧子树,然后遍历右侧子树,最后遍历根节点。
我们从 A 开始,然后遍历Post-order,首先访问左侧的子树 B 。 B 也被遍历。一直进行到访问所有节点为止。该树的后遍历的输出将是-
D→E→B→F→G→C→A
#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
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)