精华内容
下载资源
问答
  • 2022-03-23 23:47:46

    目录

    1. 定义二叉树结点类TreeNode

    2. 前序遍历(非递归)

    3. 中序遍历(非递归)

    4. 后序遍历(非递归)


    1. 定义二叉树结点类TreeNode

    public class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        public TreeNode(char val) {
            this.val = val;
        }
    }

    2. 前序遍历(非递归)

    public class TestBinaryTree {
        //前序遍历-非递归
        public preOrderTraversalNor (TreeNode root) {
            if (root == null) return;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
    
            while (cur != null || !stack.empty()) {
                while (cur != null) {
                    stack.push(cur);
                    System.out.println(cur.val + " ");
                    cur = cur.left;
                }
                //当cur.left为空时,弹栈
                TreeNode top = stack.pop();
                cur = top.right;    //1.null  2.不是null的情况
            }
        }
    }

    3. 中序遍历(非递归)

        void inOrderTraversalNor (TreeNode root) {
            if (root == null) return;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode cur = root;
    
            while (cur != null || !stack.empty()) {
                while (cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                //当cur==null,说明走到了二叉树的最左侧,开始弹栈并打印
                TreeNode top = stack.pop();
                System.out.print(top.val+" ");
                cur = top.right;  
            }
            System.out.println();
        } 

    4. 后序遍历(非递归)

    主要注意解决cur当前结点被打印 和 cur的右侧结点已被打印的问题

        void postOrderTraversalNor(TreeNode root) {
            if (root == null) return;
            Stack<TreeNode> stack = new Stack<>();
            TreeNode prev = null;
            TreeNode cur = root;        
            while ( cur != null || !stack.empty()) {
                while ( cur != null) {
                    stack.push(cur);
                    cur = cur.left;
                }
                //走到最左边了
                cur = stack.peek();
                if (cur.right == null || cur.right == prev) {    //cur.right == prev表明右结点被打印过了
                    stack.pop();
                    System.out.print(cur.val+" ");
                    //记录被打印过的结点
                    prev = cur;
                    cur = null;    //打印完一定要置空
                } else {
                    cur = cur.right;
                }
            }
        }

    更多相关内容
  • 后序遍历先序遍历中序遍历先序DLR中序LDR后序LRD二叉树二叉树遍历 可得二叉树的如下几种次序的遍历 先左后右 先右后左 先序DLR DRL 中序LDR RDL 后序LRD RLD 一般情况采用先左后右的方法来遍历二叉树ABFDGICEHJ...
  • //设计一个递归算法判断二叉树中是否含有度为2的结点 bool hasdegree2(BiTree root) {if(root==NULL) return false; if(root->lchild==NULL & root->rchild==NULL) return false; if (root->lchild!=NULL & root->...
  • 1 图的遍历与连通性 从已给的连通图中某一顶点出发沿着一些边访遍图中所有的顶点且使每个顶点仅被访问一次就叫做图的遍历 (Graph Traversal) 图中可能存在回路且图的任一顶点都可能与其它顶点相通在访问完某个顶点...
  • 二叉树非递归遍历

    2018-10-23 11:38:21
    数据结构的代码实现,非递归算法,。
  • 数据结构中二叉树的递归与非递归遍历算法(先序、中序、后序)+层次遍历算法分析与实现。 数据结构二叉树的遍历算法!!!

    文章篇幅有点长,二叉树的递归遍历算法不作详细分析,但是二叉树的非递归遍历算法和层次遍历算法都有非常详细的分析过程记得往下翻哦!

    二叉树的递归遍历算法实现

    我们首先用递归的方法先序遍历创建这样一棵二叉树,如图所示,二叉树创建完毕,我们开始研究二叉树的非递归遍历算法。
    在这里插入图片描述

    1. 算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 1000
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode,*BiTree;
    BiTree creat_BiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')
    	{
    		T= NULL;
    	}
    	else
    	{
    		T = (BiTreeNode*)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = creat_BiTree();
    		T->RChild = creat_BiTree();
    	}
    	return T;
    }
    //先序遍历
    int PreOrder(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	printf("%c", pointer->data);
    	PreOrder(pointer->LChild);
    	PreOrder(pointer->RChild);
    }
    //中序遍历
    int InOrder(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	InOrder(pointer->LChild);
    	printf("%c", pointer->data);
    	InOrder(pointer->RChild);
    }
    //后序遍历
    int PostOrder(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	PostOrder(pointer->LChild);
    	PostOrder(pointer->RChild);
    	printf("%c", pointer->data);
    }
    //二叉树的层次遍历
    int Levelprint(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	BiTree a[maxsize];
    	int front = -1;
    	int rear = 0;
    	BiTreeNode* p = pointer;
    	a[rear] = p;
    	while (front != rear)
    	{
    		front++;
    		printf("%c", a[front]->data);
    		if (a[front]->LChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->LChild;
    		}
    		if (a[front]->RChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->RChild;
    		}
    	}
    	return 1;
    }
    //统计二叉树的结点数
    int PreOrder2(BiTree pointer,int *count)
    {
    	if (pointer == NULL) return 0;
    	(*count)++;
    	PreOrder2(pointer->LChild, count);
    	PreOrder2(pointer->RChild, count);
    }
    //统计二叉树非终端结点(分支结点)的个数
    int PreOrder3(BiTree pointer, int* count)
    {
    	if (pointer == NULL) return 0;
    	if (pointer->LChild != NULL||pointer->RChild != NULL)
    	{
    		(*count)++;
    	}
    	PreOrder3(pointer->LChild, count);
    	PreOrder3(pointer->RChild, count);
    }
    //统计二叉树的叶子结点的个数
    int PreOrder4(BiTree pointer, int* count)
    {
    	if (pointer == NULL) return 0;
    	if (!pointer->LChild&&!pointer->RChild)
    	{
    		(*count)++;
    	}
    	PreOrder4(pointer->LChild, count);
    	PreOrder4(pointer->RChild, count);
    }
    //求二叉树的高度
    int BiTree_height(BiTree pointer)
    {
    	int LHeight, RHeight, Tree_Height;
    	if (pointer == NULL) return 0;
    	LHeight = BiTree_height(pointer->LChild);
    	RHeight = BiTree_height(pointer->RChild);
    	Tree_Height = (LHeight > RHeight) ? LHeight + 1 : RHeight + 1;
    	return Tree_Height;
    }
    void main()
    {
    	BiTree T;
    	int count1 = 0,count2=0,count3=0,count4=0;
    	T = creat_BiTree();
    	printf("先序遍历序列:\n");
    	PreOrder(T);
    	printf("\n中序遍历序列:\n");
    	InOrder(T);
    	printf("\n后序遍历序列:\n");
    	PostOrder(T);
    	printf("\n层次遍历序列:\n");
    	Levelprint(T);
    	printf("\n二叉树的结点数为:\n");
    	PreOrder2(T, &count1);
    	printf("%d", count1);
    	printf("\n二叉树的分支结点数为:\n");
    	PreOrder3(T, &count2);
    	printf("%d", count2);
    	printf("\n二叉树的叶子结点数为:\n");
    	PreOrder4(T, &count3);
    	printf("%d", count3);
    	printf("\n二叉树的高度为:\n");
    	count4 = BiTree_height(T);
    	printf("%d", count4);
    }
    

    2. 代码运行结果:
    在这里插入图片描述

    二叉树的非递归遍历算法实现

    我们首先用递归的方法先序遍历创建这样一棵二叉树,如图所示,二叉树创建完毕,我们开始研究二叉树的非递归遍历算法。
    在这里插入图片描述

    一、非递归先序遍历算法

    1.算法实现思路:

    二叉树的先序遍历算法主要思想是:访问根结点,先序遍历左子树,先序遍历右子树。我们可以使用一个栈来实现二叉树的非递归先序遍历算法。首先,创建栈S并对其初始化,栈中的每一个元素是二叉树中的结点。定义指针p开始指向根结点,从根结点开始遍历二叉树中的结点,若结点存在(P!=NULL),输出该结点的值,并将该结点入栈S中,将指针p指向其左孩子(P=P->Lchild),之后判断P指向的结点是否为空,若为空,则从栈中弹出上一结点,并让指针P指向该结点的右孩子( p=pop(s),p = p->RChild),用一个while循环重复以上步骤。直到结点不存在且栈为空结束时循环 while(p || !isempty(s)),二叉树先序遍历遍历结束。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的非递归先序遍历
    void Non_recursive_PREprint(BiTree pointer)
    {
    	sqstack* s;
    	s = initialize();
    	BiTreeNode* p;
    	p = pointer;
    	while (p || !isempty(s))
    	{
    		if (p != NULL)
    		{
    			printf("%c", p->data);
    			push(s, p);
    			p = p->LChild;
    		}
    		else
    		{
    			p = pop(s);
    			p = p->RChild;
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的先序遍历:\n");
    	Non_recursive_PREprint(T);
    }
    

    3.代码运行结果
    在这里插入图片描述

    二、非递归中序遍历算法

    1.算法思路:

    二叉树的中遍历算法主要思想是:中序遍历左子树,访问根结点,中序遍历右子树。该遍历算法与先序遍历算法思路相似,同样使用一个栈来实现二叉树的非递归中遍历算法。首先,创建栈S并对其初始化,栈中的每一个元素是二叉树中的结点。定义指针p开始指向根结点,从根结点开始遍历二叉树中的结点,若结点存在(P!=NULL),将该结点入栈S中,将指针p指向其左孩子(P=P->Lchild),之后判断P指向的结点是否为空,若为空,则从栈中弹出上一结点,并输出该结点的值,并让指针P指向该结点的右孩子( p=pop(s);printf(“%c”,p->data);p = p->RChild),用一个while循环重复以上步骤。直到结点不存在且栈为空结束时循环 while(p || !isempty(s)),二叉树中序遍历算法结束。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的非递归中序遍历
    void Non_recursive_INprint(BiTree pointer)
    {
    	sqstack* s;
    	s = initialize();
    	BiTreeNode* p;
    	p = pointer;
    	while (p || !isempty(s))
    	{
    		if (p != NULL)
    		{
    			push(s, p);
    			p = p->LChild;
    		}
    		else
    		{
    			p = pop(s);
    			printf("%c", p->data);
    			p = p->RChild;
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的中序遍历:\n");
    	Non_recursive_INprint(T);
    }
    

    3.代码运行结果:
    在这里插入图片描述

    三、非递归后序遍历算法

    1.算法思路:

    二叉树的后序遍历算法的主要思想是:后序遍历左子树,后序遍历右子树,访问根结点。二叉树的非递归后序遍历算法可以构造一栈来实现,栈中的元素存储的是二叉树中的结点,对于后序遍历算法,我们需要判断二叉树中每个结点的左子树是否遍历完,只有将左子树遍历完,我们才能对该结点的右子树和该结点进行遍历输出,我们可以定义一个标志数组int temp[maxsize],先初始化为0,数组元素和栈s中元素对应,栈顶指针top和数组下标对应。首先,先让指针p指向这棵二叉树的根结点,将该结点压入栈s中,同时对其标志数组赋值为0 (tem[s->top]=0),将指针p指向该结点的左孩子(p=p->Lchild),如果其左孩子为空,将栈s的栈顶元素出栈,指针p指向其右孩子,同时将该结点压回栈s中,同时对其标志数组赋值为1 (tem[s->top]=1),表示该结点的左子树已遍历完成, 若该结点的右孩子为空,则对堆栈结点进行遍历,将标志数组tem[s->top]值为1的结点全部打印输出。从二叉树的根结点开始,定一个外部循环,不断重复以上对结点的操作,直到指针p指向的结点为空且栈s中元素为空时结束循环。这就是非递归后续遍历二叉树的主要思路。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的非递归后序遍历
    void Non_recursive_POSTprint(BiTree pointer)
    {
    	sqstack* s;
    	s = initialize();
    	BiTreeNode* p = pointer;
    	int temp[maxsize] = { 0 };
    	while (p || !isempty(s))
    	{
    		if (p != NULL)
    		{
    			push(s, p);
    			temp[s->top] = 0;
    			p = p->LChild;
    		}
    		else
    		{
    			while (temp[s->top] == 1)
    			{
    				p = pop(s);
    				printf("%c", p->data);
    			}
    			if (s->top == -1)
    			{
    				break;
    			}
    			p = pop(s);
    			push(s, p);
    			temp[s->top] = 1;
    			p = p->RChild;
    		}
    	}
    	printf("\n");
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的后序遍历: ");
    	Non_recursive_POSTprint(T);
    }
    

    3.代码运行结果:
    在这里插入图片描述

    四、二叉树的层次遍历算法

    1.算法思路:

    二叉树的层次遍历算法是指从二叉树的第一层开始,逐层从左到右依次遍历结点,最终将整棵二叉树遍历完成。对于这个算法,我们可以采用队列来实现,我们初始化一个顺序队列,顺序队列的每个元素都存储着二叉树的结点,开始顺序队列为空,首先,将根结点入队,进入循环,将队头指针所指的元素出队,并输出其结点的值,如果该结点的左孩子存在,则将其左孩子入队,如果该结点的右孩子存在,则将右孩子入队,直到队头指针和队尾指针相等时(表明队列为空)退出循环,这颗二叉树的层次遍历就完成了。

    2.算法代码如下:

    #include<stdio.h>
    #include<stdlib.h>
    #define maxsize 100
    typedef char elemtype;
    typedef struct BiTreeNode
    {
    	elemtype data;
    	struct BiTreeNode* LChild, * RChild;
    }BiTreeNode, * BiTree;
    typedef struct stack
    {
    	BiTreeNode* a[maxsize];
    	int top;
    }sqstack;
    sqstack* initialize()
    {
    	sqstack* s;
    	s = (sqstack*)malloc(sizeof(sqstack));
    	if (!s)
    		return NULL;
    	else
    	{
    		s->top = -1;
    		return s;
    	}
    }
    int isempty(sqstack* s)
    {
    	return (s->top == -1);
    }
    int isfull(sqstack* s)
    {
    	return (s->top == maxsize - 1);
    }
    int push(sqstack* s, BiTreeNode* p)
    {
    	if (isfull(s))
    		return 0;
    	else
    		s->a[++(s->top)] = p;
    	return 1;
    }
    BiTreeNode* pop(sqstack* s)
    {
    	return s->a[(s->top)--];
    }
    //以递归的方式先序创建一棵二叉树
    BiTree CreatBiTree()
    {
    	char ch;
    	BiTree T;
    	scanf_s("%c", &ch);
    	if (ch == '#')  T = NULL;
    	else
    	{
    		T = (BiTree)malloc(sizeof(BiTreeNode));
    		T->data = ch;
    		T->LChild = CreatBiTree();
    		T->RChild = CreatBiTree();
    	}
    	return T;
    }
    //二叉树的层次遍历
    int Levelprint(BiTree pointer)
    {
    	if (pointer == NULL)
    		return 0;
    	BiTree a[maxsize];
    	int front = -1;
    	int rear = 0;
    	BiTreeNode* p = pointer;
    	a[rear] = p;
    	while (front != rear)
    	{
    		front++;
    		printf("%c", a[front]->data);
    		if (a[front]->LChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->LChild;
    		}
    		if (a[front]->RChild != NULL)
    		{
    			rear++;
    			a[rear] = a[front]->RChild;
    		}
    	}
    	return 1;
    }
    void main()
    {
    	BiTree T;
    	T = CreatBiTree();
    	printf("二叉树的层次遍历为: ");
    	Levelprint(T);
    }
    

    3.代码运行结果:
    在这里插入图片描述

    展开全文
  • 数据结构非递归先序、中序、后序遍历二叉树数据结构非递归先序、中序、后序遍历二叉树
  • 主要介绍了C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历)的相关资料,这里提供实例代码来帮助大家理解掌握二叉树,需要的朋友可以参考下
  • 如果你用C或者C++或者其他高级语言写过二叉树或者阅读过相关方面代码,应该知道二叉树非递归遍历避不开通过栈或者队列实现。是的,python也一样。但是python自带的list功能很强大,即可以当stack
  • 齐鲁工业大学实验报告 成绩 课程名称 数据结构 ...实现二义树的先序中序与后序遍历的递归算法与非递归算法 求二义树的结点个数叶子结点个数二义树的高度度为 2的结点个数 二 实验环境 微型计算机vc 三 实验内容 实现二
  • 主要介绍了C语言排序方法,包含10种排序,数据结构课程设计实例二叉树建立遍历冒泡排序快速排序_二叉排序树_二叉树层次遍历_二叉树非递归遍历_二叉树建立括号匹配直接插入选择代码大学生本科毕业设计期末作业排序...
  • 主要介绍了C语言数据结构二叉树非递归后序遍历算法的相关资料,希望通过本文能帮助到大家,让大家实现这样的功能,需要的朋友可以参考下
  • 编写程序,用先序递归的方法建立二叉树,建立二叉树后,用中序非递归方法遍历二叉树,并输出遍历序列。
  • 遍历二叉树需要决定对根节点N、左子树L、右子树R的访问顺序(按照先遍历左子树在遍历右子树的原则),常见的遍历次序有先序(NLR)、中序(LNR)、后序(LRN)三种遍历算法,这也是最常见的二叉树遍历算法。...

    二叉树的遍历

        所谓二叉树的遍历,是指按某条搜索路径访问树中的每个节点,使得每个节点均被访问一次,而且仅被访问一次。

        遍历二叉树需要决定对根节点N、左子树L、右子树R的访问顺序(按照先遍历左子树在遍历右子树的原则),常见的遍历次序有先序(NLR)、中序(LNR)、后序(LRN)三种遍历算法,这也是最常见的二叉树遍历算法。

       其中的“序”实际上就是根节点的访问时机。

    1. 二叉树的数据结构

    typedef struct BTNode{

        int data;       //保存节点中的值

        struct BTNode  *lchild;     //左孩子指针

        struct BTNode  *rchild;     //右孩子指针

    }BTNode,*BiTree;

    这里我使用的比较适合基础学者的二叉树的存储结构,不同的存储结构,实现二叉树操作的算法也会不同,因此要根据实际应用场合(树的形态和需要进行的运算)来选择合适的存储结构。

    不说废话了,哈哈肯定把你急死了!

     

    2.二叉树的递归遍历

    1. 先序遍历

     先序遍历(PreOrder)的操作如下:

    ①首先若二叉树为空,则什么也不做;否则,

    • 访问根节点;
    • 先序遍历左子树;
    • 先序遍历右子树。

    对应的递归算法如下:

    void PreOrder(BiTree T){
        if(T!=NULL){
            visit(T);        //访问跟结点
            PreOrder(T->lchild);    //访问左子树
            PreOrder(T->rchild);    //访问右子树
        }
    }

    这里举一个例子做说明吧(后面都是使用这个例子),例子二叉树如下:

     这样一来先序遍历所得到的节点序列为1 2 4 6 3 5.

     

    2. 中序遍历

    中序遍历(InOrder)的操作如下:

    ①首先若二叉树为空,则什么也不做;否则,

    • 中序遍历左子树;
    • 访问根节点;
    • 中序遍历右子树。

    对应的递归算法如下:

    void InOrder(BiTree T){
        if(T!=NULL){
            InOrder(T->lchild);//递归遍历左子树
            visit(T);//访问根结点
            InOrder(T->lchild);//递归遍历右子树
            
        }
    }

    这样一来中序遍历所得到的节点序列为2 6 4 1 3 5.

     

    3. 后序遍历

    后序遍历(PostOrder)的操作如下:

    ①首先若二叉树为空,则什么也不做;否则,

    • 后序遍历左子树;
    • 后序遍历右子树;
    • 访问根节点。

    对应的递归算法如下:

    void PostOrder(BiTree T){
        if(T!=NULL){
            PostOrder(T->lchild);//递归遍历左子树
            PostOrder(T->rchild);//递归遍历左子树
            visit(T);            //访问根结点
        }
    }

    这样一来后序遍历所得到的节点序列为6 4 2 5 3 1.

     

    这是二叉树结点的递归遍历,实现起来比较简单,很好地使用了递归的思想。

    二叉树的非递归遍历在我的另一边文章当中

    连接如下:二叉树的非递归遍历

     

    最后,送大家一句话:知识并不能为我们带来财富,但是能使我们有能力去创造财富。

    展开全文
  • PTA 二叉树非递归遍历 这一题写的我快要吐了,讲述一下心酸历程。 6-3 二叉树非递归遍历 (10 分) 本题要求用非递归的方法实现对给定二叉树的 3 种遍历。 函数接口定义: void InorderTraversal( ...

    PTA 二叉树的非递归遍历

    这一题写的我快要吐了,讲述一下心酸历程。

    6-3 二叉树的非递归遍历 (10 分)
    本题要求用非递归的方法实现对给定二叉树的 3 种遍历。

    函数接口定义:
    void InorderTraversal( BinTree BT );
    void PreorderTraversal( BinTree BT );
    void PostorderTraversal( BinTree BT );
    其中BinTree结构定义如下:


    typedef struct TNode Position;
    typedef Position BinTree;
    struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int flag;
    };
    要求 3 个函数分别按照访问顺序打印出结点的内容,格式为一个空格跟着一个字符。


    此外,裁判程序中给出了堆栈的全套操作,可以直接调用。


    裁判测试程序样例:
    #include <stdio.h>
    #include <stdlib.h>
    typedef enum { false, true } bool;


    typedef char ElementType;
    typedef struct TNode Position;
    typedef Position BinTree;
    struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
    int flag;
    };


    /
    ------堆栈的定义-------
    /
    typedef Position SElementType;
    typedef struct SNode PtrToSNode;
    struct SNode {
    SElementType Data;
    PtrToSNode Next;
    };
    typedef PtrToSNode Stack;


    /
    裁判实现,细节不表 /
    Stack CreateStack();
    bool IsEmpty( Stack S );
    bool Push( Stack S, SElementType X );
    SElementType Pop( Stack S ); /
    删除并仅返回S的栈顶元素 /
    SElementType Peek( Stack S );/
    仅返回S的栈顶元素 /
    /
    ----堆栈的定义结束-----/


    BinTree CreateBinTree(); /
    裁判实现,细节不表 /
    void InorderTraversal( BinTree BT );
    void PreorderTraversal( BinTree BT );
    void PostorderTraversal( BinTree BT );


    int main()
    {
    BinTree BT = CreateBinTree();
    printf(“Inorder:”); InorderTraversal(BT); printf("\n");
    printf(“Preorder:”); PreorderTraversal(BT); printf("\n");
    printf(“Postorder:”); PostorderTraversal(BT); printf("\n");
    return 0;
    }
    /
    你的代码将被嵌在这里 */
    输入样例:
    如图
    在这里插入图片描述


    输出样例:
    Inorder: D B E F A G H C I
    Preorder: A B D F E C G H I
    Postorder: D E F B H G I C A

            这道题目简直是丧尽天良,惨绝人寰。


            一开始题目看错了,以为就是简单的递归(没看见“非”字)遍历,马上就莽。一波只过了2个案例,重新审题发现要非递归。
            既然是非递归,那无非就是栈,一看题目果然有栈。好的,再扫了一眼题目,节点有个int参数flag,突然想起老师上课说的按照相反顺序入栈,然后记一个bool,1代表visit过了,0代表没有,然后马上又打。打到一半发现这个flag走了一次之后肯定就不是0了,有可能初始化就不是0(恕我没学好,我也不知道,感觉没有初始化函数他就会随机,事实上我并不知道会怎么样)。那我还有两个要遍历的就走不了。


            遂重写。换了个思路,显然先序遍历是容易的,一个while就能搞定,剩下两个分别是 左右中 左中右,想到先一直找左,没有了再根据情况判断下一个是什么。
            上代码,细节不说,看码。

    void InorderTraversal( BinTree BT ){
        Stack s=CreateStack();
        if(BT!=NULL)
            Push(s,BT);
        BinTree now;
        while(!IsEmpty(s)){
            while(Peek(s)->Left!=NULL)
                Push(s,Peek(s)->Left);
            while(!IsEmpty(s)){
                now=Peek(s);
                printf(" %c",now->Data);
                Pop(s);
                if(now->Right!=NULL){
                    Push(s,now->Right);
                    break;
                }
            }
        }
    }
    
    void PreorderTraversal( BinTree BT ){
    
        Stack s=CreateStack();
       //Push(s,BT);
        BinTree now=BT;
        if(now!=NULL)
            Push(s,now);
        while(!IsEmpty(s)){
            now=Pop(s);
            printf(" %c",now->Data);
            if(now->Right!=NULL)
                Push(s,now->Right);
            if(now->Left!=NULL)
                Push(s,now->Left);
        }
    }
    
    void PostorderTraversal( BinTree BT ){
        Stack s=CreateStack();
        if(BT!=NULL)
            Push(s,BT);
        BinTree now=BT,last=NULL;
        while(!IsEmpty(s)){
            while(Peek(s)->Left!=NULL)
                Push(s,Peek(s)->Left);
            while(!IsEmpty(s)){
                now=Peek(s);
                if(now->Right==last||now->Right==NULL){
                    printf(" %c",now->Data);
                    Pop(s);
                    last=now;
                }
                else{
                    Push(s,now->Right);
                    break;
                }
            }
        }
    }
    
    

             还有最后一个坑点

             最后一个测试点总是段错误,我仔细的看来看去都没看见野指针之类的,还以为自己遇到了指针漂移的玄学问题。。。。

    最后发现

    有个根节点是NULL的测试点。。。

    一开始直接就push了根节点,没想太多。找了半天,加上之前的递归写法,最后一个测试点过了,但是时间迷之巨大。。以为是大数据,一直没往根节点为空那个方向去想,结果在自暴自弃的路上疯狂乱改。。。????什么居然过了。。。。。。????



    更新一下

    我发现我的同学递归也过了。。。。然后仔细看了一下自己的。。。函数名直接复制了第一个函数的函数名,导致有两个函数是错的。。。下次一定好好检查

    void InorderTraversal( BinTree BT ){
    	if(BT==NULL)
    		return ;
    	InorderTraversal(BT->Left);
    	printf(" %c",BT->Data);
    	InorderTraversal(BT->Right);
    }
    void PreorderTraversal( BinTree BT ){
    	if(BT==NULL)
    		return ;
    	printf(" %c",BT->Data);
    	PreorderTraversal(BT->Left);
    	PreorderTraversal(BT->Right);
    }
    void PostorderTraversal( BinTree BT ){
    	
    	if(BT==NULL)
    		return ;
    	PostorderTraversal(BT->Left);
    	PostorderTraversal(BT->Right);
    	printf(" %c",BT->Data);
    }
    

    这是常规递归写法 。。题目居然不卡递归层数。。。

    展开全文
  • 二叉树遍历可以使用递归的方法,代码也很简单。不过也是可以通过非递归方式完成的。本次介绍二叉树的前序、中序、后序遍历非递归实现和层次遍历非递归实现。
  • 非递归遍历二叉树 这一部分内容并不难,可就是找不到完整的可实现代码教程,书上也只是粗略带过,不死心的我决定编程实现一下,也算是对我数据结构树遍历这一部分的检验。 查错排错还是花了不少时间,不多赘述,代码...
  • 二叉树非递归遍历(c语言)

    千次阅读 2020-04-07 23:16:44
    一、在c语言中进行二叉树非递归遍历需要用到栈,而在c语言中没有直接调用栈的接口,所以在实现非递归遍历时需要先实现一个栈,需要用到出栈,入栈,栈顶元素,判断栈是否为空,这四个接口,别的可以不用实现。...
  • 二叉树的中序、前序、后序的递归、非递归遍历算法
  • 二叉树结点数据结构: 定义一个顺序栈及其操作: 前序遍历非递归实现: 中序遍历非递归实现: 后序遍历非递归实现: 非递归主要依靠用一个栈记录回溯点,进行回溯。 二叉树结点数据结构: typedef ...
  • 目录 1. 创建一颗二叉树 2.递归前序遍历二叉树 3.递归中序遍历二叉树 ...对于二叉树非递归 深度优先遍历,使用的都是栈 对于二叉树的层次遍历,使用的是队列 1. 创建一颗二叉树 依据前序遍...
  • 二叉树的遍历分为前序遍历、中序遍历和后序遍历三种,其遍历顺序分别为根-左-右,左-根-右和左-右-根。...对于递归遍历,三种遍历顺序有一定的相似性,所以比较简单://前序遍历 void preorder(TreeNode *root
  • 定义二叉树的存储结构,采用非递归算法实现二叉树二叉树的先序、中序、后序和按层遍历。并实现求二叉树的深度、求总结点数、求叶子结点、查找某个结点等操作(可以采用递归)。
  • 而且对于不同的遍历顺序(前序、中序、后序),循环结构差异很大,更增加了记忆负担。 因此,我在这里介绍一种“灰白标记法”,兼具栈迭代方法的高效,又像递归方法一样简洁易懂,更重要的是,这种方法对于前序、...
  • 下面我将以一个小白的视角带你过一遍二叉树非递归遍历实现原理以及相应的C++代码实现。话不多说,现在开始???? 2.遍历过程 我将用最简单的二叉树来说明算法思路,待遍历的二叉树【 1 – 2 – 3】。 前序遍历:根...
  • 1.输入前序和中序遍历结果,建立二叉树 2.实现二叉树的三种递归遍历算方法 3.实现二叉树的三种非递归遍历算法 4.实现二叉树的旋转90°后的打印,直观树形结构
  • 二叉树非递归遍历

    千次阅读 2020-09-27 16:25:05
    二叉树非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是递归定义,因此采用递归的方法去实现...
  • 二叉树非递归遍历算法

    千次阅读 2021-10-18 12:47:26
    算法思路:采用栈来实现先序遍历非递归算法。创建栈,并初始化。遍历结点,若结点存在,则入栈,并输出结点的值,指向其左孩子;否则出栈,访问结点,指向其右孩子。如果结点不存在或者栈为空,则遍历结束。 代码:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 44,571
精华内容 17,828
关键字:

数据结构二叉树的非递归遍历

数据结构 订阅