树的遍历有先序,中序,后序,层序。
- InOrder
- PreOrder
- PostOrder
- LevelOrder
对应前三种遍历顺序,都有三种实现方式。
- Recursive
- Stack
- Morris
遍历一棵树的递归算法是简单而显然的。
递归中序遍历和先序遍历
void PrintTreeInOrder(SearchTree t){
if(t){
PrintTreeInOrder(t->left);
printf("%d\t", t->val);
PrintTreeInOrder(t->right);
}
}
void PrintTreePreOrder(SearchTree t){
if(t){
printf("%d\t", t->val);
PrintTreePreOrder(t->left);
PrintTreePreOrder(t->right);
}
}
用栈的三种顺序遍历
InOrder
- 先一次直接探到左子树最深处,依此入栈这些左子树不为空的节点,打印最后没有左子树的那个叶子节点。
- 依次出栈,找到一个右子树不为空的节点,打印这个根节点,入栈它的右子树节点
- 栈空时,所有元素打印了一遍
void InorderTraversalByStack(AvlTree root){
if(root == NULL)
return;
AvlTree* stack = (AvlTree*)malloc(100 * sizeof(AvlTree));
int top = -1;
struct TreeNode* p = root;
stack[++top] = p;
while(top != -1){
while((stack[top])->left){
p = stack[top];
stack[++top] = p->left;
}
while(top != -1){
p = stack[top--];
printf("%d\t", p->val);
if(p->right){
stack[++top] = p->right;
break;
}
}
}
free(stack);
}
PreOrder
类比中序遍历,每次入栈的是有左子树的节点,因为是先序遍历,打印这些节点。
void PreOrderTraversalByStack(AvlTree root){
struct TreeNode* stack = (struct TreeNode*)malloc(100 * sizeof(struct TreeNode));
int top = -1;
struct TreeNode* p = root;
while(p){
if(p->left == NULL){
printf("%d\t", p->val);
p = p->right;
if(p == NULL){
while((stack[top]).right == NULL && top != -1)
top--;
if(top != -1)
p = (stack[top--]).right;
}
}
else{
stack[++top] = *p;
printf("%d\t", (stack[top]).val);
p = p->left;
}
}
free(stack);
}
更新一下,上面的方法很蠢,还是受了莫里斯方法的影响。下面的代码会简洁直观的多,值得注意的是,先入栈的是右儿子。
PreOrder ++
void PreOrderTraversalByStack(AvlTree root){
if(!root)
return;
AvlTree* stack = (AvlTree*)malloc(100 * sizeof(AvlTree));
int top = -1;
stack[++top] = root;
while(top != -1){
AvlTree p = stack[top--];
printf("%d\t", p->val);
if(p->right)
stack[++top] = p->right;
if(p->left)
stack[++top] = p->left;
}
free(stack);
}
PostOrder
设置pLast
指针判断当前节点的左儿子和右儿子是否被访问过。
- 如果都没有访问过,那么它是一个新的节点,先入栈当前的左儿子节点。
- 如果当前的节点的左儿子节点被访问过(而右节点没有),就入栈它的右儿子节点。
- 如果都被访问过,那么打印这个根结点并出栈。
当栈空时,所有节点都被访问一遍。
void PostOrderTraversalByStack(AvlTree root){
if(root == NULL)
return;
AvlTree* stack = (AvlTree*)malloc(100 * sizeof(AvlTree));
int top = -1;
struct TreeNode* pCur = root;
struct TreeNode* pLast = root;
stack[++top] = pCur;
while(top != -1){
pCur = stack[top];
if(pCur->left != NULL && pLast != pCur->left && pLast != pCur->right)
stack[++top] = pCur->left;
else if(pCur->right != NULL && pLast != pCur->right)
stack[++top] = pCur->right;
else{
printf("%d\t", (stack[top--])->val);
pLast = pCur;
}
}
free(stack);
}
MorrisTraversal
- 利用所有叶子结点的right 指针,指向其后继结点,组成一个环,在第二次遍历到这个结点时,由于其左子树已经遍历完了,则访问该结点
void PrintMorrisTraversal(SearchTree root){
struct TreeNode* p = root, *tmp = NULL;
while(p){
if(p->left == NULL){
printf("%d\t", p->val);
p = p->right;
}
else{
tmp = p->left;
while(tmp->right != NULL && tmp->right != p)
tmp = tmp->right;
if(tmp->right == NULL){
tmp->right = p;
p = p->left;
}
else{
printf("%d\t", p->val);
tmp->right = NULL;
p = p->right;
}
}
}
}
最后说一下层序遍历
层序遍历也有递归实现和队列实现。
LevelTraversal队列实现(Java)
LinkedList<List<Integer>> res = new LinkedList<>();
Queue<TreeNode> que = new LinkedList<>();
if(root == null)
return res;
que.offer(root);
while(!que.isEmpty()) {
int levelSize = que.size();
List<Integer> levelList = new ArrayList<>();
while(levelSize-- > 0) {
TreeNode t = que.poll();
levelList.add(t.val);
if(t.left != null)
que.offer(t.left);
if(t.right != null)
que.offer(t.right);
}
res.addFirst(levelList);
}
return res;
}
入队每一层的所有节点,下一次出队时,访问这一层的所有节点,并依此将它们的左右儿子入队。
队内实际上始终只存储这一层的节点。