树的遍历

1,440 阅读3分钟

树的遍历有先序,中序,后序,层序。

  • 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;
    }

入队每一层的所有节点,下一次出队时,访问这一层的所有节点,并依此将它们的左右儿子入队。

队内实际上始终只存储这一层的节点。