首页 > 代码库 > 编程之美问题之二叉树层序遍历多种解法

编程之美问题之二叉树层序遍历多种解法

2024-07-06 17:27:09   221人阅读

二叉树的层序遍历(要求区分层，例如每层遍历完输出换行)


单单层序遍历非常简单，一个队列就搞定了，但是区分层则要麻烦些。总的思路无非就是在每次print的时候，要能通过某个东西
区分出当前节点是否是一层最后一个节点，或者下一层的最后一个节点，感觉有点类似于机器学习中找个区分度明显的特征：


1.自己的解法，在单队列基础上，输入队列的数据添加一个标志 ，LevelHeaded，同时，在后面插入两个孩子的时候，判断是否这次输出的是队头，如果是的话，先插
个队头标志，再插入孩子，而且插入一次之后，后面不能插入，用LevelFirst布尔变量来控制。


代码如下
void LevelOrder(node* p)
{
	Queue<node *> Q;
	Bool LevelFirst=false;
	Q.Enqueue(root);
	while(quene is not empyty)
	{
		Q.Dequeue(p);
		if(q==LevelHead)
		{
			p=Q.Dequeue(p);
			LevelFirst=true;
			cout<<endl;
			cout<<q->data;
		}
		else
		{
			cout<<q->data;
		}
		
		if(p->left)
		{
			if(LevelFirst=true)
			{
				Q.Enqueue(LevelHead);LevelFirst=False;
			}
			Q.Enqueue(p->left);
		}
		if(p->right)
		{
			if(LevelFirst=true)
			{
				Q.Enqueue(LevelHead);LevelFirst=False;
			}
			Q.Enqueue(p->right);
		}
	}
}




2.编程之美解法：


解法1：指示当前层的结束位置，判读当前index是否等于结束位置，使用vector来实现。并且里面两重循环，里层表示一层结点的处理，外层表示整个的处理
void PrintNodeByLevel(Node* root) {
     vector<Node*> vec; // 这里我们使用STL 中的vector来代替数组，可利用到其动态扩展的属性
     vec.push_back(root);
     int cur = 0;
     int last = 1;
     while(cur < vec.size()) {
          Last = vec.size(); // 新的一行访问开始，重新定位last于当前行最后一个节点的下一个位置
          while(cur < last) {
               cout << vec[cur] -> data << " "; // 访问节点
               if(vec[cur] -> lChild) // 当前访问节点的左节点不为空则压入
                   vec.push_back(vec[cur] -> lChild);
               if(vec[cur] -> rChild) // 当前访问节点的右节点不为空则压入，注意左右节点的访问顺序不能颠倒
                   vec.push_back(vec[cur] -> rChild);
               cur++;
          }
          cout << endl; // 当cur == last时,说明该层访问结束，输出换行符
     }
}




解法2：先解决访问每层结点，然后遍历层，前提还要知道树高，不过后面发现可以通过前面函数返回状态值免除求树高的过程
再次不赘述，树高也可以用递归来求解


3.某人博客：http://blog.csdn.net/cnclenovo/article/details/17513821
解法1：用两个队列，将取出队列和插入两个儿子到队列分开到两个队列里的操作。


然后一层结束标志是取元素队列为空，然后与下一个队列交换内容，实质是交换指针，Mileho是这么解释的.


解法2：记录当前层在队列中的节点数NodesInCurrentLevel，以及下一层在队列的节点数NodesInNextLevel，判断Current变量是否为0来区分层结束


4.Mileho博客：http://www.cnblogs.com/miloyip/archive/2010/05/12/binary_tree_traversal.html
这个链接还上了编程之美书：


解法1：同上面某人博客解法1，其实应该是这个时间早
解法2：和我的思路一致，加入一个层结束标志，但是程序的逻辑设计的比我的beautiful，少一个bool变量，而且看起来程序短。


void PrintNodeByLevel(Node* root) {
    queue<Node*> Q;
    Q.push(root);
    Q.push(0);
    do {
        Node* node = Q.front();
        Q.pop();
        if (node) {
            cout << node->data << " ";
            if (node->pLeft)
                Q.push(node->pLeft);
            if (node->pRight)
                Q.push(node->pRight);
        }
        else if (!Q.empty()) {
            Q.push(0);
            cout << endl;
        }
    } while (!Q.empty());
}




总结：1 实现queue的时候，都不是node类型，而是node* 类型，这样插入LevelHead标志都会比较方便，而且当swap两个队列空间复杂度为O(1)，之前老师教的时候
好像都没太注意这个地方
 2.单队列实现，空间复杂度O(n) 具体为最大长度为结点数最多的一层的结点数，n个节点最大值为(n+1)/2
 3.遇到问题，首先是大致思路，确定下来后，设计需要的变量，小心设计逻辑，这里的思路里面  区分层有点类似于ML中的找特征

 4.思路正确，代码逻辑不一定正确，20 80原理


另外看到还有一个求十进制表示的二进制数的1的位数，Hamming_weight，也才知道还有个名词


联系
我们