树(2)

Jun 07, 2016 pm 03:42 PM
main Simple algorithm recursion Traverse

一:二叉树的遍历. 由于递归算法很简单,在这里就不例举了,主要看一下非递归算法(其实也就是用栈实现,因为递归本身就是一种栈) 1.先序遍历: 思想:(1)从根节点依次遍历当前节点的左子树,边遍历访问,并且压入栈 (2).再访问当前栈顶结点的右子树,然后再返回

一:二叉树的遍历.

     由于递归算法很简单,在这里就不例举了,主要看一下非递归算法(其实也就是用栈实现,因为递归本身就是一种栈)

     1.先序遍历:

          思想:(1)从根节点依次遍历当前节点的左子树,边遍历访问,并且压入栈

                   (2).再访问当前栈顶结点的右子树,然后再返回到(1)执行,直至栈空        

#define maxsize 100
typedef struct
{
    Bitree Elem[maxsize];
    int base,top;
}SqStack;

void PreOrderUnrec(Bitree t)
{
    SqStack s;
    StackInit(s);
    p=t;
    
    while (p!=null || !StackEmpty(s))
    {
        while (p!=null)             //遍历左子树
        {
            visite(p->data);
            push(s,p);
            p=p->lchild;       
        }//endwhile
        
        if (!StackEmpty(s))         //通过下一次循环中的内嵌while实现右子树遍历
        {
            p=pop(s);
            p=p->rchild;        
        }//endif                
    }//endwhile 
    
}//PreOrderUnrec
Copy after login
   2.中序遍历:

      思想:(1)从根节点遍历左子树,边遍历边入栈

               (2)弹出栈顶元素,并访问,然后访问当前栈顶的右子树,回到(1)

#define maxsize 100
typedef struct
{
    Bitree Elem[maxsize];
    int base,top;
}SqStack;

void InOrderUnrec(Bitree t)
{
    SqStack s;
    StackInit(s);
    p=t;
    while (p!=null || !StackEmpty(s))
    {
        while (p!=null)             //遍历左子树
        {
            push(s,p);
            p=p->lchild;
        }//endwhile
        
        if (!StackEmpty(s))
        {
            p=pop(s);
            visite(p->data);        //访问根结点
            p=p->rchild;            //通过下一次循环实现右子树遍历
        }//endif   
    
    }//endwhile
}//InOrderUnrec
Copy after login
 

3.后序遍历(其实还不是特清楚,代码来自百度):(需要设置一个标志量表示当前节点的右子树是否被访问)

#define maxsize 100
typedef enum{L,R} tagtype;//标记的类型,为R时表示当前结点的
typedef struct 
{
    Bitree ptr;
    tagtype tag;
}stacknode;

typedef struct
{
    stacknode Elem[maxsize];
    int base,top;
}SqStack;

void PostOrderUnrec(Bitree t)
{ 
    SqStack s;
    stacknode x;
    StackInit(s);
    p=t;
    
    do 
    {
        while (p!=null)        //遍历左子树
        {
            x.ptr = p; 
            x.tag = L;         //标记为左子树
            push(s,x);
            p=p->lchild;
        }
    
        while (!StackEmpty(s) && s.Elem[s.top].tag==R)//如果
        {
            x = pop(s);
            p = x.ptr;
            visite(p->data);   //tag为R,表示右子树访问完毕,故访问根结点       
        }
        
        if (!StackEmpty(s))
        {
            s.Elem[s.top].tag =R;     //遍历右子树
            p=s.Elem[s.top].ptr->rchild;        
        }    
  }while (!StackEmpty(s));
}//PostOrderUnrec
Copy after login


二.线索二叉树:

             含有n个结点的二叉树,一共有2n个指针域,有n+1个处于Null状态,为了使空间不浪费,可以让这些空的指针域指向二叉树各种遍历的前驱或后继结点,这样又可以方便查找每一个元素,而不必采用遍历,节省了时间

1.存储结构:

typedef enum { Link, Thread } PointerThr; 
    // Link==0:指针,Thread==1:线索
typedef struct BiThrNode{
    TElemType data;
    Struct BiThrNode *lchild, *rchild;    // 左右孩子指针
    PointerThr LTag, RTag;   // 左右标志,当LTag=Thread时,表示线索,为Link时表示指向下一结点
} BiThrNode, *BiThrTree;
Copy after login
树(2)

1)若结点有左子树,则lchild指向其左孩子;
       否则, lchild指向其直接前驱(即线索);

2).若结点有右子树,则rchild指向其右孩子;

     否则,rchild指向其后继(即线索);

例:

树(2)


2.线索二叉树的中序遍历算法:

Status IOTraver_T( BiThrTree T,Status (*Visit)(TElemType e) )
{ //T指向头结点,头结点的左链lchild指向根结点,中序遍历 //二叉线索树T的非递归算法,对每个数据元素调用函数Visit。
 p = T->lchild;  //p指向根结点     
 while (p != T) {     //空树或遍历结束时,p = = T
    while (p->LTag==Link) p = p->lchild;  
    if (!Visit(p->data)) return ERROR;  //访问其左子树为空的结点
    while (p->RTag==Thread && p->rchild!=T) 
       { p = p->rchild; Visit(p->data);  } //访问后继结点
    p = p->rchild; 
    }
 return OK;  
} // IOTraver_T
Copy after login

3.线索二叉树的生成算法:

void InThreading (BiThrTree p)//中序并线索化
 {
    if (p)
    {  
       InThreading( p->lchild );  // 左子树线索化
        if ( !p->lchild ) 
         { p->LTag=Thread; p->lchild=pre; }  // 前驱线索

        if ( !pre->rchild )
         { pre->RTag=Thread; pre->rchild=p; }  //后继线索
        pre = p;                         // 保持pre指向p的前驱
      InThreading(p->rchild);      //右子树线索化
     }
  } // InThreading
Copy after login
Status InorderThreading(BiThrTree  & Thrt, BiThrTree  T)
{ //中序遍历二叉树T,并将其中序线索化, Thrt 指向头结点.
   if ( ! (Thrt = (BiThrTree) malloc ( sizeof (BiThrnode) ) )  exit  ( OVERFLOW ) ;
   Thrt ->LTag = Link;   Thrt ->RTag = Thead;   // 建头结点
   Thrt ->rchild = Thrt ;                                       //右指针回指
   if ( !T ) Thrt ->lchild = Thrt ;    // 若二叉树空,则左指针回指
   else {
             Thrt ->lchild = T;     pre = Thrt; //将头结点与树相连
             <strong>InThreading(T);  </strong>        // 中序遍历进行中序线索化,调用上面的函数
             pre ->rchild = Thrt;   
             pre ->RTag = Thread;     //最后一个结点线索化
             Thrt ->rchild = pre;
            }
    return OK;
 } // InOrderThreading
Copy after login







Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial
1664
14
PHP Tutorial
1267
29
C# Tutorial
1239
24
Recursive implementation of C++ functions: Is there a limit to recursion depth? Recursive implementation of C++ functions: Is there a limit to recursion depth? Apr 23, 2024 am 09:30 AM

The recursion depth of C++ functions is limited, and exceeding this limit will result in a stack overflow error. The limit value varies between systems and compilers, but is usually between 1,000 and 10,000. Solutions include: 1. Tail recursion optimization; 2. Tail call; 3. Iterative implementation.

Do C++ lambda expressions support recursion? Do C++ lambda expressions support recursion? Apr 17, 2024 pm 09:06 PM

Yes, C++ Lambda expressions can support recursion by using std::function: Use std::function to capture a reference to a Lambda expression. With a captured reference, a Lambda expression can call itself recursively.

Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Implementing Machine Learning Algorithms in C++: Common Challenges and Solutions Jun 03, 2024 pm 01:25 PM

Common challenges faced by machine learning algorithms in C++ include memory management, multi-threading, performance optimization, and maintainability. Solutions include using smart pointers, modern threading libraries, SIMD instructions and third-party libraries, as well as following coding style guidelines and using automation tools. Practical cases show how to use the Eigen library to implement linear regression algorithms, effectively manage memory and use high-performance matrix operations.

Recursive implementation of C++ functions: Comparative analysis of recursive and non-recursive algorithms? Recursive implementation of C++ functions: Comparative analysis of recursive and non-recursive algorithms? Apr 22, 2024 pm 03:18 PM

The recursive algorithm solves structured problems through function self-calling. The advantage is that it is simple and easy to understand, but the disadvantage is that it is less efficient and may cause stack overflow. The non-recursive algorithm avoids recursion by explicitly managing the stack data structure. The advantage is that it is more efficient and avoids the stack. Overflow, the disadvantage is that the code may be more complex. The choice of recursive or non-recursive depends on the problem and the specific constraints of the implementation.

Improved detection algorithm: for target detection in high-resolution optical remote sensing images Improved detection algorithm: for target detection in high-resolution optical remote sensing images Jun 06, 2024 pm 12:33 PM

01 Outlook Summary Currently, it is difficult to achieve an appropriate balance between detection efficiency and detection results. We have developed an enhanced YOLOv5 algorithm for target detection in high-resolution optical remote sensing images, using multi-layer feature pyramids, multi-detection head strategies and hybrid attention modules to improve the effect of the target detection network in optical remote sensing images. According to the SIMD data set, the mAP of the new algorithm is 2.2% better than YOLOv5 and 8.48% better than YOLOX, achieving a better balance between detection results and speed. 02 Background & Motivation With the rapid development of remote sensing technology, high-resolution optical remote sensing images have been used to describe many objects on the earth’s surface, including aircraft, cars, buildings, etc. Object detection in the interpretation of remote sensing images

C++ Recursion Advanced: Understanding Tail Recursion Optimization and Its Application C++ Recursion Advanced: Understanding Tail Recursion Optimization and Its Application Apr 30, 2024 am 10:45 AM

Tail recursion optimization (TRO) improves the efficiency of certain recursive calls. It converts tail-recursive calls into jump instructions and saves the context state in registers instead of on the stack, thereby eliminating extra calls and return operations to the stack and improving algorithm efficiency. Using TRO, we can optimize tail recursive functions (such as factorial calculations). By replacing the tail recursive call with a goto statement, the compiler will convert the goto jump into TRO and optimize the execution of the recursive algorithm.

Application of algorithms in the construction of 58 portrait platform Application of algorithms in the construction of 58 portrait platform May 09, 2024 am 09:01 AM

1. Background of the Construction of 58 Portraits Platform First of all, I would like to share with you the background of the construction of the 58 Portrait Platform. 1. The traditional thinking of the traditional profiling platform is no longer enough. Building a user profiling platform relies on data warehouse modeling capabilities to integrate data from multiple business lines to build accurate user portraits; it also requires data mining to understand user behavior, interests and needs, and provide algorithms. side capabilities; finally, it also needs to have data platform capabilities to efficiently store, query and share user profile data and provide profile services. The main difference between a self-built business profiling platform and a middle-office profiling platform is that the self-built profiling platform serves a single business line and can be customized on demand; the mid-office platform serves multiple business lines, has complex modeling, and provides more general capabilities. 2.58 User portraits of the background of Zhongtai portrait construction

Detailed explanation of C++ function recursion: application of recursion in string processing Detailed explanation of C++ function recursion: application of recursion in string processing Apr 30, 2024 am 10:30 AM

A recursive function is a technique that calls itself repeatedly to solve a problem in string processing. It requires a termination condition to prevent infinite recursion. Recursion is widely used in operations such as string reversal and palindrome checking.

See all articles