精华内容
下载资源
问答
  • 树的四种遍历方式

    2018-08-06 14:23:20
    一共有四种遍历方式,包括前序遍历,中序遍历,后序遍历和层序遍历。 前中后三种方式代码是相似,而层序遍历却不同。 前序遍历是第一次遇到这个节点输出,中序遍历是第二次遇到这个节点输出,后序遍历是...

    树一共有四种遍历方式,包括前序遍历,中序遍历,后序遍历和层序遍历。
    前中后三种方式的代码是相似的,而层序遍历的却不同。
    前序遍历是第一次遇到这个节点输出,中序遍历是第二次遇到这个节点输出,后序遍历是第三次遇到这个节点输出。
    层序遍历是通过队列的方式遍历。

    //前序遍历
    void preordertraversal(bintree t)
    {
    	if(t)
    	{
    		printf("%d ",t->data );
    		preordertraversal(t->left );
    		preordertraversal(t->right );
    	}
    }
    
    //中序遍历
    void inordertraversal( bintree t )
    {
    	if(t)
    	{	
    			inordertraversal(t->left );
    			printf("%d ",t->data );
    			inordertraversal(t->right );
    			
    	}
    }
    
    //后序遍历
    void postordertraversal(bintree t)
    {
    	if(t)
    	{
    		postordertraversal(t->left );
    		postordertraversal(t->right );
    		printf("%d ",t->data);
    	}
    }
    
    //层序遍历
    void levelordertraversal( bintree t )
    {
    	position queue[200];
    	bintree p;
    	int head = 0 ;
    	int tail = 0 ;
    	if(!t)
    		return ;
    	if(t)
    	{
    		queue[tail++] = t;
    		while(head!=tail)
    		{
    			p = queue[head++];
    			printf("%d ",p->data );
    			if(p->left != NULL)
    				queue[tail++] = p->left ;
    			if(p->right != NULL)
    				queue[tail++] = p->right ;
    		}
    	}
    }
    

    完整代码(用了插入操作):

    #include<stdio.h>
    #include<stdlib.h>
    typedef struct node* position;
    typedef position bintree;
    struct node{
    	
    	int data;
    	bintree left;
    	bintree right;
    	
    };
    
    
    void levelordertraversal( bintree t )
    {
    	position queue[200];
    	bintree p;
    	int head = 0 ;
    	int tail = 0 ;
    	if(!t)
    		return ;
    	if(t)
    	{
    		queue[tail++] = t;
    		while(head!=tail)
    		{
    			p = queue[head++];
    			printf("%d ",p->data );
    			if(p->left != NULL)
    				queue[tail++] = p->left ;
    			if(p->right != NULL)
    				queue[tail++] = p->right ;
    		}
    	}
    }
     
    void preordertraversal(bintree t)
    {
    	if(t)
    	{
    		printf("%d ",t->data );
    		preordertraversal(t->left );
    		preordertraversal(t->right );
    	}
    }
    
    
    void inordertraversal( bintree t )
    {
    	if(t)
    	{	
    			inordertraversal(t->left );
    			printf("%d ",t->data );
    			inordertraversal(t->right );
    			
    	}
    }
    
    void postordertraversal(bintree t)
    {
    	if(t)
    	{
    		postordertraversal(t->left );
    		postordertraversal(t->right );
    		printf("%d ",t->data);
    	}
    }
    
    void levelordertraversal( bintree t )
    {
    	position queue[200];
    	int head = 0 ;
    	int tail = 0 ;
    	if(!t)
    		return ;
    	if(t)
    	{
    		queue[tail++] = t;
    		while(head!=tail)
    		{
    			position t = queue[head++];
    			printf("%d ",t->data );
    			if(t->left != NULL)
    				queue[tail++] = t->left ;
    			if(t->right != NULL)
    				queue[tail++] = t->right ;
    		}
    	}
    }
    
    int main()
    {
    		int n;
    		bintree t = NULL ;//记得设空节点!
    		scanf("%d",&n);
    		int num;
    		for(int i = 0; i < n; i++ )
    		{
    			scanf("%d",&num);
    			t = insert(t,num);//注意!
    		 } 
    		 
    		printf("Inorder:");    inordertraversal(t);    printf("\n");
            printf("Preorder:");   preordertraversal(t);   printf("\n");
       		printf("Postorder:");  postordertraversal(t);  printf("\n");
       		printf("Levelorder:"); levelordertraversal(t); printf("\n");
    }
     
    
    展开全文
  • 树的四种遍历方式c++

    千次阅读 2019-03-16 17:43:25
    树的常用的遍历方式四种,分别为前序遍历,中序遍历,后续遍历和层次遍历,下面的代码依次实现了它们的递归以及非递归方法。 // tree.cpp : 此文件包含 &quot;main&quot; 函数。程序执行将在此处开始并...

    树常用的遍历方式有四种,分别为前序遍历,中序遍历,后序遍历和层次遍历,下面的代码依次实现了它们的递归以及非递归方法。

    // tree.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include "pch.h"
    #include <iostream>
    #include<stack>
    #include<queue>
    
    using namespace std;
    
    typedef struct Node
    {
    	char data;
    	struct Node *lchild, *rchild;
    }Node;
    
    //通过先序的方式创建树,#表示空节点
    /*
                       A
                   B      C
                 D   E   F  #
               #  # # # #  # 
    创建上面的树应输入应为  ABD##E##CF###
    前序遍历:ABDECF
    中序遍历:DBEAFC
    后序遍历:DEBFCA
    层次遍历:ABCDEF
    */
    void creatTree(Node* &root)
    {
    	char data;
    	cin >> data;
    	if (data == '#')
    		root = NULL;
    	else
    	{
    		root = new Node;
    		root->data = data;
    		creatTree(root->lchild);
    		creatTree(root->rchild);
    	}
    
    }
    
    
    //打印一个节点的数据
    void visit(Node* node)
    {
    	if(node!=NULL)
    		cout << node->data;
    }
    
    //递归-前序遍历,先访问跟节点,然后访问左节点,最后访问右节点,每一个节点都要准守这样的规则
    void preTraversal(Node* root)
    {
    	//访问跟节点
    	if (root != NULL)
    	{
    		visit(root);
    		preTraversal(root->lchild);
    		preTraversal(root->rchild);
    	}
    
    }
    
    //递归-中序遍历,先访问跟左节点,然后访问中节点,最后访问右节点,每一个节点都要准守这样的规则
    void midTraversal(Node* root)
    {
    	if (root != NULL)
    	{
    		midTraversal(root->lchild);
    		visit(root);
    		midTraversal(root->rchild);
    	}
    }
    
    //递归-后序遍历,先访问左节点,然后访问右节点,最后访问根节点,每一个节点都要准守这样的规则
    void postTraversal(Node* root)
    {
    	if (root != NULL)
    	{
    		postTraversal(root->lchild);
    		postTraversal(root->rchild);
    		visit(root);
    	}
    }
    
    //非递归-前序遍历
    /*
    思想:用栈来实现。首先访问根节点,然后将根节点入栈,接着访问当前节点的左节点,然后入栈,当左节点访问完后,
    出栈,并依次访问右节点
    */
    void un_preTraversal(Node* root)
    {
    	stack<Node*> stack;
    	//当前节点
    	Node* p = root;
    	while (p != NULL || stack.size() != 0)
    	{
    		if (p != NULL)
    		{
    			visit(p);//访问p之前一定要保证p不为空
    			stack.push(p);
    			p = p->lchild;
    		}
    		else
    		{
    			p = stack.top();
    			stack.pop();
    			p = p->rchild;
    		}
    
    	}
    
    }
    
    //非递归-中序遍历
    /*
    思想:用栈来实现。从根节点开始依次遍历当前节点的左节点,并依次入栈,当左节点遍历完成后,获取
    栈顶元素并出栈,然后访问该节点,并依次遍历其右节点
    */
    void un_midTraversal(Node* root)
    {
    	stack<Node*> stack;
    	Node* p = root;
    	while (p != NULL || stack.size() != 0)
    	{
    		if (p != NULL)
    		{
    			stack.push(p);
    			p = p->lchild;
    		}
    		else
    		{
    			p = stack.top();
    			stack.pop();
    			visit(p);
    			p = p->rchild;
    		}
    	}
    }
    
    //非递归-后序遍历
    /*
    思想:用栈来实现。先根节点开始依次遍历左节点,已经遍历过了的标记为'l',然后依次遍历右节点,遍历过的标记为'r',
    只有当标记为'r'时才能访问该节点。
    */
    //定义一个有标记的结构体
    typedef struct TNode
    {
    	Node* node;//树的节点的指针
    	char tag;//标记
    }TNode;
    
    
    void un_postTraversal(Node* root)
    {
    	//当前节点
    	Node *p = root;
    	TNode *n;
    	stack<TNode*> stack;
    	while (p != NULL || stack.empty() == false)
    	{
    		//遍历左节点并标记
    		while (p != NULL)
    		{
    			n = new TNode;
    			n->node = p;
    			n->tag = 'l';
    			stack.push(n);
    			p = p->lchild;
    		}
    
    		//出栈
    		n = stack.top();
    		stack.pop();
    		
    		//遍历当前节点的右子树
    		if (n->tag == 'l')
    		{
    			n->tag = 'r';
    			//再次入栈
    			stack.push(n);
    			//此时p==NULL,一定要给p当前的节点
    			p = n->node;
    			p = p->rchild;
    		}
    		//左右子树遍历完成后访问该节点
    		else
    		{
    			visit(n->node);
    			//并把p置空防止
    			p = NULL;
    		}
    	}
    }
    
    //树的层次遍历
    //思想:使用队列queue。先将根节点入队列,循环判断当前队列不为空时,将头元素出队列并访问头元素,然后在将它的左节点和右节点入队列
    void levelTraversal(Node* root)
    {
    	queue<Node*> q;
    	Node* p = root;
    	q.push(p);
    	while (q.empty() == false)
    	{
    		p = q.front();
    		q.pop();
    		visit(p);
    		if (p->lchild != NULL)
    			q.push(p->lchild);
    		if (p->rchild != NULL)
    			q.push(p->rchild);
    	}
    }
    
    int main()
    {
    	//创建上面的树应输入应为  ABD##E##CF###
    
    	Node* root;
    	creatTree(root);
    	cout << "递归-前序遍历:";
    	preTraversal(root);
    	cout << endl;
    
    	cout << "递归-中序遍历:";
    	midTraversal(root);
    	cout << endl;
    
    	cout << "递归-后序遍历:";
    	postTraversal(root);
    	cout << endl;
    
    	cout << "非递归-前序遍历:";
    	un_preTraversal(root);
    	cout << endl;
    
    	cout << "非递归-中序遍历:";
    	un_midTraversal(root);
    	cout << endl;
    
    	cout << "非递归-后序遍历:";
    	un_postTraversal(root);
    	cout << endl;
    
    	cout << "层次遍历:";
    	levelTraversal(root);
    	cout << endl;
    }
    
    
    
    
    展开全文
  • 基本数据结构算法:树的四种遍历方式,含有递归和非递归版本,非常喜欢考

    这也是暑期实习的准备之一,最近进入了算法题的整理阶段,感觉提升了很多,后期还会更新的。
    这个只含有代码和必要的解释,如果你看不懂的话,建议先把数据结构课本看一下~

    后序遍历(⚠️非递归的trick)

    递归版

    import java.util.*;
    public class Solution {
        ArrayList<Integer> res = new ArrayList<Integer>();
        public ArrayList<Integer> postorderTraversal(TreeNode root) {
            if(root!=null){
                postorderTraversal(root.left);
                postorderTraversal(root.right);
                res.add(root.val);
            }
            return res;
        }
    }
    

    利用栈

    由于先序遍历的顺序是(根,左,右),后序遍历的顺序是(左,右,根),我们可以考虑这样一种方法:将先序遍历改为(根,右,左),然后在将其逆置即可,逆置我们采取的方法是 add(0,num),即可实现逆置。

    import java.util.*;
    public class Solution {
        ArrayList<Integer> res = new ArrayList<Integer>();
        public ArrayList<Integer> postorderTraversal(TreeNode root) {
            if(root==null)
                return res;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            
            while(!stack.isEmpty()){
                TreeNode tmp = stack.pop();
                res.add(0,tmp.val);
                if(tmp.left!=null)
                    stack.push(tmp.left);
                if(tmp.right!=null)
                    stack.push(tmp.right);
            }
            return res;
        }
    }
    

    先序遍历

    递归

    import java.util.*;
    public class Solution {
        ArrayList<Integer> res = new ArrayList<Integer>();
        public ArrayList<Integer> preorderTraversal(TreeNode root) {
            if(root!=null){
                res.add(root.val);
                preorderTraversal(root.left);
                preorderTraversal(root.right);
            }
            return res;
        }
    }
    

    借助栈实现非递归写法

    import java.util.*;
    public class Solution {
        public ArrayList<Integer> preorderTraversal(TreeNode root) {
            ArrayList<Integer> res = new ArrayList<Integer>();
            if(root==null)
                return res;
            Stack<TreeNode> stack = new Stack<TreeNode>();
            stack.push(root);
            while(!stack.isEmpty()){
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                if(tmp.right!=null)
                    stack.push(tmp.right);
                if(tmp.left!=null)
                    stack.push(tmp.left);
            }
            return res;
        }
    }
    

    中序遍历

    递归

    import java.util.*;
    public class Solution {
        ArrayList<Integer> res = new ArrayList<Integer>();
        public ArrayList<Integer> inorderTraversal(TreeNode root) {
            if(root!=null){
                inorderTraversal(root.left);
                res.add(root.val);
                inorderTraversal(root.right);
                
            }
            return res;
        }
    }
    

    使用栈

    import java.util.*;
    public class Solution {
        ArrayList<Integer> res = new ArrayList<Integer>();
        public ArrayList<Integer> inorderTraversal(TreeNode root) {
            Stack<TreeNode> stack = new Stack<TreeNode>();
            TreeNode node = root;
            while(node!=null){
                stack.push(node);
                node = node.left;
            }
            while(!stack.isEmpty()){
                TreeNode tmp = stack.pop();
                res.add(tmp.val);
                if(tmp.right!=null){
                    TreeNode n = tmp.right;
                    while(n!=null){
                        stack.push(n);
                        n = n.left;
                    }
                }
            }
            return res;
        }
    }
    

    层次遍历

    import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class Solution {
        public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
            ArrayList<Integer> res = new ArrayList<Integer>();
            if(root==null) return res;
            LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
            queue.add(root);
            while(!queue.isEmpty()) {
                TreeNode node = queue.poll();
                res.add(node.val);
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }
            
            return res;
        }
    }
    
    展开全文
  • #前序遍历 def pre_order(tree): if tree==None: return print tree.data pre_order(tree.left) pre_order(tree.right) #中序遍历 def mid_order(tree): if tree==None: return mid_order(tree.left) ...

    class node(object):
    def init(self,data=None,left=None,right=None):
    self.data=data
    self.left=left
    self.right=right

    #深度
    def depth(tree):
        if tree==None:
            return 0
        left,right=depth(tree.left),depth(tree.right)
        return max(left,right)+1
    #前序遍历   
    def pre_order(tree):
        if tree==None:
            return
        print tree.data
        pre_order(tree.left)
        pre_order(tree.right)
    #中序遍历   
    def mid_order(tree):
        if tree==None:
            return
        mid_order(tree.left)
        print tree.data
        mid_order(tree.right)    
    #后序遍历   
    def post_order(tree):
        if tree==None:
            return
        post_order(tree.left)
        post_order(tree.right)   
        print tree.data
    
    #层次遍历    
    def level_order(tree):
         if tree==None:
            return 
         q=[]
         q.append(tree)
         while q:
             current=q.pop(0)
             print current.data
             if current.left!=None:
                q.append(current.left)
             if current.right!=None:
                q.append(current.right)
    
    展开全文
  • 先序遍历 #include <stdio.h> #define MAX 100 typedef struct Node { int data; struct Node * lchild; struct Node * rchild; }BTNode; // 先序遍历非递归算法 void preorder(BTNode * b) { // 创建...
  • 1.二叉树中有两特殊二叉树,叫做满二叉树和完全二叉树 2.满二叉树指是二叉树内部结点都有两个儿子 3.完全二叉树就是叶子结点不完整,从右向左连续缺若干结点,只需要用一个一维数组即可存储完全二叉树 4....
  • 1.树 我们选择一数据结构,不仅要能存储数据,而且要能...为了表达具有一对多关系的数据,我们引进了树的概念。掌握树的关键就在于掌握这种不断延伸的一对多的关系。 下面我们介绍几约定俗称的概念: ...
  • 树的种遍历方式

    千次阅读 2018-07-31 23:53:13
    今天学到了树的三种遍历方式:前序遍历,中序遍历,后序遍历,层序...来看一看这四种遍历方式的代码:  前序遍历: void PreorderTraversal( BinTree T ){ if (T==NULL)//当遍历到的节点为空时终止遍历 retur...
  • 目录系列文章目录前言一、四种遍历方式二、代码实战 前言 本文主要讲述二叉树几种遍历方式,以及代码实战 一、四种遍历方式 1.前序遍历:先访问根节点,后访问左节点,最后右节点 2.中序遍历:先访问左节点,后...
  • 前序遍历 递归版 编程思想 即借助系统栈,效率较低。二叉树的前序遍历规则:1....//树的定义 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), ...
  • 在二叉树遍历中存在三较为常用的遍历方式:前序遍历、中序遍历、后序遍历 前序遍历 使用递归方式实现前序遍历具体过程为: 先访问根节点 再序遍历左子树 最后序遍历右子 中序遍历 使用递归方式实现中序遍历...
  • -02:二叉树建立及四种遍历方式 整理了完全二叉树建立方法以及四种遍历方式(多种方法实现) 在保证结构定义一样前提下,代码可通用。 0x01.二叉树结构定义: typedef struct TreeNode { char data; ...
  • 种遍历方式(以根分类) 前序遍历:先访问根节点,再访问左子节点,最后访问右子节点。 中序遍历:先访问左子节点,再访问根节点,最后访问右子节点。 后续遍历:先访问左子节点,再访问右子节点,最后访问根节点...
  • 下面就主要介绍下二叉树的常用的四种遍历方式。 其中DFS(Depth-First-Search)的有三种分别为先序遍历,中序遍历及后序遍历,而使用BFS的只有层序遍历。 一.先序遍历 先序遍历的顺序为对于当前结点先访问其本身...
  • 二叉树四种遍历方式 前序遍历/先序遍历 :先访问根节点,再递归遍历左子树,再递归遍历右子 (根 左 右)A B D E C 中序遍历: 先递归遍历左子树,再访问根节点,再递归遍历右子(左 根 右) D B E A C 后序遍历: 先递归...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 420
精华内容 168
关键字:

树的四种遍历方式