앞차례, 중차례, 뒷차례가 두루 흐르는 여러 가지 비귀속 실현

우리는 먼저 앞의 순서로 전체 나무를 어떻게 접근하는지 보았다. 먼저 뿌리 노드를 방문한 다음에 왼쪽 노드를 방문한 다음에 오른쪽 노드를 방문한다.만약 귀속되지 않는다면 어떻게 해야 합니까?귀환 프로그램을 자세히 보면 매번 트리의 왼쪽 지점(left)을 걷고 왼쪽 트리가 비어 있을 때까지 귀환의 가장 깊은 곳에서 귀환하기 시작한 다음에 귀환 현장을 회복하고 오른쪽 트리를 방문한다.
사실 과정은 매우 간단하다: 루트->left->left->left->left...->null, 앞의 순서가 겹치기 때문에 노드를 만나면 즉시 방문해야 합니다.가장 왼쪽까지 가면 부모 노드로 돌아가 오른쪽 노드를 방문해야 하기 때문에 노드의 서열을 거슬러 올라갈 수 있는 조치가 있어야 한다.그래서 우리는 창고로 기억하는 방법을 생각했다. 방문 도중에 차례대로 만나는 노드를 저장하는 것이다.노드의 출현 순서와 회복 순서는 반차례이기 때문에 선진적인 후출 구조이기 때문에 창고를 사용해야 한다.창고 기억을 사용하는 실현은 두 가지 버전이 있다. 첫 번째 버전은 추적 바늘 이동을 창고로 중간 결과를 저장하는 실현 방식이고 두 번째 버전은 직접 아날로그 귀환이다.
1. 추적 포인터 이동용 창고에 중간 결과 저장
앞의 순서는 창고에 들어가기 전에 방문하는 것이고, 중간 순서는 창고를 나갈 때 방문하는 것이며, 뒤의 순서는 이런 방법으로는 실현하기 어렵다.
노드 정의:
 

typedef struct BiNode{

  int data;

  struct BiNode * lchild;

  struct BiNode * rchild;

}BiNode,*BiTree;

 
 
이전 순서:
 

void preOrderBiTree(BiNode * root){

	if(root == NULL)

		return;

	BiNode * node = root;

	stack<BiNode*> nodes;

	while(node || !nodes.empty()){

		while(node != NULL){

			nodes.push(node);

			printf("%d",node->data);

			node = node -> lchild;

		}

		node = nodes.top();// 

		nodes.pop();

		node = node -> rchild;

	}

}

매번 만나는 노드를 창고에 눌러 넣고 왼쪽 트리가 옮겨진 후에야 창고에서 마지막으로 방문한 노드를 꺼내 오른쪽 트리에 접근합니다.같은 층에서 두 개의 노드가 동시에 창고에 들어갈 수 없기 때문에 창고의 크기 공간은 O(h)이고 h는 두 갈래 나무 높이이다.시간적으로 각 노드는 한 번 창고에 압입되고 한 번 팝업되며 한 번 방문한다. 복잡도는 O(n)이다.
중간 순서 반복:
 
 

void midOrderBinaryTree(BiNode * root){

if(root == NULL)

return;

BiNode * node = root;

stack<BiNode*> nodes;

while(node || !nodes.empty()){

while(node != NULL){

nodes.push(node);

node = node ->lchild;

}

node = nodes.top();

printf("%d ",node ->data);

nodes.pop();

node = node ->rchild;

}

}

 
2. 창고로 직접 귀속을 시뮬레이션한다. 첫 번째 순서는 매우 간단하지만 중간 순서와 뒷 순서는 난이도가 일치하고 이 노드가 창고에 들어왔는지 여부(그 좌우 서브트리가 방문했는지 여부)를 표시하는 표지 위치가 필요하다.중차순과 후차순의 차이는 노드가 튀어나온 후에 isPushed가false라면 전자는 오른쪽 트리, 이 노드, 왼쪽 트리의 순서 입고이고 후자는 이 노드, 오른쪽 트리, 왼쪽 트리의 순서 입고이다.
이전 순서:
 

void preOrderBinaryTree(BiNode * pRoot){

    if(pRoot == NULL)

        return;

	stack<BiNode *> sData;

    sData.push(pRoot);

    BiNode * pNode = NULL;



    while(!sData.empty()){

        pNode = sData.top();

        printf("%d ",pNode -> data);

        sData.pop();

        

        if(pNode -> rchild != NULL){

            sData.push(pNode -> rchild);

        }

        if(pNode -> lchild != NULL){

            sData.push(pNode -> lchild);

        }

    }

}

매번 노드를 창고에 넣고 튀어나온 다음에 오른쪽 트리를 누르고 왼쪽 트리를 눌러서 옮겨다니는 과정에서 옮겨다니는 오른쪽 노드가 차례대로 창고에 저장되고 왼쪽 노드가 차례로 방문된다.같은 시간에 창고의 요소는 m-1개의 오른쪽 노드와 1개의 가장 왼쪽 노드이며 최고 h이다.그래서 공간도 O(h)이다.노드마다 마찬가지로 한 번, 한 번 탄창, 한 번 방문, 시간 복잡도 O(n)
노드 정의:
 
 

typedef struct BiNodeWithTag{

	int data;

	struct BiNodeWithTag * lchild;

	struct BiNodeWithTag * rchild;

	bool isPushed;

}BiNodeWithTag,*BiNodeWithTagPointer;

중간 순서 반복:
 
 

void midOrderBinaryTree(BiNodeWithTag * root){

	if(root == NULL)

		return;

	stack<BiNodeWithTag *> nodes;

	BiNodeWithTag * node = root;

	nodes.push(node);

	while(!nodes.empty()){

		node = nodes.top();

		nodes.pop();

		if(node ->isPushed){

			printf("%d ",node ->data);

			continue;

		}

		if(node ->rchild != NULL)

			nodes.push(node ->rchild);

		nodes.push(node);

		node ->isPushed = true;

		if(node ->lchild != NULL)

			nodes.push(node ->lchild);

	}

}

 
선행 순서를 비교하면 이 알고리즘은 O(n)의 로고 공간을 추가로 늘려야 한다.또한 창고 공간도 확대된다. 매번 창고에 쌓일 때마다 뿌리 노드와 좌우 노드를 눌러 넣기 때문에 창고 공간은 O(n)이다.시간의 복잡도에 있어서 각 노드가 두 번 창고에 쌓이고 하위 노드로 한 번 쌓이며 뿌리 노드로 한 번 쌓이고 탄창도 두 번 쌓인다.
다음 순서 반복:
 
 

void postOrderBinaryTree(BiNodeWithTag * root){

	if(root == NULL)

		return;

	stack<BiNodeWithTag *> nodes;

	BiNodeWithTag * node = root;

	nodes.push(node);

	while(!nodes.empty()){

		node = nodes.top();

		nodes.pop();

		if(node ->isPushed){

			printf("%d ",node ->data);

			continue;

		}

		if(node ->rchild != NULL)

			nodes.push(node ->rchild);

		if(node ->lchild != NULL)

			nodes.push(node ->lchild);

		nodes.push(node);

		node ->isPushed = true;

	}

}

참조:
 
http://blog.csdn.net/kofsky/article/details/2886453