二叉树

二叉树（Binary Tree）：n（n>=0）个结点的有限集合，该集合或者为空集（空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。

满二叉树：一颗深度为K的二叉树，如果它包含了2k-1个节点，则该二叉树为满二叉树。

完全二叉树：一颗n个节点的二叉树，按满二叉树的编号方式对它进行编号，若树中所有节点和满二叉树1-n编号完全一致，则称该树为完全二叉树。

①二叉树第i层上的节点数目之多为2i-1(i>=1);

②任何一颗二叉树中，如果叶子节点的数量为n0，度为2的节点数量为n2，则n0=n2+1;

③深度为k的二叉树至多有2k-1个结点(k>=1);

④具有n个节点的完全二叉树的深度为log2n+1。

⑤如果对一颗有n个节点的完全二叉树的节点按层进行编号，对于任一节点i(1<=i<=n)，有：

1）若i=1，则节点i无双亲，是根节点。

2）若2i>n，则节点i为叶子节点，无左孩子；若2i<=n,则节点i有左孩子，编号为2i；

3）若2i+1>n，则节点i无右节点；若2i+1<=n,则节点i有右节点，编号为2i+1。

1、顺序存储：使用一个数组来存储一颗二叉树，对于普通的二叉树来说会造成空间的浪费。除非该二叉树是完全二叉树，为例解决这个问题我们可以采用链表方式存储二叉树。

2、二叉链表存储：为一个树节点添加两个指向其左右孩子节点的引用，但是这种存储方式在访问一个节点的父节点时比较困难，必须采用遍历二叉树的方式来搜索其父节点。为了解决这个问题，我们可以采用三叉链表存储；

3、三叉链表存储：为一个树节点添加两个指向其左右孩子节点的引用和一个指向其父节点的引用。

  1 package tree;  2 public class BinaryTree{  3     public static class TreeNode<E>{  4         E data;    5         TreeNode<E> parent;  6         TreeNode<E> leftNode;  7         TreeNode<E> rightNode;  8         public TreeNode() {}  9         public TreeNode(E data) { 10             this.data=data; 11         } 12         public TreeNode(E data,TreeNode<E> leftNode,TreeNode<E> rightNode){ 13             this.data=data; 14             this.leftNode=leftNode; 15             this.rightNode=rightNode; 16         } 17     } 18      19     PRivate TreeNode root; 20     public <E> void setRoot(TreeNode<E> root) { 21         this.root = root; 22     } 23     // 返回根节点 24     public <E> TreeNode<E> getRoot(){ 25         if(root==null || isEmpty()){ 26             throw new RuntimeException("root is null"); 27         }else { 28             return root; 29         } 30     } 31     public BinaryTree() { 32     } 33     public <E> BinaryTree(TreeNode<E> root) { 34         this.root=root; 35     } 36     //返回父节点 37     public <E> TreeNode<E> getParent(TreeNode<E> node){ 38         if(node==null){ 39             throw new RuntimeException("the node is null"); 40         }else { 41             return node.parent; 42         } 43     } 44     //为指定节点添加子节点 45     public <E> void addNode(TreeNode<E> parent,E data, boolean isLeft){ 46         if(parent==null){ 47             throw new RuntimeException("parent is null,so can't add child to this parent"); 48         }else if (isLeft && parent.leftNode!=null) { 49             throw new RuntimeException("the parent already has haven a leftchild"); 50         }else if (!isLeft && parent.rightNode!=null) { 51             throw new RuntimeException("the parent already has haven a rightchild"); 52         } 53        TreeNode<E> child=new TreeNode<E>(data); 54          if (isLeft) {     55              parent.leftNode=child; 56         }else { 57             parent.rightNode=child; 58         } 59          child.parent=parent; 60     } 61     public <E> void addNode(TreeNode<E> parent,TreeNode<E> child, boolean isLeft){ 62         if(parent==null){ 63             throw new RuntimeException("parent is null,so can't add child to this parent"); 64         }else if (isLeft && parent.leftNode!=null) { 65             throw new RuntimeException("the parent already has haven a leftchild"); 66         }else if (!isLeft && parent.rightNode!=null) { 67             throw new RuntimeException("the parent already has haven a rightchild"); 68         } 69          if (isLeft) {     70              parent.leftNode=child; 71         }else { 72             parent.rightNode=child; 73         } 74          child.parent=parent; 75     } 76     // 判断二叉树是否为空 77     public boolean isEmpty(){ 78         return root==null; 79     } 80     //返回指定节点的左子节点 81     public <E> TreeNode<E> getLeftChild(TreeNode<E> parent){ 82         if(parent==null){ 83             throw new RuntimeException("parent is null"); 84         }else { 85             return parent.leftNode==null? null : parent.leftNode; 86         } 87     } 88     //返回指定节点的右子节点 89     public <E> TreeNode<E> getRightChild(TreeNode<E> parent){ 90         if(parent==null){ 91             throw new RuntimeException("parent is null"); 92         }else { 93             return parent.rightNode==null? null:parent.rightNode; 94         } 95     } 96     //返回二叉树的深度 97     public int deep(){ 98         return deep(root); 99     }100     //使用递归，如果节点为空则深度为0，如果节点既没有左孩子，也没有右孩子，则深度为1，否则为其左右孩子树中最大的深度+1101     private <E> int deep(TreeNode<E> root) {102         if(root==null){103             return 0;104         }else if (root.leftNode ==null && root.rightNode==null) {105             return 1;106         }else {107             int leftDeep=deep(root.leftNode);108             int rightDeep=deep(root.rightNode);109             int max= leftDeep>rightDeep? leftDeep:rightDeep;110             return max+1;111         }112     }113 }

如果采用顺序结构来保存二叉树，程序遍历二叉树将非常简单，直接遍历底层数组即可。如果采用链表来保存二叉树则有一下两种遍历方式：深度优先遍历这种遍历方式采用递归调用的方式（利用栈的原理），递-入栈，归-出栈。广度优先遍历这种遍历方式将逐层访问每层的节点，先访问根（第一层）节点，然后访问第二层的节点&hellip;…一次类推。因此广度优先遍历又称为按层遍历。

深度优先遍历又分为先序遍历、中序遍历、后序遍历

图解深度优先遍历：

先序遍历：①访问根节点②递归遍历左子树③递归遍历右子树

 1     public  List<TreeNode> preIterator(){ 2         return preIterator(root); 3     } 4     private List<TreeNode> preIterator(TreeNode root) { 5         List<TreeNode> list=new ArrayList<TreeNode>(); 6         list.add(root); 7         if(root.leftNode!=null){ 8             list.addAll(preIterator(root.leftNode)); 9         }10         if (root.rightNode!=null){11             list.addAll(preIterator(root.rightNode));12         }13         return list;14     }

中序遍历①递归遍历左子树②访问根节点③递归遍历右子树

 1     public List<TreeNode> midIterator(){ 2         return midIterator(root); 3     } 4     private  List<TreeNode> midIterator(TreeNode root) { 5         List<TreeNode> list=new ArrayList<TreeNode>(); 6         if(root==null){ 7             return null; 8         } 9         if(root.leftNode!=null){10             list.addAll(midIterator(root.leftNode));11         }12         list.add(root);13         if(root.rightNode!=null){14             list.addAll(midIterator(root.rightNode));15         }16         return list;17     }

后序遍历①递归遍历左子树②递归遍历右子树③访问根节点

 1     public List<TreeNode> postIterator(){ 2         return postIterator(root); 3     } 4     private List<TreeNode> postIterator(TreeNode root) { 5         if(root==null){ 6             return null; 7         } 8          9         List<TreeNode> list=new ArrayList<TreeNode>();10         if(root.leftNode!=null){11             list.addAll(postIterator(root.leftNode));12         }13         if(root.rightNode!=null){14             list.addAll(postIterator(root.rightNode));15         }16         list.add(root);17         return list;18     }

为了实现广度优先遍历，可以借助于具有“FIFO”特征的队列来实现：①建立一个队列（先进先出），把书的根节点压入队列；②从队列中弹出一个节点（第一次弹出的节点就是根节点），然后把该节点的左，右节点压入队列，如果没有子节点，则说明已经到达叶子节点。③用循环重复执行②，直到队列为空时，说明所有的叶子节点（深度最深的层）都已经经过了队列，也就完成了遍历。

 1 public List<TreeNode> breadthFirst(){ 2         Queue<TreeNode> queue=new ArrayDeque<TreeNode>(); 3         List<TreeNode> list=new ArrayList<TreeNode>(); 4         if(root!=null){ 5             //将树根加入队列 6             queue.offer(root); 7         } 8         while(!queue.isEmpty()){ 9             //将队列的“队尾”的元素添加到list中10             list.add(queue.peek());11             //从队列中弹出一个节点，并获取12             TreeNode node=queue.poll();13             //如果该节点有左孩子，就把左孩子压入队列14             if(node.leftNode!=null){15                 queue.offer(node.leftNode);16             }17             //如果该节点有右孩子，就把右孩子压入队列18             if(node.rightNode!=null){19                 queue.offer(node.rightNode);20             }21         }22         return list;23     }

View Code