찾다
일반적인 문제이진 트리 순회 알고리즘

이진 트리 순회 알고리즘

Jun 20, 2019 am 11:51 AM
이진 트리연산횡단

이진 트리 순회 알고리즘

A. 이진 트리 순회

1. 이진 트리의 선주문 순회:

(1) 이진 트리가 비어 있으면 작업이 수행되지 않습니다. 빈 상태로 반환됩니다.
(2) 루트 노드를 방문합니다.
(3) 왼쪽 하위 트리의 선주문 순회.
(4) 오른쪽 하위 트리의 선주문 순회.

a. 이진 트리의 선주문 순회를 위한 재귀 알고리즘:

   void PreOrderTraverse(BiTree BT)
   {     if(BT)
     {
        printf("%c",BT->data);              //访问根结点
        PreOrderTraverse(BT->lchild);       //前序遍历左子树
        PreOrderTraverse(BT->rchild);       //前序遍历右子树     }
   }

b. 각 노드의 오른쪽 하위 트리:

(1) 트리가 비어 있으면 포인터 p가 루트 노드를 가리키고 p는 현재 노드 포인터입니다.
(2) 먼저 현재 노드 p를 방문하고 p를 스택 S에 푸시합니다.
(3) p가 왼쪽 자식을 가리키도록 합니다.
(4) p가 빌 때까지 (2)와 (3) 단계를 반복합니다.
(5) 스택 S에서 최상위 요소를 팝하고 p를 이 요소의 오른쪽 자식으로 지정합니다.
(6) p가 비어 있고 스택 S도 비어 있을 때까지 (2)~(5) 단계를 반복합니다.
(7) 순회가 끝났습니다.
        스택을 사용하는 선주문 탐색을 위한 비재귀 알고리즘:

      void PreOrderNoRec(BiTree BT)
      {
        stack S;
        BiTree p=BT->root;        while((NULL!=p)||!StackEmpty(S))
        {          if(NULL!=p)
          {
            printf("%c",p->data);
            Push(S,p);
            p=p->lchild;
          }          else
          {
            p=Top(S);
            Pop(S);
            p=p->rchild;
          }
        }
      }
 

c. 이진 연결 목록 저장소를 사용하는 이진 트리의 선주문 탐색을 위한 비재귀 알고리즘:

    void PreOrder(pBinTreeNode pbnode)
    {
      pBinTreeNode stack[100];
      pBinTreeNode p;      int top;
      top=0;
      p=pbnode;      do
      {        while(p!=NULL)
        {
          printf("%d\n",p->data);      //访问结点p
          top=top+1;
          stack[top]=p;
          p=p->llink;                  //继续搜索结点p的左子树        }        if(top!=0)
        {
          p=stack[top];
          top=top-1;
          p=p->rlink;                  //继续搜索结点p的右子树        }
      }while((top!=0)||(p!=NULL));
    }

2. 중간 이진 트리의 순차적 순회:

(1) 이진 트리가 비어 있으면 무작동 작업이며 아무것도 반환하지 않습니다.
(2) 왼쪽 하위 트리를 순서대로 순회합니다.
(3) 루트 노드를 방문합니다.
(4) 오른쪽 하위 트리를 순서대로 순회합니다.
a. 이진 트리의 순차 순회를 위한 재귀 알고리즘:
    void InOrderTraverse(BiTree BT)
    {      if(BT)
      {
         InOrderTraverse(BT->lchild);        //中序遍历左子树
         printf("%c",BT->data);              //访问根结点
         InOrderTraverse(BT->rchild);        //中序遍历右子树      }
    }

b.

( 1) 트리가 비어 있으면 포인터 p가 루트 노드를 가리키고 p는 현재 노드 포인터입니다.
(2) p를 스택 S에 밀어넣고 p가 왼쪽 자식을 가리키도록 만듭니다.
(3) p가 빌 때까지 (2)단계를 반복합니다.
(4) 스택 S에서 최상위 요소를 팝하고 p가 이 요소를 가리킵니다.
(5) 현재 노드 p를 방문하고 p가 오른쪽 자식을 가리킵니다.
(6) p가 비어 있고 스택 S도 비어 있을 때까지 (2)~(5) 단계를 반복합니다.
(7) 순회가 끝났습니다.
스택을 사용한 순차 순회를 위한 비순차 알고리즘:
     void IneOrderNoRec(BiTree BT)
     {
       stack S;
       BiTree p=BT->root;       while((NULL!=p)||!StackEmpty(S))
       {         if(NULL!=p)
         {
           Push(S,p);
           p=p->lchild;
         }         else
         {
           p=Top(S);
           Pop(S);
           printf("%c",p->data);
           p=p->rchild;
         }
       }
     }

c. 이진 연결 목록 저장소를 사용하여 이진 트리의 순차 순회를 위한 비순차 알고리즘:

    void InOrder(pBinTreeNode pbnode)
    {
         pBinTreeNode stack[100];
         pBinTreeNode p;         int top;
         top=0;
         p=pbnode;         do
         {           while(p!=NULL)
           {
             top=top+1;
             stack[top]=p;                //结点p进栈
             p=p->llink;                  //继续搜索结点p的左子树           }           if(top!=0)
           {
             p=stack[top];                //结点p出栈
             top=top-1;
             printf("%d\n",p->data);      //访问结点p
             p=p->rlink;                  //继续搜索结点p的右子树           }
         }while((top!=0)||(p!=NULL));
    }
3.이진 트리의 순차적 순회 후:

(1) 이진 트리가 비어 있으면 아무 작업도 하지 않으며 아무것도 반환하지 않습니다.
(2) 왼쪽 하위 트리의 사후 순회.
(3) 오른쪽 하위 트리의 사후 순회.
(4) 루트 노드를 방문합니다.
     a.二叉树后序遍历的递归算法:
     void PostOrderTraverse(BiTree BT)
     {       if(BT)
       {
          PostOrderTraverse(BT->lchild);        //后序遍历左子树
          PostOrderTraverse(BT->rchild);        //后序遍历右子树
          printf("%c",BT->data);                //访问根结点       }
     }

     b.使用栈存储的二叉树后序遍历的非递归算法:

      算法思想:首先扫描根结点的所有左结点并入栈,然后出栈一个结点,扫描该结点的右结点并入栈,再扫描该右结点的所有左结点并入栈,当一个结点的左、右子树均被访问后再访问该结点。因为在递归算法中,左子树和右子树都进行了返回,因此为了区分这两种情况,还需要设置一个标识栈tag,当tag的栈顶元素为0时表示从左子树返回,为1表示从右子树返回。
       (1)当树为空时,将指针p指向根结点,p为当前结点指针。
       (2)将p压入栈S中,0压入栈tag中,并令p指向其左孩子。
       (3)重复执行步骤(2),直到p为空。
       (4)如果tag栈中的栈顶元素为1,跳至步骤(6)。
       (5)如果tag栈中的栈顶元素为0,跳至步骤(7)。
       (6)将栈S的栈顶元素弹出,并访问此结点,跳至步骤(8)。
       (7)将p指向栈S的栈顶元素的右孩子。
       (8)重复执行步骤(2)~(7),直到p为空并且栈S也为空。
       (9)遍历结束。
        使用栈的后序遍历非递归算法:

       void PostOrderNoRec(BiTree BT)
       {
         stack S;
         stack tag;
         BiTree p=BT->root;         while((NULL!=p)||!StackEmpty(S))
         {           while(NULL!=p)
           {
             Push(S,p);
             Push(tag,0);
             p=p->lchild;
           }           if(!StackEmpty(S))
           {             if(Pop(tag)==1)
             {
               p=Top(S);
               Pop(S);
               printf("%c",p->data);
               Pop(tag);    //栈tag要与栈S同步             }             else
             {
               p=Top(S);               if(!StackEmpty(S))
               {
                 p=p->rchild;
                 Pop(tag);
                 Push(tag,1);
               }
             }
           }
         }
       }

     c.使用二叉链表存储的二叉树后序遍历非递归算法:

     void PosOrder(pBinTreeNode pbnode)
     {
          pBinTreeNode stack[100];       //结点的指针栈          int count[100];                //记录结点进栈次数的数组          pBinTreeNode p;          int top;
          top=0;
          p=pbnode;          do
          {            while(p!=NULL)
            {
              top=top+1;
              stack[top]=p;                //结点p首次进栈
              count[top]=0;
              p=p->llink;                  //继续搜索结点p的左子树            }
            p=stack[top];                  //结点p出栈
            top=top-1;            if(count[top+1]==0)
            {
              top=top+1;
              stack[top]=p;                //结点p首次进栈
              count[top]=1;
              p=p->rlink;                  //继续搜索结点p的右子树            }            else
            {
              printf("%d\n",p->data);      //访问结点p
              p=NULL;
            }
          }while((top>0));
     }

 B 线索化二叉树:

       线索化二叉树的结点结构图:
                 이진 트리 순회 알고리즘
     线索化二叉树的结点类型说明:
      typedef struct node
      {
        DataType data;        struct node *lchild, *rchild;       //左、右孩子指针        int ltag, rtag;                     //左、右线索
      }TBinTNode;         //结点类型
      typedef TBinTNode *TBinTree;
     在线索化二叉树中,一个结点是叶子结点的充分必要条件是其左、右标志均为1.
    中序线索化二叉树及其对应的线索链表如下图:
            이진 트리 순회 알고리즘

   (1)中序线索化二叉树的算法:

   void InOrderThreading(TBinTree p)
      {        if(p)
        {
          InOrderThreading(p->lchild);   //左子树线索化          if(p->lchild)
            p->ltag=0;          else
            p->ltag=1;          if(p->rchild)
            p->rtag=0;          else
            p->rtag=1;          if(*(pre))      //若*p的前驱*pre存在          {            if(pre->rtag==1)
              pre->rchild=p;            if(p->ltag==1)
              p->lchild=pre;
          }
          pre=p;                         //另pre是下一访问结点的中序前驱
          InOrderThreading(p->rchild);   //右子树线索化        }
      }

   (2)在中序线索化二叉树下,结点p的后继结点有以下两种情况:

      ①结点p的右子树为空,那么p的右孩子指针域为右线索,直接指向结点p的后继结点。
     ②结点p的右子树不为空,那么根据中序遍历算法,p的后继必是其右子树中第1个遍历到的结点。
     中序线索化二叉树求后继结点的算法:
 TBinTNode *InOrderSuc(BiThrTree p)
    {
       TBinTNode *q;       if(p->rtag==1)   //第①情况         return p->rchild;       else            //第②情况       {
         q=p->rchild;         while(q->ltag==0)
           q=q->lchild;         return q;
       }
    }

     中序线索化二叉树求前驱结点的算法:

TBinTNode *InOrderPre(BiThrTree p)
    {
       TBinTNode *q;       if(p->ltag==1)         return p->lchild;       else
       {
         q=p->lchild;         //从*p的左孩子开始查找         while(q->rtag==0)
           q=q->rchild;         return q;
       }
    }

   (3)遍历中序线索化二叉树的算法

void TraversInOrderThrTree(BiThrTree p)
    {      if(p)
      {        while(p->ltag==0)
          p=p->lchild;        while(p)
        {
          printf("%c",p->data);
          p=InOrderSuc(p);
        }
      }
    }

FAQ와 관련된 더 많은 기술 기사를 보려면 FAQs 컬럼을 방문하여 자세히 알아보세요!

위 내용은 이진 트리 순회 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.
Deepseek 웹 버전 공식 입구Deepseek 웹 버전 공식 입구Mar 12, 2025 pm 01:42 PM

국내 AI Dark Horse Deepseek은 글로벌 AI 산업에 충격을 주면서 강력하게 증가했습니다! 1 년 반 동안 단지 설립 된이 중국 인공 지능 회사는 무료 및 오픈 소스 모형 인 DeepSeek-V3 및 DeepSeek-R1에 대해 글로벌 사용자로부터 광범위한 칭찬을 받았습니다. DeepSeek-R1은 이제 OpenAIO1의 공식 버전과 비교할 수있는 성능으로 완전히 출시되었습니다! 웹 페이지, 앱 및 API 인터페이스에서 강력한 기능을 경험할 수 있습니다. 다운로드 방법 : iOS 및 Android 시스템을 지원하면 사용자가 App Store를 통해 다운로드 할 수 있습니다. Deepseek 웹 버전 공식 입구 : HT

DeepSeek의 바쁜 서버 문제를 해결하는 방법DeepSeek의 바쁜 서버 문제를 해결하는 방법Mar 12, 2025 pm 01:39 PM

DeepSeek : 서버와 혼잡 한 인기있는 AI를 처리하는 방법은 무엇입니까? 2025 년 핫 AI로서 DeepSeek은 무료이며 오픈 소스이며 OpenAIO1의 공식 버전과 비교할 수있는 성능을 가지고 있으며, 이는 인기를 보여줍니다. 그러나 높은 동시성은 서버 바쁜 문제를 가져옵니다. 이 기사는 이유를 분석하고 대처 전략을 제공합니다. DeepSeek 웹 버전 입구 : https://www.deepseek.com/deepseek 서버 바쁜 이유 : 높은 동시 액세스 : DeepSeek의 무료 및 강력한 기능은 동시에 많은 사용자를 유치하여 과도한 서버로드를 초래합니다. 사이버 공격 : DeepSeek은 미국 금융 산업에 영향을 미친다 고보고되었습니다.

심층적 인 검색 DeepSeek 공식 웹 사이트 입학심층적 인 검색 DeepSeek 공식 웹 사이트 입학Mar 12, 2025 pm 01:33 PM

2025 년 초, 국내 AI "Deepseek"은 놀라운 데뷔를했습니다! 이 무료 및 오픈 소스 AI 모델은 OpenAI의 O1의 공식 버전과 비교할 수있는 성능을 가지고 있으며 웹 측, 앱 및 API에서 완전히 출시되어 iOS, Android 및 웹 버전의 다중 터미널 사용을 지원합니다. DeepSeek 공식 웹 사이트 및 사용 지침의 심도있는 검색 : 공식 웹 사이트 주소 : https://www.deepseek.com/using 웹 버전 : 위의 링크를 클릭하여 DeepSeek 공식 웹 사이트를 입력하십시오. 홈페이지에서 "대화 시작"버튼을 클릭하십시오. 먼저 사용하려면 휴대폰 확인 코드와 함께 로그인해야합니다. 로그인 한 후 대화 인터페이스를 입력 할 수 있습니다. DeepSeek은 강력하고 코드를 작성하고 파일을 읽고 코드를 만들 수 있습니다.

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

SecList

SecList

SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.

Dreamweaver Mac版

Dreamweaver Mac版

시각적 웹 개발 도구

MinGW - Windows용 미니멀리스트 GNU

MinGW - Windows용 미니멀리스트 GNU

이 프로젝트는 osdn.net/projects/mingw로 마이그레이션되는 중입니다. 계속해서 그곳에서 우리를 팔로우할 수 있습니다. MinGW: GCC(GNU Compiler Collection)의 기본 Windows 포트로, 기본 Windows 애플리케이션을 구축하기 위한 무료 배포 가능 가져오기 라이브러리 및 헤더 파일로 C99 기능을 지원하는 MSVC 런타임에 대한 확장이 포함되어 있습니다. 모든 MinGW 소프트웨어는 64비트 Windows 플랫폼에서 실행될 수 있습니다.

VSCode Windows 64비트 다운로드

VSCode Windows 64비트 다운로드

Microsoft에서 출시한 강력한 무료 IDE 편집기

에디트플러스 중국어 크랙 버전

에디트플러스 중국어 크랙 버전

작은 크기, 구문 강조, 코드 프롬프트 기능을 지원하지 않음