欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

树的遍历(Trees Traversals)

程序员文章站 2022-05-06 21:36:12
...

树的遍历


想要访问二叉树中的节点需要遍历整棵树。通常有三种遍历树的形式,每种遍历形式产生不同顺序的元素。

中序遍历(Left-Root-Right)


中序遍历首先访问左子节点,然后访问根节点,最后再访问右子节点。递归重复此操作,直到遍历完树中的所有元素。

中序遍历算法步骤

  1. 遍历左子树,中序递归调用(左子树)
  2. 访问根结点
  3. 遍历右子树,中序递归调用(右子树)
树的遍历(Trees Traversals)

中序遍历代码

void inorder(struct Node* node){
   if (node==NULL)return;
   inorder(node->left);
   cout<<node-data<<endl;
   inorder(node->right);
}

前序遍历(Root-Left-Right)


在前序遍历中,首先访问根节点,然后访问左节点,最后访问右节点。重复执行递归,直到所有节点都被遍历。

前序遍历算法步骤

  1. 访问根节点
  2. 遍历左子树,前序递归调用(左子树)
  3. 遍历右子树,前序递归调用(右子树)
树的遍历(Trees Traversals)

前序遍历代码

void preorder(struct Node* node){
    if (node==NULL)return;
    cout<<node->data<<endl;
    preorder(node->left);
    preorder(node->right);
}

后序遍历(Left-Right-Root)


后序遍历首先访问左子节点,然后访问右子节点,最后访问根节点。递归重复此操作,直到树中的每个元素都被访问。

后序遍历算法步骤

  1. 遍历左子树,后序递归调用(左子树)
  2. 遍历右子树,后序递归调用(右子树)
  3. 访问根节点
树的遍历(Trees Traversals)

后序遍历代码

void postorder(struct Node* node){
    if (node==NULL)return;
    postorder(node->left);
    postorder(node->right);
}

算法时间复杂度


每棵树的遍历的时间复杂度均为O(n),遍历树所需时间随元素线性增加

更多内容,欢迎访问:


树的遍历(Trees Traversals)