0809-二叉树层次遍历

第一题：

struct node_t

{

    node_t *left, *right;

    int value;

};

要求编写函数 node_t* foo(node_t *node, unsigned int m, unsigned int k);

输出以 node 为根的二叉树第 m 层的第 k 个节点值.

(level, k 均从 0 开始计数)

注意：

此树不是完全二叉树；

所谓的第K个节点，是本层中从左到右的第K个节点

 

------------------------------------------------------------

第二题：

求二叉树的宽度和高度

 

package org.jyjiao;


class BiNode {
	int data;
	BiNode leftChild;
	BiNode rightChild;

	public BiNode getLeftChild() {
		return this.leftChild;
	}

	public BiNode getRightChild() {
		return this.rightChild;
	}

	public void setLeftChild(BiNode leftChild) {
		this.leftChild = leftChild;
	}

	public void setRightChild(BiNode rightChild) {
		this.rightChild = rightChild;
	}

	public int getData() {
		return data;
	}

	public void setData(int data) {
		this.data = data;
	}

}

public class BiTree1 {
	int num;
	BiNode root;

	public BiTree1(int num) {
		this.num = num;
	}

    /*
    * createTree()--创建一颗二叉树
    */
	public BiNode createTree() {
		BiNode[] queue = new BiNode[num];
		int front = 0, rear = 0, last = 0;
		int i = 0;
		BiNode root = new BiNode();
		root.setData(i);
		root.setLeftChild(null);
		root.setRightChild(null);
		queue[rear++] = root;

		while (i < num) {
			BiNode node = queue[front++];
			// System.out.print("parant:"+node.getData());
			int ldata = ++i;
			if (ldata < num) {
				BiNode lchild = new BiNode();
				lchild.setData(ldata);
				lchild.setLeftChild(null);
				lchild.setRightChild(null);
				queue[rear++] = lchild;
				node.setLeftChild(lchild);
				// System.out.print("lchild:"+lchild.getData());
			}

			int rdata = ++i;
			if (rdata < num) {
				BiNode rchild = new BiNode();
				rchild.setData(rdata);
				rchild.setLeftChild(null);
				rchild.setRightChild(null);
				queue[rear++] = rchild;
				node.setRightChild(rchild);
				// System.out.print("rchild:"+rchild.getData()+"\n");
			}
		}
		return root;
	}

	
	/*
	 * public void visitTree(BiNode root) -- 求二叉树的高度和宽度
	 * 输入：二叉树的根节点
	 * 打印：二叉树的高度和宽度
	 * front：已经出队的节点个数
	 * last：本层最右边的元素为二叉树的第几个元素
	 * rear：下层当前的入队元素个数
	 */
	public void visitTree(BiNode root) {
		int front = 0, rear = 0, last = 1;
		int curWith = 0;
		int maxWith = 0;
		int hight = 0;
		BiNode[] queue = new BiNode[num];
		if (root == null) {
			System.out.println("tree is null");
		} else {
			queue[0] = root;
			rear++;
			while (front != rear) {
				BiNode node = queue[front++];
				// System.out.println("out:"+node.getData());
				curWith++;
				if (node.getLeftChild() != null) {
					queue[rear++] = node.getLeftChild();
				}
				if (node.getRightChild() != null) {
					queue[rear++] = node.getRightChild();
				}
				if (front >= last) {

					if (curWith > maxWith) {
						maxWith = curWith;
					}
					hight++;
					last = rear;
					curWith = 0;
				}

			}
			System.out.println("with=" + maxWith + "，hight=" + hight);
		}

	}

	public static void main(String[] args) {
		BiTree1 tree = new BiTree1(4);
		BiNode root = tree.createTree();
		tree.visitTree(root);
	}

}