二叉树的存储结构包括:顺序存储结构&链式存储结构
注:上述的链式存储方式,即为树结构中的孩子兄弟表示法。具体如下:
大多数情况下,二叉树的建立会采用链式存储结构
建立的核心:数据结构=链表、实现方式=递归/非递归算法
采用链表的方式,也称为:二叉链表
从根节点出发,按照某种次序访问二叉树中的所有结点,使得每个结点被访问1次且只被访问1次
二叉树的遍历方式包括:
遍历的实现方式分为:递归&非递归方式,下面会详细说明
也称深度优先遍历
/***内容:前序遍历*方式:递归*/publicvoidpreOrder(Noderoot){//1.判断二叉树结点是否为空;若是,则返回空操作if(root==null)return;//2.访问根节点(显示根结点)printNode(root);//3.遍历左子树preOrder(root.getLeftNode());//4.遍历右子树preOrder(root.getRightNode());}示意图
/***方式:非递归(栈实现)*/publicstaticvoidpreOrder_stack(Noderoot){Stackstack=newStack();//步骤1:直到当前结点为空&栈空时,循环结束while(root!=null||stack.size()>0){//步骤2:判断当前结点是否为空//a.若不为空,执行3//b.若为空,执行5if(root!=null){//步骤3:输出当前节点,并将其入栈printNode(root);stack.push(root);//步骤4:置当前结点的左孩子为当前节点//返回步骤1root=root.getLeftNode();}else{//步骤5:出栈栈顶结点root=stack.pop();//步骤6:置当前结点的右孩子为当前节点root=root.getRightNode();//返回步骤1}}}示意图
/***方式:递归*/publicvoidInOrder(Noderoot){//1.判断二叉树结点是否为空;若是,则返回空操作if(root==null)return;//2.遍历左子树InOrder(root.getLeftNode());//3.访问根节点(显示根结点)printNode(root);//4.遍历右子树InOrder(root.getRightNode());}示意图
流程图
/***方式:非递归(栈实现)*/publicstaticvoidInOrder_stack(Noderoot){Stackstack=newStack();//1.直到当前结点为空&栈空时,循环结束while(root!=null||stack.size()>0){//2.判断当前结点是否为空//a.若不为空,执行3、4//b.若为空,执行5、6if(root!=null){//3.入栈当前结点stack.push(root);//4.置当前结点的左孩子为当前节点//返回步骤1root=root.getLeftNode();}else{//5.出栈栈顶结点root=stack.pop();//6.输出当前节点printNode(root);//7.置当前结点的右孩子为当前节点root=root.getRightNode();//返回步骤1}}5.3.3后序遍历示意图
/***方式:递归*/publicvoidPostOrder(Noderoot){//1.判断二叉树结点是否为空;若是,则返回空操作if(root==null)return;//2.遍历左子树PostOrder(root.getLeftNode());//3.遍历右子树PostOrder(root.getRightNode());//4.访问根节点(显示根结点)printNode(root);}示意图
/***方式:非递归(栈实现)*/publicvoidPostOrder_stack(Noderoot){Stackstack=newStack();Stackoutput=newStack();//步骤1:直到当前结点为空&栈空时,循环结束——>步骤8while(root!=null||stack.size()>0){//步骤2:判断当前结点是否为空//a.若不为空,执行3、4//b.若为空,执行5、6if(root!=null){//步骤3:入栈当前结点到中间栈output.push(root);//步骤4:入栈当前结点到普通栈stack.push(root);//步骤4:置当前结点的右孩子为当前节点//返回步骤1root=root.getRightNode();}else{//步骤5:出栈栈顶结点root=stack.pop();//步骤6:置当前结点的右孩子为当前节点root=root.getLeftNode();//返回步骤1}}//步骤8:输出中间栈的结点while(output.size()>0){printNode(output.pop());}}示意图
/***方式:非递归(采用队列)*/publicvoidlevelTravel(Noderoot){//创建队列Queueq=newLinkedList();//1.判断当前结点是否为空;若是,则返回空操作if(root==null)return;//2.入队当前结点q.add(root);//3.判断当前队列是否为空,若为空则跳出循环while(!q.isEmpty()){//4.出队队首元素root=q.poll();//5.输出出队元素printNode(root);//6.若出队元素有左孩子,则入队其左孩子if(root.getLeftNode()!=null)q.add(root.getLeftNode());//7.若出队元素有右孩子,则入队其右孩子if(root.getRightNode()!=null)q.add(root.getRightNode());}}