二叉樹（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