二叉树建立及遍历的算法

二叉树是一种树形结构，它的每个节点最多只有两个子节点。二叉树的遍历方式有三种：先序遍历、中序遍历和后序遍历。其中，先序遍历是指先访问根节点，然后访问左子树，最后访问右子树；中序遍历是指先访问左子树，然后访问根节点，最后访问右子树；后序遍历是指先访问左子树，然后访问右子树，最后访问根节点。

二叉树的建立可以通过递归或非递归方式实现。递归方式建立二叉树的过程是：先读入一个节点的值，如果该节点的值不为空，则创建一个新节点，并将该节点的值赋给新节点；然后递归调用建立左子树和右子树的过程，直到读入的节点值为空为止。非递归方式建立二叉树的过程是：使用一个栈来存储节点，先读入根节点的值，创建一个新节点，并将该节点入栈；然后读入下一个节点的值，如果该节点的值不为空，则创建一个新节点，并将该节点入栈，并将该节点作为上一个节点的左子节点；如果该节点的值为空，则弹出栈顶节点，并将该节点作为上一个节点的右子节点。

二叉树的遍历算法可以通过递归或非递归方式实现。递归方式实现二叉树的遍历算法比较简单，只需要按照遍历顺序递归访问左子树和右子树即可。非递归方式实现二叉树的遍历算法需要使用栈来存储节点。先序遍历的非递归算法是：先将根节点入栈，然后弹出栈顶节点并访问该节点，将该节点的右子节点入栈，再将该节点的左子节点入栈，重复上述过程直到栈为空；中序遍历的非递归算法是：先将根节点入栈，然后将根节点的所有左子节点入栈，重复弹出栈顶节点并访问该节点，将该节点的右子节点入栈，重复上述过程直到栈为空；后序遍历的非递归算法是：先将根节点入栈，然后将根节点的所有左子节点入栈，重复弹出栈顶节点并访问该节点，如果该节点的右子节点不为空且未被访问过，则将该节点的右子节点入栈，否则访问该节点，重复上述过程直到栈为空。