二叉树遍历

分析&回答

二叉树是一种非常重要的数据结构，非常多其他数据结构都是基于二叉树的基础演变而来的。对于二叉树，有深度遍历和广度遍历，深度遍历有前序、中序以及后序三种遍历方法，广度遍历即我们寻常所说的层次遍历。

四种基本的遍历思想为：

• （深度遍历）前序遍历：根结点 ---> 左子树 ---> 右子树
• （深度遍历）中序遍历：左子树---> 根结点 ---> 右子树
• （深度遍历）后序遍历：左子树 ---> 右子树 ---> 根结点
• （广度遍历）层次遍历：仅仅需按层次遍历就可以

• 前序遍历：1  2  4  5  7  8  3  6 
• 中序遍历：4  2  7  5  8  1  3  6 
• 后序遍历：4  7  8  5  2  6  3  1 
• 层次遍历：1  2  3  4  5  6  7  8 

递归排序写法

/**
 * 前序遍历
 * @param root
 */
public void preOrderTraverse1(TreeNode root) {
    if (root != null) {
        System.out.print(root.val+"  ");
        preOrderTraverse1(root.left);
        preOrderTraverse1(root.right);
    }
}

/**
 * 中序遍历
 * @param root
 */
public void inOrderTraverse1(TreeNode root) {
    if (root != null) {
        inOrderTraverse1(root.left);
        System.out.print(root.val+"  ");
        inOrderTraverse1(root.right);
    }
}


/**
 * 后续遍历
 * @param root
 */
public void postOrderTraverse1(TreeNode root) {
    if (root != null) {
        postOrderTraverse1(root.left);
        postOrderTraverse1(root.right);
        System.out.print(root.val+"  ");
    }
}

非递归排序写法

/**
 * 前序遍历
 * @param root
 */
public void preOrderTraverse2(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pNode = root;
    while (pNode != null || !stack.isEmpty()) {
        if (pNode != null) {
            System.out.print(pNode.val+"  ");
            stack.push(pNode);
            pNode = pNode.left;
        } else { //pNode == null && !stack.isEmpty()
            TreeNode node = stack.pop();
            pNode = node.right;
        }
    }
}

/**
 * 中序遍历
 * @param root
 */
public void inOrderTraverse2(TreeNode root) {
    LinkedList<TreeNode> stack = new LinkedList<>();
    TreeNode pNode = root;
    while (pNode != null || !stack.isEmpty()) {
        if (pNode != null) {
            stack.push(pNode);
            pNode = pNode.left;
        } else { //pNode == null && !stack.isEmpty()
            TreeNode node = stack.pop();
            System.out.print(node.val+"  ");
            pNode = node.right;
        }
    }
}


/**
 * 后序遍历
 */
void postOrder2(BinTree *root)    //非递归后序遍历
{
    stack<BTNode*> s;
    BinTree *p=root;
    BTNode *temp;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)              //沿左子树一直往下搜索。直至出现没有左子树的结点
        {
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
            btn->btnode=p;
            btn->isFirst=true;
            s.push(btn);
            p=p->lchild;
        }
        if(!s.empty())
        {
            temp=s.top();
            s.pop();
            if(temp->isFirst==true)     //表示是第一次出如今栈顶
            {
                temp->isFirst=false;
                s.push(temp);
                p=temp->btnode->rchild;
            }
            else                        //第二次出如今栈顶
            {
                cout<<temp->btnode->data<<" ";
                p=NULL;
            }
        }
    }
}


/**
 * 层次遍历
 * @param root
 */
public void levelTraverse(TreeNode root) {
    if (root == null) {
        return;
    }
    LinkedList<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val+"  ");
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

反思&扩展

由于树的定义本身就是递归定义，因此采用递归的方法去实现树的三种遍历不仅easy理解并且代码非常简洁，而对于广度遍历来说，须要其他数据结构的支撑。比如：堆。所以。对于一段代码来说，有时候可读性要比代码本身的效率要重要的多。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！