题目
给你二叉树的根节点 root ，返回它节点值的 前序 遍历。
示例 1：
输入：root = [1,null,2,3]
输出：[1,2,3]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [1]
输出：[1]
示例 4：
输入：root = [1,2]
输出：[1,2]
示例 5：
输入：root = [1,null,2]
输出：[1,2]
提示：
树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
分析
递归法
判断给的指针是否为NULL，非空的话先输出自己，然后调用自己的左子树，最后调用自己的右子树。
C
#incl#include<stdio.h> #include<assert.h> #include<stdlib.h> #define MAXSIZE 100 /* 存储空间初始分配量 */ typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */ typedef struct node { TElemType data; struct node * lchild, * rchild;//左右孩纸指针 }BTree; void CreatTree(BTree** T)//构造二叉树 { TElemType n = 0; scanf("%d", &n); if(999 != n) { (*T) = (BTree*)malloc(sizeof(BTree)); assert(NULL != *T); (*T)->data = n; CreatTree(&((*T)->lchild)); CreatTree(&((*T)->rchild)); } else { *T = NULL; } } //先序遍历 递归法 void preorderTraversalRecursion(BTree* T) { if(NULL == T) { return ; } printf("%d ", T->data); //先输出 preorderTraversalRecursion(T->lchild);//再向左子树走 preorderTraversalRecursion(T->rchild);//最后向右子树走 } int main() { BTree* root = NULL; CreatTree(&root); printf("递归的先序输出：\t"); preorderTraversalRecursion(root); printf("\n"); return 0; }
迭代法(栈)
用一个栈来存储每次遇到的节点，先一直向左子树节点遍历，并保存到栈中。若为NULL时，从栈中取出最近一次遍历过的节点，然后访问该节点的右子树节点，若再为NULL，就再从栈中取出。
C
#include<stdio.h> #include<assert.h> #include<stdlib.h> #define MAXSIZE 100 /* 存储空间初始分配量 */ typedef int TElemType; /* 树结点的数据类型，目前暂定为整型 */ typedef struct node { TElemType data; struct node * lchild, * rchild;//左右孩纸指针 }BTree; void CreatTree(BTree** T)//构造二叉树 { TElemType n = 0; scanf("%d", &n); if(999 != n) { (*T) = (BTree*)malloc(sizeof(BTree)); assert(NULL != *T); (*T)->data = n; CreatTree(&((*T)->lchild)); CreatTree(&((*T)->rchild)); } else { *T = NULL; } } //先序输出 非递归法 栈 void preorderTraversalnoRecursion(BTree* T) { assert(T != NULL); BTree* n[MAXSIZE] = { 0 };//0下标不存数据 n[0] = NULL; int i = 0; while(T != NULL || i > 0) { while(T != NULL) { printf("%d ", T->data); i++; n[i] = T; T = T->lchild; } T = n[i]; i--; T = T->rchild; } } int main() { BTree* root = NULL; CreatTree(&root); printf("非递归的先序输出：\t"); preorderTraversalnoRecursion(root); printf("\n"); return 0; }
本章完！
