# 如何实现树遍历？先序、中序和后序遍历详细代码

2021年3月31日18:36:23 发表评论 1,102 次浏览

## 本文概述

(a)先序遍历(左, 根, 右)：4 2 5 1 3

(b)中序遍历(根, 左, 右)：1 2 4 5 3

(c)后续遍历(左, 右, 根)：4 5 2 3 1

``````Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)``````

``````Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)``````

``````Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.``````

## C++

``````// C program for different tree traversals
#include <iostream>
using namespace std;

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct Node
{
int data;
struct Node* left, *right;
Node( int data)
{
this ->data = data;
left = right = NULL;
}
};

/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder( struct Node* node)
{
if (node == NULL)
return ;

// first recur on left subtree
printPostorder(node->left);

// then recur on right subtree
printPostorder(node->right);

// now deal with the node
cout << node->data << " " ;
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder( struct Node* node)
{
if (node == NULL)
return ;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
cout << node->data << " " ;

/* now recur on right child */
printInorder(node->right);
}

/* Given a binary tree, print its nodes in preorder*/
void printPreorder( struct Node* node)
{
if (node == NULL)
return ;

/* first print data of node */
cout << node->data << " " ;

/* then recur on left sutree */
printPreorder(node->left);

/* now recur on right subtree */
printPreorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
struct Node *root = new Node(1);
root->left             = new Node(2);
root->right         = new Node(3);
root->left->left     = new Node(4);
root->left->right = new Node(5);

cout << "\nPreorder traversal of binary tree is \n" ;
printPreorder(root);

cout << "\nInorder traversal of binary tree is \n" ;
printInorder(root);

cout << "\nPostorder traversal of binary tree is \n" ;
printPostorder(root);

return 0;
}``````

## C

``````// C program for different tree traversals
#include <stdio.h>
#include <stdlib.h>

/* A binary tree node has data, pointer to left child
and a pointer to right child */
struct node
{
int data;
struct node* left;
struct node* right;
};

/* Helper function that allocates a new node with the
given data and NULL left and right pointers. */
struct node* newNode( int data)
{
struct node* node = ( struct node*)
malloc ( sizeof ( struct node));
node->data = data;
node->left = NULL;
node->right = NULL;

return (node);
}

/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder( struct node* node)
{
if (node == NULL)
return ;

// first recur on left subtree
printPostorder(node->left);

// then recur on right subtree
printPostorder(node->right);

// now deal with the node
printf ( "%d " , node->data);
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder( struct node* node)
{
if (node == NULL)
return ;

/* first recur on left child */
printInorder(node->left);

/* then print the data of node */
printf ( "%d " , node->data);

/* now recur on right child */
printInorder(node->right);
}

/* Given a binary tree, print its nodes in preorder*/
void printPreorder( struct node* node)
{
if (node == NULL)
return ;

/* first print data of node */
printf ( "%d " , node->data);

/* then recur on left sutree */
printPreorder(node->left);

/* now recur on right subtree */
printPreorder(node->right);
}

/* Driver program to test above functions*/
int main()
{
struct node *root  = newNode(1);
root->left             = newNode(2);
root->right           = newNode(3);
root->left->left     = newNode(4);
root->left->right   = newNode(5);

printf ( "\nPreorder traversal of binary tree is \n" );
printPreorder(root);

printf ( "\nInorder traversal of binary tree is \n" );
printInorder(root);

printf ( "\nPostorder traversal of binary tree is \n" );
printPostorder(root);

getchar ();
return 0;
}``````

## python

``````# Python program to for tree traversals

# A class that represents an individual node in a
# Binary Tree
class Node:
def __init__( self , key):
self .left = None
self .right = None
self .val = key

# A function to do inorder tree traversal
def printInorder(root):

if root:

# First recur on left child
printInorder(root.left)

# then print the data of node
print (root.val), # now recur on right child
printInorder(root.right)

# A function to do postorder tree traversal
def printPostorder(root):

if root:

# First recur on left child
printPostorder(root.left)

# the recur on right child
printPostorder(root.right)

# now print the data of node
print (root.val), # A function to do preorder tree traversal
def printPreorder(root):

if root:

# First print the data of node
print (root.val), # Then recur on left child
printPreorder(root.left)

# Finally recur on right child
printPreorder(root.right)

# Driver code
root = Node( 1 )
root.left      = Node( 2 )
root.right     = Node( 3 )
root.left.left  = Node( 4 )
root.left.right  = Node( 5 )
print "Preorder traversal of binary tree is"
printPreorder(root)

print "\nInorder traversal of binary tree is"
printInorder(root)

print "\nPostorder traversal of binary tree is"
printPostorder(root)``````

## Java

``````// Java program for different tree traversals

/* Class containing left and right child of current
node and key value*/
class Node
{
int key;
Node left, right;

public Node( int item)
{
key = item;
left = right = null ;
}
}

class BinaryTree
{
// Root of Binary Tree
Node root;

BinaryTree()
{
root = null ;
}

/* Given a binary tree, print its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(Node node)
{
if (node == null )
return ;

// first recur on left subtree
printPostorder(node.left);

// then recur on right subtree
printPostorder(node.right);

// now deal with the node
System.out.print(node.key + " " );
}

/* Given a binary tree, print its nodes in inorder*/
void printInorder(Node node)
{
if (node == null )
return ;

/* first recur on left child */
printInorder(node.left);

/* then print the data of node */
System.out.print(node.key + " " );

/* now recur on right child */
printInorder(node.right);
}

/* Given a binary tree, print its nodes in preorder*/
void printPreorder(Node node)
{
if (node == null )
return ;

/* first print data of node */
System.out.print(node.key + " " );

/* then recur on left sutree */
printPreorder(node.left);

/* now recur on right subtree */
printPreorder(node.right);
}

// Wrappers over above recursive functions
void printPostorder()  {     printPostorder(root);  }
void printInorder()    {     printInorder(root);   }
void printPreorder()   {     printPreorder(root);  }

// Driver method
public static void main(String[] args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node( 1 );
tree.root.left = new Node( 2 );
tree.root.right = new Node( 3 );
tree.root.left.left = new Node( 4 );
tree.root.left.right = new Node( 5 );

System.out.println( "Preorder traversal of binary tree is " );
tree.printPreorder();

System.out.println( "\nInorder traversal of binary tree is " );
tree.printInorder();

System.out.println( "\nPostorder traversal of binary tree is " );
tree.printPostorder();
}
}``````

## C#

``````// C# program for different
// tree traversals
using System;

/* Class containing left and
right child of current
node and key value*/
class Node
{
public int key;
public Node left, right;

public Node( int item)
{
key = item;
left = right = null ;
}
}

class BinaryTree
{
// Root of Binary Tree
Node root;

BinaryTree()
{
root = null ;
}

/* Given a binary tree, print
its nodes according to the
"bottom-up" postorder traversal. */
void printPostorder(Node node)
{
if (node == null )
return ;

// first recur on left subtree
printPostorder(node.left);

// then recur on right subtree
printPostorder(node.right);

// now deal with the node
Console.Write(node.key + " " );
}

/* Given a binary tree, print
its nodes in inorder*/
void printInorder(Node node)
{
if (node == null )
return ;

/* first recur on left child */
printInorder(node.left);

/* then print the data of node */
Console.Write(node.key + " " );

/* now recur on right child */
printInorder(node.right);
}

/* Given a binary tree, print
its nodes in preorder*/
void printPreorder(Node node)
{
if (node == null )
return ;

/* first print data of node */
Console.Write(node.key + " " );

/* then recur on left sutree */
printPreorder(node.left);

/* now recur on right subtree */
printPreorder(node.right);
}

// Wrappers over above recursive functions
void printPostorder() {printPostorder(root);}
void printInorder()  {printInorder(root);}
void printPreorder() {printPreorder(root);}

// Driver Code
static public void Main(String []args)
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);

Console.WriteLine( "Preorder traversal " +
"of binary tree is " );
tree.printPreorder();

Console.WriteLine( "\nInorder traversal " +
"of binary tree is " );
tree.printInorder();

Console.WriteLine( "\nPostorder traversal " +
"of binary tree is " );
tree.printPostorder();
}
}

// This code is contributed by Arnab Kundu``````

``````Preorder traversal of binary tree is
1 2 4 5 3
Inorder traversal of binary tree is
4 2 5 1 3
Postorder traversal of binary tree is
4 5 2 3 1``````

T(n)= T(k)+ T(n – k – 1)+ c

T(n)= T(0)+ T(n-1)+ c

T(n)= 2T(0)+ T(n-2)+ 2c

T(n)= 3T(0)+ T(n-3)+ 3c

T(n)= 4T(0)+ T(n-4)+ 4c

…………………………………………

…………………………………………。

T(n)=(n-1)T(0)+ T(1)+(n-1)c

T(n)= nT(0)+(n)c

T(0)的值将是一个常数, 例如d。 (遍历一棵空树将花费一些常量时间)

T(n)= n(c + d)

T(n)=Θ(n)(n的θ)

T(n)= 2T(| _n / 2_ |)+ c