[ 数据结构 ] 二叉树详解--------前序、中序、后序、存储、线索化
0 前言
-
why?为什么需要树结构?
数组虽然查找快(通过下标访问),但无法动态扩容(拷贝到新的数组),而链表相反,树结构刚好结合两者优点
-
浅谈树?
树的存储和读取效率都很高,比如二叉排序树,理解树的抽象模型有助于理解递归的原理,树的模型接近于单向链表,父节点指向左右子树,而链表相比二叉树可以看成单叉
1 初识二叉树
- 遍历:分为前、中、后序,区分前中后简单说就是对当前节点的处理操作(打印)是在左右子节点的递归调用的前面、中间、还是后面,比如前序:先打印当前节点,再分别左右子节点递归调用
- 查找:同样有前、中、后序,取决于判断操作是在两个递归调用的前面、中间、后面,当然,如果到方法的最后(搜索到叶子节点)都没能找到目标,需要返回null(结果需要在判断之后立即返回,不可以先收集再在末尾返回)
- 删除:先找再删,这里的找不同于2中的查找,判断操作是在当前节点判断子节点是否要删除,毕竟只能通过父节点的指针删除,而不能自己删除自己
//二叉树的前序、中序、后序遍历,前中后序查找,删除三类方法
//主类+树类+节点类
public class Tree01_BinaryTreeDemo {public static void main(String[] args) {//手动创建二叉树BinaryTree tree = new BinaryTree();Hero root = new Hero(1, "宋江");Hero node2 = new Hero(2, "吴用");Hero node3 = new Hero(3, "卢俊义");Hero node4 = new Hero(4, "林冲");Hero node5 = new Hero(5, "关胜");Hero node8 = new Hero(8, "晁盖");Hero node7 = new Hero(7, "武松");root.setLeft(node2);root.setRight(node3);node3.setRight(node4);node3.setLeft(node5);node2.setLeft(node8);node2.setRight(node7);tree.setRoot(root);//遍历tree.preOrder();//12354
// tree.infixOrder();//21534
// tree.postOrder();//25431//查找tree.postOrderSearch(4);//删除
// tree.delNode(3);
// System.out.println("删除后:");
// tree.preOrder();}
}//二叉树
class BinaryTree {private Hero root;public void setRoot(Hero root) {this.root = root;}//三种方式遍历树,从root起public void preOrder() {if (root != null) {root.preOrder();} else {System.out.println("二叉树为空");}}public void infixOrder() {if (root != null) {root.infixOrder();} else {System.out.println("二叉树为空");}}public void postOrder() {if (root != null) {root.postOrder();} else {System.out.println("二叉树为空");}}//三种方式查找树,从root起public void preOrderSearch(int no) {if (root != null) {if (root.preOrderSearch(no) != null) {System.out.println("查找结果为" + root.preOrderSearch(no));} else {System.out.println("没找到!!!");}} else {System.out.println("二叉树为空");}}public void infixOrderSearch(int no) {if (root != null) {if (root.infixOrderSearch(no) != null) {System.out.println("查找结果为" + root.infixOrderSearch(no));} else {System.out.println("没找到!!!");}} else {System.out.println("二叉树为空");}}public void postOrderSearch(int no) {if (root != null) {Hero result= root.postOrderSearch(no);if (result != null) {System.out.println("查找结果为" + result);} else {System.out.println("没找到!!!");}} else {System.out.println("二叉树为空");}}//删除节点public void delNode(int no) {if (root == null) {System.out.println("二叉树空,无法删除");} else {//删除的节点就是root,直接置空,否则遍历删除if (root.getNo() == no) {root = null;} else {root.delNode(no);}}}
}//树节点
//编写三种遍历方式
class Hero {private int no;private String name;private Hero left;private Hero right;public Hero(int no, String name) {this.no = no;this.name = name;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Hero getLeft() {return left;}public void setLeft(Hero left) {this.left = left;}public Hero getRight() {return right;}public void setRight(Hero right) {this.right = right;}@Overridepublic String toString() {return "HeroNode [no=" + no + ", name=" + name + "]";}//前序遍历public void preOrder() {System.out.println(this);if (left != null) {left.preOrder();}if (right != null) {right.preOrder();}}//中序遍历public void infixOrder() {if (left != null) {left.infixOrder();}System.out.println(this);if (right != null) {right.infixOrder();}}//后序遍历public void postOrder() {if (left != null) {left.postOrder();}if (right != null) {right.postOrder();}System.out.println(this);}//前序查找//这里当前节点的查找结果毫无疑问若正确可以直接返回//子节点的查找结果必须先收集再判断,若正确直接返回,为空则在方法末尾返回// =>如果不立即判断返回则当查找到第一个叶子节点直接必出结果,即路径上遇到结果就返回,到叶子都没遇到就返回null了//整体判断逻辑:当前节点能否返回(能否返回:找到正确结果才返回)-->左递归能否返回-->右递归直接返回-->补上方法返回值null//总结:以前序为例,无论是遍历还是查找,对于当前节点的操作其实只是左递归前的附带操作,// 因此从执行结果来看,整体是先从上往下执行,(中+左)=>(中+左)=>(中+左)=>叶子,然后开始从下层处理到上层public Hero preOrderSearch(int no) {if (this.no == no) {return this;}if (left != null) {if (left.preOrderSearch(no) != null) {return left.preOrderSearch(no);}}if (right != null) {return right.preOrderSearch(no);}return null;}//中序查找public Hero infixOrderSearch(int no) {if (left != null) {if (left.infixOrderSearch(no) != null) {return left.infixOrderSearch(no);}}if (this.no == no) {return this;}if (right != null) {if (right.infixOrderSearch(no) != null) {return right.infixOrderSearch(no);}}return null;}//后序查找public Hero postOrderSearch(int no) {Hero result = null;if (left != null) {result = left.postOrderSearch(no);if (result != null) {return result;}}if (right != null) {result = right.postOrderSearch(no);if (result != null) {return result;}}//统计比较多少次,以后序查找为例,//注意为了得到正确的比较次数,需要将递归结果先收集再做判断或返回,否则次数会翻倍System.out.println("一次");if (this.no == no) {return this;}return result;}//删除节点//核心:在当前节点判断是否删除子节点(因为单向二叉树只能操作自己的左右指针),注意根节点的判断在树类中//若删除了子节点,则直接返回结束方法(递归),否则调用递归删除public void delNode(int no) {if (this.left != null && this.left.no == no) {this.left = null;return;}if (this.right != null && this.right.no == no) {this.right = null;return;}if (this.left != null) {this.left.delNode(no);}if (this.right != null) {this.right.delNode(no);}}
}
2 顺序存储二叉树
说明:
- 顺序存储二叉树其实就是将数组转换成树,也可以说是将树节点存放在数组中
- 根节点表示下标为0的数组元素,那么下标为n的节点,它的左子节点下标(2 * n + 1),右子节点(2 * n - 1),父节点(n-1) / 2.
- 按要求,顺序二叉树需满足完全二叉树(叶子节点在最下面两层,最后一层左侧连续)
//顺序存储二叉树(数组和树可相互转换,这里用数组存放二叉树节点)
//数组存储元素顺序是按树层序遍历顺序......
public class Tree02_ArrBinaryTreeDemo {public static void main(String[] args) {int[] arr = { 1, 2, 3, 4, 5, 6, 7 };ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);arrBinaryTree.preOrder();}
}//树
class ArrBinaryTree {private int[] arr;public ArrBinaryTree(int[] arr) {this.arr = arr;}//重载public void preOrder() {preOrder(0);}//前序遍历//核心:父子节点间的索引计算等式,左子节点2n+1,右子节点2n+2,父节点(n-1)/2//递归终止条件为索引越界arr.length,当然给递归调用加if判断也可以终止调用public void preOrder(int index) {if (arr == null || arr.length == 0) {System.out.println("数为空,无法遍历!");return;}if (index >= 0 && index < arr.length) {System.out.println(arr[index]);} else {return;}preOrder(2 * index + 1);preOrder(2 * index + 2);}
}
3 线索化二叉树
- 问题:先看上图,数列 {1, 3, 6, 8, 10, 14 } 构建成一颗二叉树,节点数n=6,每个节点两个指针计算,满打满算2n个指针,但是除去根节点只有n-1个指针指向已有节点,算下来就有2n-(n-1)=n+1个空指针,怎么用这些个空指针呢?
- 以中序遍历为例,如果遍历时利用这些空指针按规则指向中序遍历结果的相邻节点(前驱节点/后继节点),那么就会将树中序线索化,也就有了后面新的遍历方式(线型遍历)
- 线型遍历:利用线索二叉树叶子节点连成的线索,以非递归的方式遍历树(有点像链表)
- 线索化代码核心:定义全局变量pre用来存放中序遍历的前驱节点(毕竟是单向的二叉树,无法在当前节点让前驱节点指向自己),通过pre节点和当前节点(两节点形成前驱-后继关系)来改变原来空指针的指向
//二叉树的中序线索化及其线型遍历
public class Tree03_ThreadedBinaryTreeDemo {public static void main(String[] args) {//手动创建二叉树Ho root = new Ho(1, "tom");Ho node2 = new Ho(3, "jack");Ho node3 = new Ho(6, "smith");Ho node4 = new Ho(8, "mary");Ho node5 = new Ho(10, "king");Ho node6 = new Ho(14, "dim");root.setLeft(node2);root.setRight(node3);node2.setLeft(node4);node2.setRight(node5);node3.setLeft(node6);ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();threadedBinaryTree.setRoot(root);//测试threadedBinaryTree.threadedNode();
// System.out.println(node5.getLeft().toString());
// System.out.println(node5.getRight().toString());threadedBinaryTree.threadedList();}
}//二叉树
class ThreadedBinaryTree {private Ho root;private Ho pre = null;//前驱节点public void setRoot(Ho root) {this.root = root;}//三种方式遍历树,从root起public void preOrder() {if (root != null) {root.preOrder();} else {System.out.println("二叉树为空");}}public void infixOrder() {if (root != null) {root.infixOrder();} else {System.out.println("二叉树为空");}}public void postOrder() {if (root != null) {root.postOrder();} else {System.out.println("二叉树为空");}}//三种方式查找树,从root起public void preOrderSearch(int no) {if (root != null) {if (root.preOrderSearch(no) != null) {System.out.println("查找结果为" + root.preOrderSearch(no));} else {System.out.println("没找到!!!");}} else {System.out.println("二叉树为空");}}public void infixOrderSearch(int no) {if (root != null) {if (root.infixOrderSearch(no) != null) {System.out.println("查找结果为" + root.infixOrderSearch(no));} else {System.out.println("没找到!!!");}} else {System.out.println("二叉树为空");}}public void postOrderSearch(int no) {if (root != null) {Ho result= root.postOrderSearch(no);if (result != null) {System.out.println("查找结果为" + result);} else {System.out.println("没找到!!!");}} else {System.out.println("二叉树为空");}}//删除节点public void delNode(int no) {if (root == null) {System.out.println("二叉树空,无法删除");} else {//删除的节点就是root,直接置空,否则遍历删除if (root.getNo() == no) {root = null;} else {root.delNode(no);}}}//中序线索化//切入点:线索化无非就是改变左右指向,从null改为指向前驱和后继节点,但是遍历到当前节点时只经过了前驱节点,不可能拿到后继节点,所以...//中序遍历的基本思想,处理当前节点时:若需要线索化则改变当前节点的左指向和类型(完成前驱线索化),//同时通过改变前驱节点的右指向和类型(完成后继线索化),2步处理完更新前驱节点//线索化后再遍历会死龟!!!public void threadedNode(Ho node) {if (node == null) {return;}threadedNode(node.getLeft());if (pre != null&&pre.getRight()==null) {pre.setRight(node);pre.setRightType(1);}if (node.getLeft() == null) {node.setLeft(pre);node.setLeftType(1);}pre = node;threadedNode(node.getRight());}//中序线索化方法重载public void threadedNode() {this.threadedNode(root);}//线型方式遍历(非递归),实现线索化二叉树的中序遍历//逻辑:左子树上寻找线索化节点并打印,持续输出后继节点,没有后继节点节点就取右子树后找线索化节点-->循环//宏观上:就是寻找线索化节点和它的后继节点public void threadedList() {Ho node = root;while (node!=null) {//找到线索化节点并打印8,打印8//找到线索化节点并打印10,打印10//找到线索化节点并打印14,打印14while (node.getLeftType()==0) {node = node.getLeft();}System.out.println(node);//后继节点打印3//后继节点打印1//后继节点打印6while ( node.getRightType() == 1) {node = node.getRight();System.out.println(node);}//右子节点10//右子节点6//右子节点null,退出node = node.getRight();}}
}//树节点
//编写三种遍历方式
class Ho {private int no;private String name;private Ho left;private Ho right;//新增指针类型,0表示子树,1表示前驱/后继节点,问:有啥用?答:遍历防止死龟private int leftType;private int rightType;public Ho(int no, String name) {this.no = no;this.name = name;}public int getNo() {return no;}public void setNo(int no) {this.no = no;}public String getName() {return name;}public void setName(String name) {this.name = name;}public Ho getLeft() {return left;}public void setLeft(Ho left) {this.left = left;}public Ho getRight() {return right;}public void setRight(Ho right) {this.right = right;}public int getLeftType() {return leftType;}public void setLeftType(int leftType) {this.leftType = leftType;}public int getRightType() {return rightType;}public void setRightType(int rightType) {this.rightType = rightType;}@Overridepublic String toString() {return "HoNode [no=" + no + ", name=" + name + "]";}//前序遍历public void preOrder() {System.out.println(this);if (left != null) {left.preOrder();}if (right != null) {right.preOrder();}}//中序遍历,线索化后的
// public void infixOrder() {
// if (left != null&& leftType==0) {
// left.infixOrder();
// }
// System.out.println(this);
// if (right != null&& rightType==0) {
// right.infixOrder();
// }
// }//中序遍历public void infixOrder() {if (left != null) {left.infixOrder();}System.out.println(this);if (right != null) {right.infixOrder();}}//后序遍历public void postOrder() {if (left != null) {left.postOrder();}if (right != null) {right.postOrder();}System.out.println(this);}//前序查找//这里当前节点的查找结果毫无疑问若正确可以直接返回//子节点的查找结果必须先收集再判断,若正确直接返回,为空则在方法末尾返回// =>如果不立即判断返回则当查找到第一个叶子节点直接必出结果,即路径上遇到结果就返回,到叶子都没遇到就返回null了//整体判断逻辑:当前节点能否返回(能否返回:找到正确结果才返回)-->左递归能否返回-->右递归直接返回-->补上方法返回值null//总结:以前序为例,无论是遍历还是查找,对于当前节点的操作其实只是左递归前的附带操作,// 因此从执行结果来看,整体是先从上往下执行,(中+左)=>(中+左)=>(中+左)=>叶子,然后开始从下层处理到上层public Ho preOrderSearch(int no) {if (this.no == no) {return this;}if (left != null) {if (left.preOrderSearch(no) != null) {return left.preOrderSearch(no);}}if (right != null) {return right.preOrderSearch(no);}return null;}//中序查找public Ho infixOrderSearch(int no) {if (left != null) {if (left.infixOrderSearch(no) != null) {return left.infixOrderSearch(no);}}if (this.no == no) {return this;}if (right != null) {if (right.infixOrderSearch(no) != null) {return right.infixOrderSearch(no);}}return null;}//后序查找public Ho postOrderSearch(int no) {Ho result = null;if (left != null) {result = left.postOrderSearch(no);if (result != null) {return result;}}if (right != null) {result = right.postOrderSearch(no);if (result != null) {return result;}}//统计比较多少次,以后序查找为例,//注意为了得到正确的比较次数,需要将递归结果先收集再做判断或返回,否则次数会翻倍System.out.println("一次");if (this.no == no) {return this;}return result;}//删除节点//核心:在当前节点判断是否删除子节点(因为单向二叉树只能操作自己的左右指针),注意根节点的判断在树类中//若删除了子节点,则直接返回结束方法(递归),否则调用递归删除public void delNode(int no) {if (this.left != null && this.left.no == no) {this.left = null;return;}if (this.right != null && this.right.no == no) {this.right = null;return;}if (this.left != null) {this.left.delNode(no);}if (this.right != null) {this.right.delNode(no);}}
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！