精华内容
下载资源
问答
  • 二叉树的遍历

    万次阅读 2020-05-30 12:36:43
    遍历 先序遍历[先访问根节点] 先访问根节点 再先序访问左子树 ...但是通过先序和后序是无法还原出原始的二叉树的 换种说法: 只有通过先序和中序,或 通过中序和后序 我们才可以唯一的确定一个二叉树 ...

    遍历

    先序遍历[先访问根节点]
    先访问根节点
    再先序访问左子树
    再先序访问右子树

    中序遍历[中间访问根节点]
    中序遍历左子树
    再访问根节点
    再中序遍历右子树

    后序遍历[最后访问根节点]
    先中序遍历左子树
    再中序遍历右子树
    再访问根节点

    已知两种遍历序列求原始二叉树
    通过先序和中序或者中序和后序我们可以
    还原出原始的二叉树
    但是通过先序和后序是无法还原出原始的二叉树的
    换种说法:
    只有通过先序和中序,或 通过中序和后序
    我们才可以唯一的确定一个二叉树

    展开全文
  • 数据结构 - 二叉树的遍历

    万次阅读 多人点赞 2019-02-18 14:32:52
    二叉树的遍历 N:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。 给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树。 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度...

    分享一个大牛的人工智能教程。零基础!通俗易懂!风趣幽默!希望你也加入到人工智能的队伍中来!请点击http://www.captainbed.net 

    二叉树的遍历

    N:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。

    给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一确定一棵二叉树。

    二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。

    深度优先遍历二叉树

    1. 中序遍历(LNR)的递归算法:

    若二叉树为空,则算法结束;否则:

    中序遍历根结点的左子树;

    访问根结点;

    中序遍历根结点的右子树。

    2. 前序遍历(NLR)的递归算法:

    若二叉树为空,则算法结束,否则:

    访问根结点;

    前序遍历根结点的左子树;

    前序遍历根结点的右子树。

    3. 后序遍历(LRN)的递归算法:

    若二叉树为空,则算法结束,否则:

    后序遍历根结点的左子树;

    后序遍历根结点的右子树;

    访问根结点。

    非递归深度优先遍历二叉树

    栈是实现递归最常用的结构,利用一个栈来记下尚待遍历的结点或子树,以备以后访问,可以将递归的深度优先遍历改为非递归的算法。

    1. 非递归前序遍历:遇到一个结点,就访问该结点,并把此结点推入栈中,然后下降去遍历它的左子树。遍历完它的左子树后,从栈顶托出这个结点,并按照它的右链接指示的地址再去遍历该结点的右子树结构。

    2. 非递归中序遍历:遇到一个结点,就把它推入栈中,并去遍历它的左子树。遍历完左子树后,从栈顶托出这个结点并访问之,然后按照它的右链接指示的地址再去遍历该结点的右子树。

    3. 非递归后序遍历:遇到一个结点,把它推入栈中,遍历它的左子树。遍历结束后,还不能马上访问处于栈顶的该结点,而是要再按照它的右链接结构指示的地址去遍历该结点的右子树。遍历完右子树后才能从栈顶托出该结点并访问之。另外,还需要给栈中的每个元素加上一个特征位,以便当从栈顶托出一个结点时区别是从栈顶元素左边回来的(则要继续遍历右子树),还是从右边回来的(则该结点的左、右子树均已遍历)。特征为Left表示已进入该结点的左子树,将从左边回来;特征为Right表示已进入该结点的右子树,将从右边回来。

    非递归广度优先遍历二叉树

    非递归广度优先遍历二叉树(层序遍历)是用队列来实现的。从二叉树的第一层(根结点)开始,自上至下逐层遍历;在同一层中,按照从左到右的顺序对结点逐一访问。

    按照从根结点至叶结点、从左子树至右子树的次序访问二叉树的结点。算法如下:

    1. 初始化一个队列,并把根结点入队列;

    2. 当队列为非空时,循环执行步骤3到步骤5,否则执行6;

    3. 出队列取得一个结点,访问该结点;

    4. 若该结点的左子树为非空,则将该结点的左子树入队列;

    5. 若该结点的右子树为非空,则将该结点的右子树入队列;

    6. 结束。

    /*
     * Binary Tree Breadth-First Traverse - by Chimomo
     */
    
    #include <iostream>
    
    #define _OK 1
    #define _ERROR 0
    
    using namespace std;
    
    // Define node element type in binary tree.
    typedef char Element;
    
    // Binary tree node.
    typedef struct BTNode {
        Element data;
        BTNode *lChild, *rChild; // Define left, right subtree.
    } BTNode, *BTree;
    
    // Define node element type in queue. (The node element type in queue is the pointer to binary tree node)
    typedef BTNode *QElementType;
    typedef int status;
    
    // We need use queue to perform level traverse. So, define queue first.
    typedef struct QNode {
        QElementType data;
        QNode *next;
    } QNode, *QueuePtr;
    
    // Definition of queue.
    typedef struct {
        QueuePtr front;
        QueuePtr rear;
    } LinkQueue;
    
    status InitQueue(LinkQueue &Q) {
        Q.front = NULL;
        Q.rear = NULL;
        return _OK;
    }
    
    bool IsEmpty(LinkQueue Q) {
        return Q.front == NULL;
    }
    
    /**
     * Enqueue.
     * @param Q The queue.
     * @param e The queue element.
     * @return 1 for ok, 0 for error.
     */
    status EnQueue(LinkQueue &Q, QElementType e) {
        // Construct queue node.
        QNode *ptrNode = (QNode *) malloc(sizeof(QNode));
        if (!ptrNode) {
            return _ERROR;
        }
    
        ptrNode->data = e;
        ptrNode->next = NULL;
        if (IsEmpty(Q)) {
            Q.front = Q.rear = ptrNode;
            return _OK;
        }
    
        Q.rear->next = ptrNode;
        Q.rear = ptrNode;
        return _OK;
    }
    
    /**
     * Dequeue.
     * @param Q The queue.
     * @param e The queue element.
     * @return 1 for ok, 0 for error.
     */
    status DeQueue(LinkQueue &Q, QElementType &e) {
        if (IsEmpty(Q)) {
            return _ERROR;
        }
    
        QNode *tempPtr = Q.front;
        e = tempPtr->data;
        Q.front = tempPtr->next;
        free(tempPtr);
        return _OK;
    }
    
    /**
     * Create binary tree.
     * @param T The binary tree address.
     * @return 1 for success, 0 for fail.
     */
    int CreateBTree(BTree &T) {
        char ch;
        cout << "Please input a character:" << endl;
        cin >> ch;
        if (ch == '#') {
            T = NULL;
        } else {
            // Allocate memory for new node.
            if (!(T = (BTNode *) malloc(sizeof(BTNode)))) {
                return 0; // Allocation fails.
            }
    
            T->data = ch;
    
            // Create left subtree.
            CreateBTree(T->lChild);
    
            // Create right subtree.
            CreateBTree(T->rChild);
        }
    
        return 1;
    }
    
    void VisitBTNode(BTNode *BT) {
        cout << BT->data << " ";
    }
    
    void VisitQNode(QNode *Q) {
        VisitBTNode(Q->data);
    }
    
    /**
     * Breadth-first traverse.
     * @param T The binary tree.
     */
    void LevelTraverse(BTree T) {
        QElementType e;
        LinkQueue Q;
        InitQueue(Q);
        EnQueue(Q, T);
        while (!IsEmpty(Q)) {
            VisitQNode(Q.front);
            if (Q.front->data->lChild != NULL) {
                EnQueue(Q, Q.front->data->lChild);
            }
            if (Q.front->data->rChild != NULL) {
                EnQueue(Q, Q.front->data->rChild);
            }
            DeQueue(Q, e);
        }
    }
    
    int main() {
        BTree T;
        CreateBTree(T);
        cout << "Breadth-first traverse: ";
        LevelTraverse(T);
        return 0;
    }
    
    // Output:
    /*
    Please input a character:
    1
    1
    Please input a character:
    2
    2
    Please input a character:
    3
    3
    Please input a character:
    4
    4
    Please input a character:
    5
    5
    Please input a character:
    6
    6
    Please input a character:
    #
    #
    Please input a character:
    #
    #
    Please input a character:
    #
    #
    Please input a character:
    #
    #
    Please input a character:
    #
    #
    Please input a character:
    #
    #
    Please input a character:
    #
    #
    Breadth-first traverse: 1 2 3 4 5 6
    */

     

    展开全文
  • 二叉树的遍历是指从根节点出发, 按照某种次序依次访问二叉树中所有结点, 使得每个结点被访问一次且仅被访问一次。二叉树的遍历方式很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种: 1.前序遍历 ...

    目录

    1.前序遍历

    2.中序遍历

    3.后序遍历

    4.层序遍历


    二叉树的遍历是指从根节点出发, 按照某种次序依次访问二叉树中所有结点, 使得每个结点被访问一次且仅被访问一次。二叉树的遍历方式很多,如果我们限制了从左到右的习惯方式,那么主要就分为四种:

    1.前序遍历

    前序遍历的规则是若二叉树为空,则空操作返回,否则先访问根结点,然后前序遍历左子树,再前序遍历右子树。如图所示的二叉树遍历的顺序为ABDGHCEIF。

    void PreOrder(tnode* t)
    {
    	if (t != NULL)
    	{
    		printf("%d ", t->data);
    		PreOrder(t->left);
    		PreOrder(t->right);
    	}
    }
    

    非递归前序遍历:根据前序遍历访问的顺序,优先访问根结点,然后再分别访问左孩子和右孩子。即对于任一结点,其可看做是根结点,因此可以直接访问,访问完之后,若其左孩子不为空,按相同规则访问它的左子树;当访问其左子树时,再访问它的右子树。对于任一结点P:

         1)访问结点P,并将结点P入栈;

         2)判断结点P的左孩子是否为空,若为空,则取栈顶结点并进行出栈操作,并将栈顶结点的右孩子置为当前的结点P,循环至1);若不为空,则将P的左孩子置为当前的结点P;

         3)直到P为NULL并且栈为空,则遍历结束。

    void preOrder2(tnode* t)     //非递归前序遍历 
    {
    	stack<tnode*> s;
    	tnode *p = t;
    	while (p != NULL || !s.empty())
    	{
    		while (p != NULL)
    		{
    			cout << p->data << " ";
    			s.push(p);
    			p = p->left;
    		}
    		if (!s.empty())
    		{
    			p = s.top();
    			s.pop();
    			p = p->right;
    		}
    	}
    }


    2.中序遍历

    中序遍历的规则是若树为空,则空操作返回,否则从根结点开始中序遍历根结点的左子树,然后是访问根结点,最后中序遍历右子树。如图所示的二叉树遍历的顺序为:GDHBAEICF。

    void inOrder(tnode* t)
    {
    	if (t != NULL)
    	{
    		inOrder(t->left);
    		printf("%d ", t->data);
    		inOrder(t->right);
    	}
    }

    非递归中序遍历:根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。因此其处理过程如下:

       对于任一结点P,

      1)若其左孩子不为空,则将P入栈并将P的左孩子置为当前的P,然后对当前结点P再进行相同的处理;

      2)若其左孩子为空,则取栈顶元素并进行出栈操作,访问该栈顶结点,然后将当前的P置为栈顶结点的右孩子;

      3)直到P为NULL并且栈为空则遍历结束

    void inOrder2(tnode* t)      //非递归中序遍历
    {
    	stack<tnode*> s;
    	tnode *p = t;
    	while (p != NULL || !s.empty())
    	{
    		while (p != NULL)
    		{
    			s.push(p);
    			p = p->left;
    		}
    		if (!s.empty())
    		{
    			p = s.top();
    			cout << p->data << " ";
    			s.pop();
    			p = p->right;
    		}
    	}
    }


    3.后序遍历

    后序遍历的规则是若树为空,则空操作返回,否则从左到右先叶子后结点的方式遍历访问左右子树,最后访问根结点。如图所示的二叉树遍历的顺序为:GHDBIEFCA。

    void PostOrder(tnode* t)
    {
    	if (t != NULL)
    	{
    		PostOrder(t->left);
    		PostOrder(t->right);
    		printf("%d ", t->data);
    	}
    }

    后序遍历的非递归实现是三种遍历方式中最难的一种。因为在后序遍历中,要保证左孩子和右孩子都已被访问并且左孩子在右孩子前访问才能访问根结点,这就为流程的控制带来了难题。

    对于任一结点P,将其入栈,然后沿其左子树一直往下搜索,直到搜索到没有左孩子的结点,此时该结点出现在栈顶,但是此时不能将其出栈并访问,因此其右孩子还为被访问。所以接下来按照相同的规则对其右子树进行相同的处理,当访问完其右孩子时,该结点又出现在栈顶,此时可以将其出栈并访问。这样就保证了正确的访问顺序。可以看出,在这个过程中,每个结点都两次出现在栈顶,只有在第二次出现在栈顶时,才能访问它。因此需要多设置一个变量标识该结点是否是第一次出现在栈顶。

    void postOrder2(tnode *t)//后序遍历的非递归算法
    {
    	stack<tnode*> s;
    	tnode *temp = t;
    	while (temp != NULL || !s.empty())
    	{
    		while (temp != NULL)
    		{
    			temp->cishu = 1;       // 当前节点首次被访问
    			s.push(temp);
    			temp = temp->left;
    		}
    		if (!s.empty())
    		{
    			temp = s.top();
    			if (temp->cishu == 1)   // 第一次出现在栈顶
    			{
    
    				temp->cishu++;
    				s.push(temp);
    				temp = temp->right;
    			}
    			
    			if (temp->cishu == 2)//第二次输出并制空,防止陷入死循环
    			{
    				cout << temp->data;
    				temp = NULL;
    			}
    		}
    	}
    }

    另外一种遍历方法。

    void postOrder3(tnode *t)
    {
    	if (t == NULL)
    		return;
    	stack<tnode*> s;
    	//pCur:当前访问节点,pLastVisit:上次访问节点
    	tnode* pCur, *pLastVisit;
    	//pCur = root;
    	pCur = t;
    	pLastVisit = NULL;
    	//先把pCur移动到左子树最下边
    	while (pCur)
    	{
    		s.push(pCur);
    		pCur = pCur->left;
    	}
    	while (!s.empty())
    	{
    		//走到这里,pCur都是空,并已经遍历到左子树底端(看成扩充二叉树,则空,亦是某棵树的左孩子)
    		pCur = s.top();
    		s.pop();
    		//一个根节点被访问的前提是:无右子树或右子树已被访问过
    		if (pCur->right == NULL || pCur->right == pLastVisit)
    		{
    			cout << pCur->data;
    			//修改最近被访问的节点
    			pLastVisit = pCur;
    		}
    		else
    		{
    			//根节点再次入栈
    			s.push(pCur);
    			//进入右子树,且可肯定右子树一定不为空
    			pCur = pCur->right;
    			while (pCur)
    			{
    				s.push(pCur);
    				pCur = pCur->left;
    			}
    		}
    	}
    	cout << endl;
    }


    4.层序遍历

    层序遍历的规则是若树为空,则空操作返回,否则从树的第一层,也就是树的根结点开始访问,从上而下逐层遍历,从左到右的顺序对结点逐个访问。如图所示的二叉树遍历的顺序为:ABCDEFGHI。

    仔细看看层序遍历过程,其实就是从上到下,从左到右依次将每个数放入到队列中,然后按顺序依次打印就是想要的结果。

    实现过程
    1、首先将二叉树的根节点push到队列中,判断队列不为NULL,就输出队头的元素,
    2、判断节点如果有孩子,就将孩子push到队列中,
    3、遍历过的节点出队列,
    4、循环以上操作,直到Tree == NULL。
     

    void FloorPrint(tnode* t) //层序遍历_队列实现
    {
    	queue<tnode*> q;
    	if (t != NULL)
    	{
    		q.push(t);   //根节点进队列
    	}
    
    	while (q.empty() == false)  //队列不为空判断
    	{
    		cout << q.front()->data << " → ";
    
    		if (q.front()->left != NULL)   //如果有左孩子,leftChild入队列
    		{
    			q.push(q.front()->left);
    		}
    
    		if (q.front()->right != NULL)   //如果有右孩子,rightChild入队列
    		{
    			q.push(q.front()->right);
    		}
    		q.pop();  //已经遍历过的节点出队列
    	}
    }

     

    展开全文
  • 数据结构~15.使用自定义的栈来优化二叉树的遍历

    万次阅读 多人点赞 2020-08-12 18:44:15
    使用自定义的栈来优化二叉树的遍历 本文是上一篇文章的后续,详情点击该链接~ 前言        在前面遍历二叉树的操作里,基本上都是使用递归实现的,因为递归解决问题的方式会相对...

    使用自定义的栈来优化二叉树的遍历

    本文是上一篇文章的后续,详情点击该链接~

    前言

           在前面遍历二叉树的操作里,基本上都是使用递归实现的,因为递归解决问题的方式会相对循环来说要更加简单一些。但是我们要知道,对于计算机而言,却未必如此。

    递归的缺点

           递归的优点,想必在之前也已经体会到了。使用递归解决问题,往往思路清晰,简单易懂。但是我们要知道,递归在调用的时候会占用大量的系统堆栈,内存耗用非常的多。在递归调用层次多的时候,速度也要比循环慢得多。所以说,在要求高性能的情况下尽量避免使用递归,递归调用既花时间又耗内存。

    优化方案

           我们可以由用户自己定义一个栈来代替系统栈,也就是用非递归的方式来实现遍历算法,这样一来可以得到不小的效率提升。

           那么问题来了。一个是系统栈,而另一个是用户定义的栈。明明都是栈,为什么用户定义的栈会比系统的栈更高效?

           这里的一个解释是递归函数所申请的系统栈,是一个所有递归函数都通用的栈。对于二叉树深度优先遍历算法。系统栈除了记录访问过的结点信息之外,还有其它信息需要记录,以实现函数递归的调用。而用户自己定义的栈,仅保存了遍历所需的节点信息,是对遍历算法的一个针对性的设计,对于遍历算法来说,显然要比递归函数通用的系统栈更高效。

    在这里插入图片描述

    代码实现

    二叉树的结构还是继续使用上篇文章开头图片上的那棵树。

    先序遍历

    void preOrder(Tree *btn) {
    	if (btn != NULL) {
    		//定义一个栈
    		Tree* Stack[MAXSIZE];
    		//初始化栈
    		int top = -1;
    		Tree* p;
    		//根节点入栈
    		Stack[++top] = btn;
    		//栈空循环退出,遍历结束
    		while (top != -1) {
    			//出栈并输出栈顶结点
    			p = Stack[top--];
    			printf("%c ",p->data);
    			//栈是先进后出的,所以先让右孩子进去,再进左孩子
    			//等下出来的时候.就是左孩子先出来,右孩子后出来
    			//栈顶结点的右孩子存在,则右孩子入栈
    			if (p->right != NULL) {
    				Stack[++top] = p->right;
    			}
    			//栈顶结点的左孩子存在,则左孩子入栈
    			if (p->left != NULL) {
    				Stack[++top] = p->left;
    			}
    		}
    	}
    }
    
    我们看到,运行的结果和刚才用笔在本子上分析的一样

    在这里插入图片描述


    中序遍历

           中序遍历和前序遍历差不多。遍历到左孩子最底层之前的结点都会先存入栈内,等遍历到了左孩子最底层结点之后,才会开始出栈进栈的过程。

    void InOrder(Tree *tree) {
    	if (tree != NULL) {
    		Tree* Stack[MAXSIZE];
    		int top = -1;
    		Tree* p;
    		p = tree;
    		//遍历
    		while (top != -1 || p != NULL) {
    			//左孩子入栈
    			while (p != NULL) {
    				Stack[++top] = p;
    				p = p->left;
    			}
    			//栈不空的时候出栈,并输出栈结点
    			if (top != -1) {
    				p = Stack[top--];
    				printf("%c ",p->data);
    				p = p->right;
    			}
    		}
    	}
    }
    

    后序遍历

           在后序遍历操作之前,我们可以先手动写上遍历的结果再进行过程分析

           刚才的先序遍历结果为: A B D H I E J K C F G

           后序遍历的结果为: H I D J K E B F G C A

           后序遍历逆转的结果:A C G F B E K J D I H

           我们仔细观察会发现一个规律。就是当我们把后序遍历的结果倒过来之后就比较像是先序遍历过程中的左右子树顺序交换后的结果。所以,我们只需要将前面的先序遍历算法中的左右子树顺序交换就可以得到逆转后的后序遍历序列。然后再把逆转后的序列逆序也就得到了我们想要的结果。这么做的话,我们就需要两个栈。

           一个栈用来辅助做逆后序遍历,然后将遍历结果的序列压入另一个栈当中。由于栈是先进后出的数据结构,所以只需要按照栈的顺序把它们正常出栈。就得到我们想要的结果了~

    void postOrder(Tree *tree) {
    	if (tree != NULL) {
    		//定义两个栈
    		Tree* Stack1[MAXSIZE]; int top1 = -1;
    		Tree* Stack2[MAXSIZE]; int top2 = -1;
    		Tree* p = NULL;
    		Stack1[++top1] = tree;
    		while (top1 != -1) {
    			p = Stack1[top1--];
    			Stack2[++top2] = p;
    			if (p -> left != NULL) {
    				Stack1[++top1] = p->left;
    			}
    			if (p -> right != NULL) {
    				Stack1[++top1] = p->right;
    			}
    		}
    		while (top2 != -1) {
    			p = Stack2[top2--];
    			printf("%c ",p->data);
    		}
    	}
    }
    

    最后奉上完整代码

    #include<stdio.h>
    #include<stdlib.h>
    #define MAXSIZE 100
    typedef struct BinaryNode {
    	char data;		//数据域
    	struct BinaryNode* left;	//指针域 左孩子
    	struct BinaryNode* right;	//指针域 右孩子
    }Tree;
    //赋值
    Tree* getTree(char data) {
    	Tree* tree = (Tree*)malloc(sizeof(Tree));
    	tree->data = data;
    	tree->left = NULL;
    	tree->right = NULL;
    	return tree;
    }
    //先序遍历
    void preOrder(Tree* btn) {
    	if (btn != NULL) {
    		//定义一个栈
    		Tree* Stack[MAXSIZE];
    		//初始化栈
    		int top = -1;
    		Tree* p;
    		//根节点入栈
    		Stack[++top] = btn;
    		//栈空循环退出,遍历结束
    		while (top != -1) {
    			//出栈并输出栈顶结点
    			p = Stack[top--];
    			printf("%c ", p->data);
    			//栈是先进后出的,所以先让右孩子进去,再进左孩子
    			//等下出来的时候.就是左孩子先出来,右孩子后出来
    			//栈顶结点的右孩子存在,则右孩子入栈
    			if (p->right != NULL) {
    				Stack[++top] = p->right;
    			}
    			//栈顶结点的左孩子存在,则左孩子入栈
    			if (p->left != NULL) {
    				Stack[++top] = p->left;
    			}
    		}
    	}
    }
    //中序遍历
    void InOrder(Tree *tree) {
    	if (tree != NULL) {
    		Tree* Stack[MAXSIZE];
    		int top = -1;
    		Tree* p;
    		p = tree;
    		//遍历
    		while (top != -1 || p != NULL) {
    			//左孩子入栈
    			while (p != NULL) {
    				Stack[++top] = p;
    				p = p->left;
    			}
    			//栈不空的时候出栈,并输出栈结点
    			if (top != -1) {
    				p = Stack[top--];
    				printf("%c ",p->data);
    				p = p->right;
    			}
    		}
    	}
    }
    //后序遍历
    void postOrder(Tree *tree) {
    	if (tree != NULL) {
    		//定义两个栈
    		Tree* Stack1[MAXSIZE]; int top1 = -1;
    		Tree* Stack2[MAXSIZE]; int top2 = -1;
    		Tree* p = NULL;
    		Stack1[++top1] = tree;
    		while (top1 != -1) {
    			p = Stack1[top1--];
    			Stack2[++top2] = p;
    			if (p -> left != NULL) {
    				Stack1[++top1] = p->left;
    			}
    			if (p -> right != NULL) {
    				Stack1[++top1] = p->right;
    			}
    		}
    		while (top2 != -1) {
    			p = Stack2[top2--];
    			printf("%c ",p->data);
    		}
    	}
    }
    
    int main(int argc, char* argv[]) {
    	//搭建图中的二叉树
    	Tree* tree = (Tree*)malloc(sizeof(Tree));
    	tree = getTree('A');
    	tree->left = getTree('B');
    	tree->right = getTree('C');
    	tree->left->left = getTree('D');
    	tree->left->right = getTree('E');
    	tree->left->left->left = getTree('H');
    	tree->left->left->right = getTree('I');
    	tree->left->right->left = getTree('J');
    	tree->left->right->right = getTree('K');
    	tree->right->left = getTree('F');
    	tree->right->right = getTree('G');
    
    	printf("先序遍历结果: "); preOrder(tree);
    	printf("\n\n中序遍历结果: "); InOrder(tree);
    	printf("\n\n后序遍历结果: "); postOrder(tree);
    	getchar();
    	return 0;
    }
    
    展开全文
  • 二叉树的遍历详解

    千次阅读 多人点赞 2019-02-16 19:30:14
    二叉树的遍历是一个很常见的问题。二叉树的遍历方式主要有:先序遍历、中序遍历、后序遍历、层次遍历。先序、中序、后序其实指的是父节点被访问的次序。若在遍历过程中,父节点先于它的子节点被访问,就是先序遍历;...
  • 我是怎么一步一步调试出来二叉树的遍历,二叉树遍历再也不用愁了
  • 二叉树的遍历方式及根据遍历结果还原二叉树1. 二叉树的遍历方式2. 根据遍历结果还原二叉树2.1 已知先序遍历和中序遍历还原二叉树2.2 已知后序遍历和中序遍历还原二叉树 1. 二叉树的遍历方式 二叉树有三种遍历方式...
  • 6.2二叉树的遍历

    千次阅读 2014-10-20 11:10:28
    6.2二叉树的遍历 二叉树的遍历(规定)
  • 二叉树的遍历——层次遍历

    千次阅读 2019-10-13 20:10:19
    上一节:二叉树的遍历——先序遍历、中序遍历、后序遍历 层序遍历是指按层次的顺序从根结点向下逐层进行遍历,且对同一层的结点为从左到右遍历。需要从根结点开始从上往下逐层遍历,而对同一层进行从左到右的遍历。...
  • 二叉树作为最常碰到和最基础的数据结构,今天来聊一聊二叉树的遍历 二叉树的遍历分为深度优先遍历和广度优先遍历,其中,深度优先遍历又分为先序遍历,中序遍历和后序遍历三种。 先,中,后都是根据根节点而言的...
  • 4.3.1二叉树的遍历 二叉树的遍历,是指按某搜索路径访问树中的每个结点,使得每个结点均被访问一次,而且仅被访问一次。 按照先遍历左子树再遍历右子树的原则,常见的遍历次序有先序,中序和后序三种遍历算法。 ...
  • 写在前边的话:你的支持是我写作的动力,...树、森林、二叉树的遍历对应关系 树、森林、二叉树的遍历对应关系 树 森林 二叉树 先序遍历 先序遍历 先序遍历 后序遍历 中序遍历 中序遍历 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,422
精华内容 31,368
关键字:

二叉树的遍历