二叉树的三种遍历（先序，中序，后序）

二叉树的遍历

1、递归形式的遍历

1.1先序遍历

先访问父亲节点，在访问左叶子节点，在访问右叶子节点，代码如下：

void preOrder(TreeNode root){

if(root!=null){

vistit(root);

preOrder(root->lchild);

preOrder(root->rchild);

}

}

1.2中序遍历

先访问左叶子节点，在访问父亲节点，在访问右孩子节点

void middleOrder(TreeNode root){

if(root!=null){

preOrder(root->lchild);

vistit(root);

preOrder(root->rchild);

}

}

1.3后序遍历

先访问左右叶子节点,在访问父亲节点

void postOrder(TreeNode root){

if(root!=null){

preOrder(root->lchild);

preOrder(root->rchild);

vistit(root);

}

}

2、非递归遍历

2.1先序遍历

void preOrder2(TreeNode root){

Stack();

TreeNode pNode=root;

while(pNode!=null || stack.isNotEmpty){

if(pNode!=null){

visit(pNode);

stack.push(pNode);

pNode=pNode->lchild;

}else{

TreeNode node=stack.pop();

pNode=node->rchild;

}

}

}

2.2中序遍历

void middleOrder(TreeNode root){

Stack();

TreeNode pNode=root;

while(pNode!=null || stack.isNotEmpty()){

if(pNode!=null){

stack.push(pNode);

pNode=pNode->lchild;

}else{

TreeNode node=stack.pop();

visit(node);

pNode=node->rchild;

}

}

}

2.3后序遍历

思路：从根节点以次入栈，先入右孩子节点，再入左孩子节点，直到节点的左右孩子都没有，再出栈。由于栈的特性，先进后出，先入右孩子可以保证先访问左孩子，在访问右孩子，在是父亲节点。为了防止访问再次进入访问过的节点，每次记录上次访问的节点。

void postOrder(TreeNode root){

Stack();

TreeNode pNode,pre=null;

stack.push(root);

while(stack.isNotEmpty()){

pNode=s.top();

if((pNode->lchild==null&&pNode->rchild==null)||(pNode->lchild==pre||pNode->rchild==pre)){

visit(pNode);

stack.pop();

pre=pNode;

}else{

if(pNode->rchild!=null){

stack.push(pNode->rchild);

}

if(pNode->lchild!=null){

stack.push(pNode->lchild);

}

}

}

}