数据结构(十三)树的遍历

妖狐艹你老母 2022-05-31 10:39 196阅读 0赞

### **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;
        }
    }