二叉树基本种类
结点结点的度树的深度k满二叉树完全二叉树 二叉树的存储方式
顺序存储链式存储 二叉树三种遍历方式
前序遍历中序遍历后序遍历递归实现三种遍历迭代实现三种遍历
二叉树基本种类 结点
根结点,可以单独成树即该根结点没有孩子;也可以有孩子;
叶子结点简称叶子,又称终端结点,顾名思义,该结点不是根结点且没有孩子;
子结点如上图所示,子结点不是根结点且它有孩子。
结点的度就是其孩子的个数,如上图,根结点度为2,子结点度为2,叶子结点度为0.
树的深度k1.k>=1,树有几层,就有多深;
2.树的结点总数为
2
k
2^k
2k-1;
3.第k层的结点数为
2
k
−
1
2^{k-1}
2k−1.
顾名思义,分两种情况:
1.该树只有根结点;
2.该树所有非叶子结点的度为2。
完全二叉树定义为:
除了最底层节点可能没填满外,其余每层节点数都达到最大值,并且最下面一层的结点都是处于左边。
所谓顺序存储就是存储在数组中,一段连续的内存地址,然后通过下标去索引目标结点。
链式存储链式存储和双向链表差不多,首先创造一个结点对象,该对象有三个属性,分别是值,left指针,right指针
public class Node { int val; Node left; Node right; public Node(){ } public Node(int val, Node left, Node right) { this.val = val; this.left = left; this.right = right; } }二叉树三种遍历方式 前序遍历
前序遍历顺序为中左右:
上图使用前序遍历:12485367
中序遍历顺序为左中右:
上图使用中序遍历:84251637
后序遍历顺序为左右中:
上图使用后序遍历:84526731
1.写递归时一定别忘了递归终止条件;
2.递归的过程就是不断地进入下一层递归,当遇到终止条件,返回上一层,执行下一条语句,当该层语句执行完后也会返回上一层;
3.注意递归返回的位置;
4.可以看到递归的过程和进出栈类似,其实,递归的底层是栈实现的。
public class Ergodic { //前序遍历 public ArrayList迭代实现三种遍历preReverse(Node root){ ArrayList result = new ArrayList<>(); preOrder(root,result); return result;//在java中引用类型的实参会被改动 } public void preOrder(Node root,ArrayList result){ if(root!=null) { result.add(root.val);//中 preOrder(root.left, result);//左 preOrder(root.right, result);//右 } } //中序遍历 public ArrayList midReverse(Node root){ ArrayList res=new ArrayList<>(); midOrder(root,res); return res; } public void midOrder(Node root,ArrayList res){ if(root!=null){ midOrder(root.left,res);//左 res.add(root.val);//中 midOrder(root.right, res);//右 } } //后序遍历 public ArrayList postReverse(Node root){ ArrayList res=new ArrayList<>(); midOrder(root,res); return res; } public void postOrder(Node root,ArrayList res){ if(root!=null){ postOrder(root.left,res);//左 postOrder(root.right,res);//右 res.add(root.val);//中 } } }
1.使用递归算法可以实现二叉树三种遍历,而递归底层使用栈实现;因此我们可以直接使用栈来实现三种遍历;
2.栈的原理是后进先出,因此将后遍历的结点先push入栈中;当结点为空时,执行pop();
3.将push的结点用数组保存其数值。
public class Iteration { //前序遍历;入栈顺序:中右左 public ArrayListpreOrder(Node root){ ArrayList res = new ArrayList<>(); Stack stack=new Stack<>(); if(root==null){ return res; } stack.push(root);//中 while(!stack.isEmpty()) { Node node = stack.pop(); res.add(node.val); if(node.right!=null){//右 stack.push(node.right); } if(node.left!=null){//左 stack.push(node.left); } } return res; } //中序遍历;入栈顺序:左,右 public ArrayList midOrder(Node root){ ArrayList res=new ArrayList<>(); Stack stack =new Stack<>(); if(root==null){ return res; } Node node=root; while(node!=null||!stack.isEmpty()) {//当栈为空,node为空时,遍历结束 if (node != null) {//将左孩子全部推进栈中 stack.push(node); node = node.left; } else { node = stack.pop(); res.add(node.val); node = node.right;//考虑右分支 } } return res; } //后序遍历与前序遍历入栈顺序相反;入栈顺序:中,左,右,出栈顺序:中,右,左;翻转数组 public ArrayList postOrder(Node root){ ArrayList res=new ArrayList<>(); Stack stack =new Stack<>(); if(root==null){ return res; } stack.push(root);//中 while(!stack.isEmpty()) { Node node = stack.pop(); res.add(node.val); if(node.left!=null){//左 stack.push(node.left); } if(node.right!=null){//右 stack.push(node.right); } } Collections.reverse(res); return res; } }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)