求二叉树的先序遍历
先序遍历是二叉树遍历算法中的一种，也是最基础的一种遍历方式。该遍历方式是按照“根节点->左子树->右子树”的顺序遍历整个二叉树，得到的结果就是二叉树的先序遍历。下面将从多个角度来对该算法进行分析。
1. 原理
二叉树的先序遍历是按照根节点的访问顺序进行遍历的。首先访问根节点，然后递归遍历它的左子树，最后递归遍历它的右子树。具体实现时，可以采用递归算法或非递归算法。
递归算法实现过程如下：
1）判断当前节点是否为空；
2）如果当前节点不为空，则输出当前节点的值；
3）递归遍历它的左子树；
4）递归遍历它的右子树。
非递归算法实现过程如下：
1）申请一个栈，将根节点压入栈中；
2）循环进行以下操作，直到栈为空：
a)弹出栈顶元素，并输出该元素的值；
b)将弹出元素的右子树节点压入栈中，如果它存在的话；
c)将弹出元素的左子树节点压入栈中，如果它存在的话。
2. 时间复杂度
假设二叉树的节点数为n，则先序遍历需要访问每个节点一次。因此，先序遍历的时间复杂度为O(n)。
3. 空间复杂度
递归实现的先序遍历需要使用递归调用栈，因此它的空间复杂度为O(h)，其中h是二叉树的高度。由于非递归算法使用了栈来实现，因此它的空间复杂度也是O(h)。
4. 代码实现
递归实现的代码：
```
void PreorderTraversal(BinaryTree *root){
if (root != NULL){
printf("%d ", root->val); //输出节点的值
PreorderTraversal(root->left); //遍历左子树
PreorderTraversal(root->right); //遍历右子树
}
}
```
非递归实现的代码：
```
void PreorderTraversal(BinaryTree *root){
stack
BinaryTree *p = root;
while (p != NULL || !s.empty()){
while (p != NULL){
printf("%d ", p->val); //输出节点的值
s.push(p); //将节点压入栈中
p = p->left; //遍历左子树
}
if (!s.empty()){
p = s.top();
s.pop();
p = p->right; //遍历右子树
}
}
}
```
5. 应用场景
二叉树先序遍历是二叉树遍历算法的基础，并且在很多算法中都有重要应用。例如，二叉树的序列化和反序列化、二叉搜索树的最近公共祖先等问题都需要用到先序遍历的算法。
6.
