树和图

树和图

　　

1. 树的遍历

说起树的遍历那肯定就会有两种实现方法：递归和迭代。以前序为例就来小说几句好了：

前序的遍历顺序是：根，左子树，右子树。

递归：

先遍历根节点，

然后遍历左子树，

之后遍历右子树。

void preorderTravelsal(Node root){

if( root = null) return;

root.printValue();

preorderTravelsal(root.getLeft());

preorderTravelsal(root.getRight());

}

迭代（使用栈）

创建栈

将根节点压入栈中

while栈非空

弹出一个节点，并输出他的值

If 弹出节点有右子节点，将右子节点压入栈

If 弹出接点有左子节点，将左子节点压入栈

void preorderTravelsal(Node root){

NodeStack stack = new NodeStack();'

stack.push(root);

while( stack.size() > 0){

Node curr = stack.pop();

curr.printValue();

Node n =  curr.getRight();

if (n != null) stack.push(n);

n = curr.getLeft();

if(n != null) stack.push(n);

}

}

2. 树的高

很明显要用递归咯，树的高等于其最高子树的高加一。

3. 二叉搜索树最近共同祖先

一种思路：将两个节点都生成其所有祖先节点的链表，然后在这两个链表中搜索，找到第一个不同的节点的前一个节点即是所求。
另一种思路：二叉搜索树的做子树的节点的值都小于根节点，右子树的节点的值都大于根节点。

If value1 和value2都小于当前节点的值

检查左子节点

If value1和value2都大于当前节点的值

检查右子节点

否则 当前节点就是所求节点

4. 二叉树转堆

题目：给定一个存储于无序的二叉树中的整数集合。使用数组排序算法将这个树转化成为一个堆，这个堆使用的是平衡二叉树的结构。

总体思路   二叉树->数组->堆

新建一个节点对象数组

遍历二叉树将节点存储到数组中

对数组进行排序

For 每个i节点

Left = 2 * i +1

Rigjt = left + 1

If left长度小于数组长度，设置对应的Left节点为左子节点

If right长度小于数组长度，设置对应的right节点为右子节点。