데이터 구조 (13) 트 리 의 옮 겨 다 니 기

1. 앞 순 서 를 편력 하 다.
먼저 자신 을 방문 한 다음 에 왼쪽 트 리 를 방문 한 다음 에 오른쪽 트 리 를 방문 합 니 다.
(1) 귀속 방법

function(node*p)
{
    print p.value
    function(p->left);
    function(p->right);
}

(2) 비 귀속 방법

while(p!=null&&!stack.empty())
{
	while(p!=null)
    {
        print p.value;
        stack.push(p);
        p=p.left;
    }
    if(!stack.empty())
    {
        temp=stack.pop();
        p=temp.right;
      }
}

2. 중간 순서 로 옮 겨 다 니 기
먼저 왼쪽 트 리 에 접근 한 다음 자신 에 게 접근 한 다음 오른쪽 트 리 에 접근 합 니 다.
(1) 귀속 방법

function(node*p)
{
    function(p->left);
    print p.value
    function(p->right);
}

(2) 비 귀속 방법

while(p!=null&&!stack.empty())
{
	while(p!=null)
        {
            stack.push(p);
            p=p.left;
        }
    if(!stack.empty())
    {
        temp=stack.pop();
        print temp.value;    
        p=temp.right;
      }
}

3. 후 순 옮 겨 다 니 기
먼저 왼쪽 나무, 뒤에 오른쪽 나무, 뒤에 자신.
(1) 귀속 방법

function(node*p)
{
    function(p->left);
    function(p->right);
    print p.value
}

(2) 비 귀속 방법

while(p!=null&&!stack.empty())
{
    while(p!=null)
    {
        stack.push(p);
        p=p.left;
    }
    if(!stack.empty())
    {
        temp=statck.first();
        if(temp.isfirst==false)
        {
             temp.isfirst=true;
             p=temp.right
        }
        else{
            temp=stack.pop();
            print temp.value
        }
      }
}

4. 넓이 우선
범위 우선 순 위 는 주로 대열 로 이 루어 집 니 다. 매번 대열 의 첫 번 째 요 소 를 꺼 내 고 먼저 나 갑 니 다.

function(node*p)
{
    Queue.insert(p);
    While(!queue.empty())
    {
        p=queue.pop();
        queue.push(p->left);
        queue.push(p->right);
        print p.value;

    }
}

5. 깊이 우선
깊이 우선 옮 겨 다 니 는 것 은 주로 스 택 으로 이 루어 지 며 매번 스 택 꼭대기 에서 꺼 냅 니 다.

function(node*p)
{
    Stack.insert(p);
    While(!Stack.empty())
    {
        p=Stack.pop();
        Stack.push(p->left);
        Stack.push(p->right);
        print p.value;
    }
}