首页 > 代码库 > DSA——二叉树笔记
DSA——二叉树笔记
几个总忘的点儿：
结点的深度：一个结点向上移动到其父节点——是一步，再移动到父结点的父结点——是两步，移动到了根结点——结点的深度
树的深度：所有叶子结点的最大深度
数组存储完全二叉树：某个Node在数组中的位置为[i],其父结点则是在[(i-1)/2],其两个孩子则是[2i+1],[2i+2]
树的遍历：前中后广
前序遍历-递归【根左右】
protected void preOder(BinTreeNode root)
{
if(root!=null)
visit();//①
preOrder(root.left); //②
preOrder(root.right); //③
}
中序遍历-递归【左根右】②①③
后序遍历-递归【左右根】②③①
//很显然，重头戏是 非递归------使用栈帮忙【使得效率并没有改进多少，在使用栈的过程中每次while都需要push,pop分别两次】
前序遍历-非递归_1
【visit()必须在pop()后,pop()必须在两次push()前面，显然，visit()和两次push()的先后关系没什么必要】
【记得，访问必须在子女压栈之前】
- 维护一个栈，将根节点入栈，然后只要栈不为空，出栈并访问，接着依次将访问节点的右节点、左节点入栈。
- 这种方式应该是对先序遍历的一种特殊实现（看上去简单明了），但是不具备很好的扩展性，在中序和后序方式中不适用
public void iterativePreOrder_1(BinTreeNode root)
{
BinTreeNode p=root;
Stack<BinTreeNode> stack=new Stack<BinTreeNode>();
if(p!=null)
{
stack.push(p);
while(!stack.isEmpty())
{
p=stack.pop();
visitNode(p);
if(p.right!=null)
stack.push(p.right);
if(p.left!=null)
stack.push(p.left);//left后于right入栈，为了保持在栈顶先访问
}
}
前序遍历-非递归_2
- 利用栈模拟递归过程实现循环先序遍历二叉树
- * 这种方式具备扩展性，它模拟递归的过程，将左子树点不断的先访问再压入栈，直到null，然后处理栈顶节点的右子树
public void iterativePreOrder_2(BinTreeNode root){
if(root==null)return;
Stack<BinTreeNode> s=new Stack<BinTreeNode>();
while(root!=null||!s.isEmpty()){
while(root!=null){
visitNode(p);
s.push(root);//先访问再入栈
root=root.left;
}
root=s.pop();
root=root.right;//如果是null，出栈并处理右子树
}
}
中序遍历---非递归【思想同前序2】
public void iterativeInOrder(BinTreeNode root)
{
if(root==null)return;
BinTreeNode p=root;
Stack<BinTreeNode> stack=new Stack<BinTreeNode>();
while(!stack.isEmpty()||p!=null)
{
while(p!=null)
{
stack.push(p);
root=root.left;
}
p=stack.pop();
visitNode(p);
p=p.right;
}
}
后序---非递归【又不一样了，参考数据结构C++】
public void iterativePostOrder(BinTreeNode root)
{
if(root==null)return;
BinTreeNode p=root;
BinTreeNode prev=root;//保存上一个刚被访问的结点
Stack<BinTreeNode> stack=new Stack<BinTreeNode>();
while(p!=null)
{
for(;p.left!=null;p=p.left)//不断向左搜索，压栈
stack.push(p);
while(p!=null&&(p.right==null||p.right==prev))//当前结点没有右孩子或者右孩子刚刚被访问过
{
visitNode(p);//就访问这个结点
prev=p;//访问后别忘了置为上一个被访问的结点
if(stack.isEmpty())
return;
p=stack.pop();
}
stack.push(p);//有右孩子的时候，先把自己压栈
p=p.right;//再找自己的右子树
}}
最后一个--广度优先遍历
- /**
- *
- * @param root 树根节点
- * 层序遍历二叉树，用队列实现，先将根节点入队列，只要队列不为空，然后出队列，并访问，接着讲访问节点的左右子树依次入队列
- */
public static void levelTravel(BinTreeNode root){
if(root==null)return;
BinTreeNode p=root;
Queue<BinTreeNode> queue=new LinkedList<BinTreeNode>();
queue.add(p);
while(!queue.isEmpty())
{
p=queue.poll();
visitNode(p);
if(p.left!=null) queue.add(p.left);
if(p.right!=null) queue.add(p.right);
}
}
参考博客：http://blog.csdn.net/kerryfish/article/details/24309617
DSA——二叉树笔记
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。