首页 > 试题广场 >

有如下图所示(左)的一棵二叉树, 请设计一种遍历方式,使得按

[问答题]
有如下图所示(左)的一棵二叉树, 请设计一种遍历方式,使得按照如下方式(右)输出各个元素:(从下到上, 从右到左输出, 要求每层之间换行, 同行元素之间用tab分割,写出完整代码)。
推荐
// 逆序 BFS 搜索
void reverseBFS(Tree *t)
{
	if(NULL == t)
	{
		return;
	}
	vector<vector<char>> vv;
	queue<Tree*> que;
	que.push(t);
	int length = 1;
	while(!que.empty())
	{
		vector<char> v;
		while(length != 0)
		{
			Tree *t = que.front();
			//cout<<t->data<<endl;
			que.pop();
			if(t->left)
			{
				que.push(t->left);
			}
			if(t->right)
			{
				que.push(t->right);
			}
			v.push_back(t->data);
			v.push_back('	');	
			length--;
		}
		v.push_back('\n');
		vv.push_back(v);
		length = que.size();
	}
	//cout<<vv.size()<<endl;
	for (int i = vv.size() - 1; i >= 0; i--)
	{
		vector<char> v = vv[i];
		for(int j = 0; j < v.size(); j++)
		{
			cout<<v[j];
		}
	}
}
编辑于 2015-09-10 14:41:25 回复(0)
void Print(TreeNode *root)
{
    vector<TreeNode*> temp;
    vector<vector<TreeNode*> > result; 
    if (root == NULL)
    {
        return;
    }
    
    queue<TreeNode*> que;
    que .push(root);
    int toPrintnum = 1;
    int curnum = 0;
    while (!que.empty())
    {        
        TreeNode *node = que.front();
        temp.push_back(node);
        que.pop();
        toPrintnum--;
        if (node->left != NULL)
        {
            que.push(node->left);
            curnum++;
        }
        if (node->right != NULL)
        {
            que.push(node->right);
            curnum++;
        }
        if (toPrintnum==0)
        {
            result.push_back(temp);
            temp.clear();
            toPrintnum = curnum;
            curnum = 0;
        }
    }
    for (int i = result.size()-1; i >=0; i++)
    {
        for (int j = 0; j < result[i].size(); j++)
        {
            cout << result[i][j] << '\t';
        }
        cout << endl;
    }
}
发表于 2015-05-29 15:26:47 回复(0)
object Test extends App {
  val queue = new LinkedList[Node]
  val stack = new Stack[String]
  queue.add(root) // 假设持有根节点的引用root
  while (!queue.isEmpty) {
    for (i <- 0 until queue.size) {
      val node = queue.poll
      stack.add(node.toString() + "\t")
      if (node.left != null)  queue add node.left
      if (node.right != null) queue add node.right
    }
    stack.add("\r\n")
  }
  stack.foreach(x => print(x))
}


发表于 2014-12-31 00:55:51 回复(1)
有必要那么复杂吗??

'''
Created on Dec 30, 2014

@author: ScottGu<gu.kai.66@gmail.com, 150316990@qq.com>
'''
# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param root, a tree node
    # @return a list of lists of characters
    def levelOrder(self, root):
        if(root==None): return []
        rslt=[]
        theLevel=[]
        theLevel.append(root)
        while(len(theLevel)>0):
            rslt.append(theLevel[:]) # deep copy current level
            # foreach and save next level
            cnt= len(theLevel)
            for ix in range(cnt):
                if(theLevel[0].left!=None):  
                    theLevel.append(theLevel[0].left)
                    theLevel.append('\t')
                if(theLevel[0].right!=None): 
                    theLevel.append(theLevel[0].right)
                    theLevel.append('\t')
                theLevel.pop(0) # remove 1 from this level     
            theLevel.append('\n') # Don't forget to add a line breaker
        return rslt[::-1]

发表于 2014-12-30 23:56:35 回复(3)
public class Test {
     public static void main(String[] args) {    
         Queue<MyNode> queue = new LinkedList<MyNode>();
         queue.add(new MyNode(root, 0));
         Stack<MyNode> stack = new Stack<MyNode>();
         int preLevel = stack.peek().level;
         while (!stack.isEmpty()) {
             if (stack.peek().level != preLevel) {
                 System.out.println();
                 preLevel = stack.peek().level;
             }
             System.out.print(stack.pop().node + "\t");
         }
     }
     
     public static void travers(Queue<MyNode> queue,Stack<MyNode> stack) {
         if (queue.peek() == null) return;
         MyNode mynode = queue.poll();
         if (node.left != null) {
             queue.add(new MyNode(mynode.node.left, mynode.node.level +1));    
         }
         if (node.right != null) {
              queue.add(new MyNode(mynode.node.right, mynode.node.level+ 1));
         }
         stack.push(mynode)
     }
 }

 class MyNode {
     public Node node;
     int level;
     public MyNode(Node node, int level) {
         this.node = node;
         this.level = level;
     }
 }

编辑于 2015-09-10 14:39:37 回复(0)