树的遍历(Trees Traversals)
程序员文章站
2022-05-06 21:36:12
...
树的遍历
想要访问二叉树中的节点需要遍历整棵树。通常有三种遍历树的形式,每种遍历形式产生不同顺序的元素。
中序遍历(Left-Root-Right)
中序遍历首先访问左子节点,然后访问根节点,最后再访问右子节点。递归重复此操作,直到遍历完树中的所有元素。
中序遍历算法步骤
- 遍历左子树,中序递归调用(左子树)
- 访问根结点
- 遍历右子树,中序递归调用(右子树)
中序遍历代码
void inorder(struct Node* node){
if (node==NULL)return;
inorder(node->left);
cout<<node-data<<endl;
inorder(node->right);
}
前序遍历(Root-Left-Right)
在前序遍历中,首先访问根节点,然后访问左节点,最后访问右节点。重复执行递归,直到所有节点都被遍历。
前序遍历算法步骤
- 访问根节点
- 遍历左子树,前序递归调用(左子树)
- 遍历右子树,前序递归调用(右子树)
前序遍历代码
void preorder(struct Node* node){
if (node==NULL)return;
cout<<node->data<<endl;
preorder(node->left);
preorder(node->right);
}
后序遍历(Left-Right-Root)
后序遍历首先访问左子节点,然后访问右子节点,最后访问根节点。递归重复此操作,直到树中的每个元素都被访问。
后序遍历算法步骤
- 遍历左子树,后序递归调用(左子树)
- 遍历右子树,后序递归调用(右子树)
- 访问根节点
后序遍历代码
void postorder(struct Node* node){
if (node==NULL)return;
postorder(node->left);
postorder(node->right);
}
算法时间复杂度
每棵树的遍历的时间复杂度均为O(n),遍历树所需时间随元素线性增加
更多内容,欢迎访问: