摘要：实现基本数据结构栈，队列，链表这篇笔记侧重点二叉树的三种遍历前中后迭代非迭代代码重建二叉树的代码与分析和关于二叉树的题简单理解二叉查找树红黑树，的性质，实际用途。同时，以对应的节点为边界，就会把中序遍历的结果分为左子树和右子树。
虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/
.. 拒绝伸手复制党
以下是算法导论第十章的学习笔记 即 剑指offer题目
剑指offer电子书 见我的github https://github.com/GsmToday/JianZhi-offer/tree/master
前面总结了，栈，队列，链表。 Java 实现基本数据结构 1（栈，队列，链表）
这篇笔记侧重点：
1 二叉树的三种遍历（前中后）迭代非迭代代码
2 重建二叉树的代码与分析 和 关于二叉树的题 简单理解
3 二叉查找树, 红黑树，Btree的性质，实际用途。比如hashmap用到了红黑树
二叉树最重要的操作某过于遍历，namely 按照某一顺序访问树中的所有节点。
通常有四种遍历方式：
深度优先：
- 前序遍历 （根-左-右）10,6,4,8,14,12,16
用途：1 拷贝树。 2 计算前缀表达式
- 中序遍历 （左-根-右）4,6,8,10,12,14,16
用途：BST（二叉搜索树）的中序遍历以非降序方式输出节点。
- 后序遍历 （右-左-根）4,8,8,12,16,14,10
后序遍历的用途：1 删除树 2 计算后缀表达式
2. 广度优先：
- 层序遍历
二叉树的遍历时间复杂度，无论递归与否，方式与否，都是O(n). 这是因为每个算法都要遍历每个节点仅仅一次。
1.2代码 前序遍历（递归）java public static void preOrderTraverse(Treenode rootnode){
Treenode p = rootnode;
if(p!=null){
System.out.println(p.value);
preOrderTraverse(p.leftchild);
preOrderTraverse(p.rightchild);
}
else return;
}
前序遍历（非递归）
树的深度优先遍历，因为没有parent指针，所有非递归形式一定要借助栈；相反，如果二叉树的节点有parent指针，那么就不需要栈了。
先让根进栈。只要栈不为空，就可以弹栈。每次弹出一个节点，要把它的左右节点进栈（右节点先进栈）。
java public static void preOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Treenode p = rootnode;
Stack stack = new Stack();
stack.push(p);
while(stack.isEmpty()!=true){
p = stack.pop();
System.out.println(p.value);
if(p.rightchild != null ){
stack.push(p.rightchild);
}
if(p.leftchild != null){
stack.push(p.leftchild);
}
}
}
中序遍历（递归）
java public static void inOrderTraverse(Treenode rootnode){
Treenode p = rootnode;
if(p!=null){
inOrderTraverse(p.leftchild);
System.out.println(p.value);
inOrderTraverse(p.rightchild);
}
else return;
}
中序遍历（非递归）:
current = root;
把current, current的左孩子，current的左孩子的左孩子都入栈,直至current = null -> 跳到step 3
（current = current.left, push(current)）
若current = null 且栈没空，则弹栈，并访问。current = 弹出的节点的右孩子 <- 十分重要，之后重复2。
geeksforgeeks思路参照link
java public static void inOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Treenode current = rootnode;
Stack stack = new Stack();
while(current != null||stack.isEmpty()!=true){
while(current!=null){
stack.push(current);
current = current.leftchild;
}
if(current==null){
Treenode node = stack.pop();
System.out.println(node.value);
current = node.rightchild;
}
}
}
后序遍历（递归)
java public static void postOrderTraverse(Treenode rootnode){
Treenode p = rootnode;
if(p!=null){
postOrderTraverse(p.leftchild);
postOrderTraverse(p.rightchild);
System.out.println(p.value);
}
else return;
}
后序遍历（非递归）
1.1 创建一个空栈
2.1 当current is not null
a) 先右孩子进栈，然后current进栈
b) 设置current为左孩子
这样从根节点，down to 最左孩子节点。最后current == null
2.2 出栈，设置出栈的节点为current
既然出栈了，该节点肯定没有左孩子。
a) 如果出栈节点存在右孩子
并且 右孩子是栈顶^1（这个是必要的，原因下面讲）
并且 栈不为空 ^2（这个是必要的，原因下面讲）,
则 再弹栈（弹出右孩子），把current指向的刚刚出栈的节点（右孩子的爹）入栈。
设置 current = current.right;
b) 如果出栈节点不存在右孩子，那么就可以访问之。记得设置current = null
2.3 重复 2.1 and 2.2 直到栈空.
^1 请看例子：
如果current指向6，他存在右孩子，但是这个时候他的孩子节点都已经访问完毕，没必要再把8入栈。所以要判断。
^2 判断条件2出现在遍历根节点的时候，因为访问一个节点的时机必是弹栈之后，当根节点弹栈之后，栈已空，所以stack.peek（）会报错。
geeksforgeeks思路参照link
java public static void postOrderNonrecur(Treenode rootnode){
if(rootnode==null){
return;
}
Stack stack = new Stack();
Treenode current = rootnode;
while(current !=null || stack.isEmpty()!=true){
//step 1
while(current!=null){
if(current.rightchild!=null){
stack.push(current.rightchild);
}
stack.push(current);
current = current.leftchild;
}
// step2 既然出栈了，该节点肯定没有左孩子。
current = stack.pop();
if(current.rightchild!=null && !stack.isEmpty() && current.rightchild == stack.peek()) {
stack.pop(); //出栈右孩子
stack.push(current);
current = current.rightchild;
}
else{
System.out.println(current.value);
current = null;
}
}
}
层序遍历（递归）
先介绍下如何计算树的高度
树的高度的定义："height of the root"
节点高度的定义："number of edges in longest path from the node to a leaf node". 如：叶子节点的高度是0.
计算高度的时候，利用递归,从父节点到子节点，直至叶子节点，设置叶子节点的高度是0。再从叶子回到父节点，直至跟根节点，height(parentnode) = max(height(left),height(son))+1
节点深度的定义："number of edges in path from root to that node"
java public static int height(Treenode rootnode){
if(rootnode == null){
return -1;
}
int lheight = height(rootnode.leftchild); 计算该节点左孩子的高度
int rheight = height(rootnode.rightchild); 计算该节点右孩子的高度
return Math.max(lheight, rheight)+1; 返回给该节点自己的高度
}
贴的是我在leetcode AC 的代码
javapublic class Solution {
public List> levelOrder(TreeNode rootnode) {
List> resultlist = new ArrayList>();
for(int level = 0; level<= height(rootnode);level++)
{
List list = new ArrayList();
printGivenLevel(rootnode,level,list);
resultlist.add(list);
}
return resultlist;
}
public int height(TreeNode rootnode){
if(rootnode==null){
return -1;
}
else{
return Math.max(height(rootnode.left),height(rootnode.right))+1;
}
}
public void printGivenLevel(TreeNode rootnode, int level, List list){
if(rootnode==null){
return;
}
if(level == 0){
list.add(rootnode.val);
}
else{
printGivenLevel(rootnode.left, level-1, list);
printGivenLevel(rootnode.right, level-1, list);
}
}
}
思路参照
层序遍历（非递归）无论是树，还是图的广度优先遍历，都要使用先进先出的队列结构。
步骤：
1. 创建队列
2. tempnode = root
3. tempnode 不是 null时候循环
a） 输出tempnode.value
b) 将tempnode的孩子入队（先左后右）
c) 出队，把出队的值赋予tempvalue
java public static void LevelOrderNonRecur(Treenode rootnode){
Treenode tempnode = rootnode;
ArrayDeque queue=new ArrayDeque();
if(rootnode==null){
return;
}
queue.add(tempnode);
while(queue.isEmpty()!=true){
tempnode = queue.remove();
System.out.println(tempnode.value);
if(tempnode.leftchild!=null)
queue.add(tempnode.leftchild);
if(tempnode.rightchild!=null)
queue.add(tempnode.rightchild);
}
}
2 二叉树的题
2.1 线性时间判断一个树是否是平衡二叉树：
最直接的方法是遍历树的每个节点的时候，调用函数的TreeDepth得到他的左右节点的高度，如果每个节点的左右子树的高度相差不超过 1. 则它就是一颗平衡二叉树。
但是在计算一个节点的深度的时候，就把该节点和该节点level以下的所有节点都遍历了。 因此，一个节点会被重复遍历多次，这种思路的时间效率不高。所以，效率更高的做法是在计算高度的时候，边计算边判断。
思路参考
java private int getHeight(TreeNode root) {
if (root == null) return 0;
int depL = getHeight(root.left);
int depR = getHeight(root.right);
if (depL < 0 || depR < 0 || Math.abs(depL - depR) > 1) return -1; 返回给该节点自己的value
else return Math.max(depL, depR) + 1; 返回给该节点自己的value
}
public boolean isBalanced(TreeNode root) {
return (getHeight(root) >= 0);
}
2.2 输入两棵二叉树A，B，判断B是不是A的子结构。
java //遍历Tree1,查找与Tree2 root相同的节点
boolean HasSubtree(TreeNode root1, TreeNode root2){
boolean result = false;
if(root1 != null && root2 != null){
if(root1.val == root2.val){
//查找到与Tree2 root相同的节点，接着判断二者是否具有相同结构
result = DoesTree1hasTree2(root1,root2);
}
if(result != true)
result = HasSubtree(root1.left, root2);
if(result != true)
result = HasSubtree(root1.right, root2);
}
return result;
}
java boolean DoesTree1hasTree2(TreeNode root1, TreeNode root2){
boolean lflag = false;
boolean rflag = false;
//Tree2结束
if(root2==null){
return true;
}
//Tree2有节点时候，Tree1还有，说明肯定不是包含关系
if(root1==null){
return false;
}
if(root1.val != root2.val){
return false;
}
else{
lflag = DoesTree1hasTree2(root1.left,root2.left);
rflag = DoesTree1hasTree2(root1.right,root2.right);
return lflag && rflag;
}
}
2.3 输入某二叉树的前序遍历和中序遍历结果，请重建二叉树 ，假设前序遍历和中序遍历中不含重复数字。
思路： 前序遍历的每一个节点都是当前子树的根节点。同时，以对应的节点为边界，就会把中序遍历的结果分为左子树和右子树。
java public static TreeNode buildTree(int[] preOrder,int start, int[] inOrder,
int end,int length){
// 边界验证
if (preOrder == null || preOrder.length == 0 || inOrder == null
|| inOrder.length == 0 || length <= 0) {
return null;
}
//根据 前序遍历的第一个元素建立树根节点
int value = preOrder[start];
TreeNode root = new TreeNode();
root.val = value;
// 递归终止条件：子树只有一个节点
if (length == 1)
return root;
// 根据 前序遍历的第一个元素在中序遍历中的位置分拆树的左子树和右子树
int i = 0;
while (i < length) {
if (value == inOrder[end - i]) {
break;
}
i++;
}
// 建立子树的左子树
root.left = buildTree(preOrder, start + 1, inOrder,
end - i - 1, length - 1 - i);
// 建立子树的右子树
root.right = buildTree(preOrder, start + length - i,
inOrder, end, i);
return root;
}
2.3.1 根据中序+后序遍历结果重构二叉树
java public static TreeNode buildTree(int postOrder[], int pend, int inOrder[],int iend, int length){
//boundary test
if(postOrder == null || postOrder.length == 0 || inOrder == null || inOrder.length == 0 || postOrder.length != inOrder.length)
{
System.out.print("te");
return null;
}
//create root;
TreeNode root = new TreeNode();
int value = postOrder[pend];
root.val = value;
if(length ==1)
return root;
// search the index of the root in inorder
int i =0;
while(inOrder[iend-i]!=value){
i++;
}
root.right = buildTree(postOrder, pend-1, inOrder, iend, i);
root.left = buildTree(postOrder, pend-i-1, inOrder, iend-i-1, length-i-1);
return root;
}
2.4 二叉树中和位某一值的所有路径
java private static Stackstack=new Stack (); public static void findPathk(TreeNode root,int k,int sum){ boolean isLeaf = false; // 为了追溯路径，需要记住栈记录父节点 stack.push(root); // 记录路径的sum sum = root.val + sum; // 判断是否路径到头 if(root.left == null && root.right==null){ isLeaf = true; } // 路径到头且和达到k if(isLeaf && sum ==k){ System.out.println(stack); } // 左子树 if(root.left != null){ findPathk(root.left,k,sum); } // 右子树 if(root.right != null){ findPathk(root.right,k,sum); } // 出栈 stack.pop(); }
想更一进步的支持我，请扫描下方的二维码，你懂的~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64291.html
摘要：有网友私信我，期待我的下一篇数据结构。前言数据结构与算法专题会不定时更新，欢迎各位读者监督。本文介绍数据结构里一些复杂的数据结构树，相应的会补充一些算法。除根节点外，每个节点又可以分为多个不相交的子树。 声明：码字不易，转载请注明出处，欢迎文章下方讨论交流。有网友私信我，期待我的下一篇数据结构。非常荣幸文章被认可，也非常感谢你们的监督。 前言：Java数据结构与算法专题会不定时更新，欢...
摘要：结构型模式适配器模式桥接模式装饰模式组合模式外观模式享元模式代理模式。行为型模式模版方法模式命令模式迭代器模式观察者模式中介者模式备忘录模式解释器模式模式状态模式策略模式职责链模式责任链模式访问者模式。 主要版本 更新时间 备注 v1.0 2015-08-01 首次发布 v1.1 2018-03-12 增加新技术知识、完善知识体系 v2.0 2019-02-19 结构...
摘要：一名年工作经验的程序员应该具备的技能，这可能是程序员们比较关心的内容。数据结构和算法分析数据结构和算法分析，对于一名程序员来说，会比不会好而且在工作中能派上用场。 一名3年工作经验的Java程序员应该具备的技能，这可能是Java程序员们比较关心的内容。我这里要说明一下，以下列举的内容不是都要会的东西—-但是如果你掌握得越多，最终能得到的评价、拿到的薪水势必也越高。 1、基本语法 这包括...
摘要：很多文章或书籍在介绍红黑树的时候直接上来就是红黑树的个基本性质插入删除操作等。这也不奇怪，算法的作者就是红黑树的作者之一。所以，理解树对掌握红黑树是至关重要的。 本文主要包括以下内容： 什么是2-3树 2-3树的插入操作 红黑树与2-3树的等价关系 《算法4》和《算法导论》上关于红黑树的差异 红黑树的5条基本性质的分析 红黑树与2-3-4树的等价关系 红黑树的插入、删除操作 JDK ...
摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...
阅读 1877·2021-10-11 10:59
阅读 1016·2021-09-07 09:59
阅读 2206·2021-08-27 16:17
阅读 2767·2019-08-30 15:54
阅读 2253·2019-08-30 12:58
阅读 1732·2019-08-30 12:53
阅读 1423·2019-08-28 18:13
阅读 706·2019-08-26 13:35
