按层次遍历二叉树

小咪咪 2022-08-02 09:59 246阅读 0赞

前序遍历

前序遍历也叫做先根遍历，可记做根左右。

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子

树，最后遍历右子树。遍历左右子树时仍然采用前序遍历方法。

中序遍历

中序遍历也叫做中根遍历，可记做左根右。

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结

点，最后遍历右子树。遍历左右子树时仍然采用中序遍历方法。

后序遍历（LRD）

后序遍历也叫做后根遍历，可记做左右根。

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子

树，最后访问根结点。遍历左右子树时仍然采用后序遍历方法。

如下图：

![Center][]

先序输出:  
A B D G H E C K F I J  
中序输出:  
G D H B E A K C I J F  
后序输出:  
G H D E B K J I F C A

已知一棵二叉树的先序遍历序列和中序遍历序列分别是abdgcefh、dgbaechf，求二叉树及后序遍历序列

编写按层次顺序（同一层自左至右）遍历二叉树的算法。

#include "stdafx.h"
    #include<iostream>    
    #include<vector>  
    
    using namespace std;
    
    
    struct BiNOde
    {
    	int ele;
    	BiNOde* lnode;
    	BiNOde* rnode;
    };
    
    vector<vector<int>>aa;
    BiNOde*p;
    BiNOde*root;
    
    
    
    void findparent(BiNOde*node, BiNOde*parent)
    {
    	if (parent == NULL)
    		return;
    	if (parent->lnode == node || parent->rnode == node)
    	{
    		p = parent; 
    		return;
    	}
    	findparent(node, parent->lnode);
    	findparent(node, parent->rnode);
    }
    
    int depth_of_node(BiNOde*node)
    {
    	int k = 0;
    	if (node == root)
    		return 0;
    	BiNOde*n = node;
    	while (n != root)
    	{
    		findparent(n, root);
    		n = p;
    		k++;
    	}
    
    	return k;
    }
    
    void PreOrderTraverse(BiNOde*node)
    {
    	if (node == NULL)
    		return;
    	int d = depth_of_node(node);
    	if (d + 1 > aa.size())
    	{
    		vector<int>a;
    		a.push_back(node->ele);
    		aa.push_back(a);
    	}
    	else
    	{
    		vector<int>a=aa[d];
    		a.push_back(node->ele);
    		aa[d] = a;
    	}
    	if (node->lnode != NULL)
    		PreOrderTraverse(node->lnode);
    	if (node->rnode != NULL)
    		PreOrderTraverse(node->rnode);
    
    }
    
    BiNOde*create_tree()
    {
    	BiNOde * root = new BiNOde;
    	BiNOde*node1 = new BiNOde;
    	BiNOde*node2 = new BiNOde;
    	BiNOde*node3 = new BiNOde;
    	BiNOde*node4 = new BiNOde;
    	BiNOde*node5 = new BiNOde;
    	BiNOde*node6 = new BiNOde;
    	BiNOde*node7 = new BiNOde;
    	BiNOde*node8 = new BiNOde;
    	BiNOde*node9 = new BiNOde;
    	BiNOde*node10 = new BiNOde;
    	BiNOde*node11 = new BiNOde;
    	root->ele = 0;
    	node1->ele = 1;
    	node2->ele = 2;
    	node3->ele = 3;
    	node4->ele = 4;
    	node5->ele = 5;
    	node6->ele = 6;
    	node7->ele = 7;
    	node8->ele = 8;
    	node9->ele = 9;
    	node10->ele = 10;
    	node11->ele = 11;
    	root->lnode = node1;
    	root->rnode = node2;
    	node1->lnode = node3;
    	node1->rnode = node4;
    	node2->lnode = node7;
    	node2->rnode = node8;
    	node3->lnode = node5;
    	node3->rnode = node11;
    	node4->lnode = node10;
    	node4->rnode = NULL;
    	node5->lnode = node6;
    	node5->rnode = NULL;
    	node6->lnode = NULL;
    	node6->rnode = NULL;
    	node7->lnode = node9;
    	node7->rnode = NULL;
    	node8->lnode = NULL;
    	node8->rnode = NULL;
    	node9->lnode = NULL;
    	node9->rnode = NULL;
    	node10->lnode = NULL;
    	node10->rnode = NULL;
    	node11->lnode = NULL;
    	node11->rnode = NULL;
    	//BiNOde*node12 = new BiNOde;    
    	//node12->ele = 12;    
    	//node12->lnode = NULL;    
    	//node12->rnode = NULL;    
    	//node6->lnode = node11;    
    	
    	return root;
    }
    int _tmain(int argc, _TCHAR* argv[])
    {
    	root = create_tree();
    	PreOrderTraverse(root);
    
    	system("pause");
    	return 0;
    }

先序遍历一遍tree，同一深度的节点访问的顺序虽然不是连续的，但是却满足从左到右的顺序，只需将同以深度的节点依次存到一个数组即可。

在main函数的system("pause")这一句设置断点，将全局变量aa添加监视，运行到system这一句暂停的时候观察aa中存放的数据，结果正确。

[Center]: /images/20220731/0e3472cb61364955940b7ffd72cb3179.png