樹

二叉樹
---- 二叉樹的遍歷,添加，查找，刪除
---- 順序存儲二叉樹
-----線索化二叉樹
赫夫曼樹
赫夫曼編碼
二叉排序樹
平衡二叉樹中的AVL數

二叉樹

完全二叉樹:
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹
滿二叉樹:
若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹

二叉樹的遍歷,添加，查找，刪除

代碼

public class BinaryTreeDemo{public static void main(String[] args) {TreeNode root=new TreeNode(1);TreeNode node1=new TreeNode(2);root.setLeft(node1);TreeNode node2=new TreeNode(3);root.setRight(node2);TreeNode node3=new TreeNode(4);node1.setLeft(node3);TreeNode node4=new TreeNode(5);node1.setRight(node4);TreeNode node5=new TreeNode(6);node2.setLeft(node5);TreeNode node6=new TreeNode(7);node2.setRight(node6);TreeNode node7=new TreeNode(8);node3.setLeft(node7);TreeNode node8=new TreeNode(9);node3.setRight(node8);BinaryTree binaryTree = new BinaryTree(root);//前序遍歷輸出//binaryTree.preOrder();//中序遍歷輸出//binaryTree.infixOrder();//后序遍歷輸出//binaryTree.postOrder();//前序遍歷查找// TreeNode tree = binaryTree.preOrderSearch(8);// System.out.println(tree);//中序遍歷查找//TreeNode tree = binaryTree.infixOrderSearch(1);//System.out.println(tree.getNo());//后序遍歷查找//TreeNode tree = binaryTree.postOrderSearch(0);//System.out.println(tree.getNo());//節點刪除,如果刪除的是非葉子節點,將非葉子節點下的節點也刪除//binaryTree.deleteTree(node5);//binaryTree.preOrder();//節點刪除,如果刪除的是非葉子節點,只刪除此節點,此節點的左節點代替它binaryTree.deleteNode(node1);binaryTree.preOrder();} } class BinaryTree{private TreeNode root;public BinaryTree(TreeNode root) {this.root=root;}//刪除節點node,然后node節點的左子節點代替nodepublic void deleteNode(TreeNode node5) {if(root !=null){if(this.root.getNo()==node5.getNo()){//1.首先緩存根節點的右節點(tempNode)//2.如果根節點沒有左子節點,則將右節點設置為根節點結束//3.如果根節點有左子節點,則將左子節點設置為根節點(leftRoot)//4.如果tempNode為null則直接結束，否則進行如下操作//5.如果leftRoot有沒有左子節點，則將tempNode設置為leftRoot的左子節點//6.如果leftRoot有沒有右子節點，則將tempNode設置為leftRoot的右子節點//7.如果leftRoot有左子節點和又子節點則作如下操作//8. // 緩存根節點 // TreeNode temp=leftRoot; // 緩存根節點的右節點 // TreeNode rightTemp=null; // 只要他的右子節點不為空 // while(temp.right!=null){ // 緩存兩個值，同時給 // rightTemp=temp.right; // temp.right=tempNode; // tempNode=rightTemp; // 節點后移 // temp=temp.left; // } // 他的右子節點為空時，將值設置為他的父節點的右子節點 // temp.setRight(tempNode);}else{this.root.deleteNode(node5); }}}//刪除以node5為根節點的樹public void deleteTree(TreeNode node5) {if(root.getNo()==node5.getNo()){this.root=null;return;}root.deleteTree(node5);}//后序遍歷查找public TreeNode postOrderSearch(int i) {return root.postOrderSearch(i);}//中序遍歷查找public TreeNode infixOrderSearch(int i) {return root.infixOrderSearch(i);}//前序遍歷查找public TreeNode preOrderSearch(int i) {return this.root.preOrderSerach(i); }//前序遍歷//中->左->右public void preOrder() {if(root!=null){root.preOrder();}}//中序遍歷//左->中->右public void infixOrder(){if(root!=null){root.infixOrder();}}//后序遍歷//左->右->中public void postOrder(){if(root!=null){root.postOrder();}}} class TreeNode{private int no;private TreeNode left;private TreeNode right;public TreeNode(int no) {this.no=no;}//刪除node節點public void deleteNode(TreeNode node) {if(this.left!=null && this.left.getNo()==node.getNo()){//這時要刪除this.left節點//1.如果this.left有右節點 緩存this.left的左子節點TreeNode rightNode=null;if(this.left.right!=null){rightNode=this.left.right;}//刪除left節點,如果left有子節點,將left的左子節點代替它if(this.left.left==null){this.setLeft(rightNode);}else{//要刪除的孩子的節點有值this.setLeft(this.left.left);//當替換的節點沒有右節點時直接將緩存的節點添加上if(rightNode!=null){if(this.left.right==null){this.left.right=rightNode;}else if(this.left.left==null){this.left.left=rightNode;}else{//緩存刪除節點位置上的節點TreeNode temp=this.left;//緩存刪除節點位置的右節點TreeNode temp2=null;while(temp.right!=null){temp2=temp.right;temp.right=rightNode;rightNode=temp2;temp=temp.left;}temp.setRight(rightNode);}}}}if(this.right!=null && this.right.getNo()==node.getNo()){//同left 代碼略}if(this.left!=null){this.left.deleteNode(node);}if(this.right!=null){this.right.deleteNode(node);}}//刪除以node為根節點的樹public void deleteTree(TreeNode node5) { // if(this.getNo()==node5.getNo()){ // this=null; 這里不能設置要在調用方法中設置 // }if(this.getLeft()!=null && this.getLeft().getNo() == node5.getNo()){this.setLeft(null);}if(this.getRight()!=null && this.getRight().getNo() == node5.getNo()){this.setRight(null);}if(this.getLeft()!=null){this.getLeft().deleteTree(node5);}if(this.getRight()!=null){this.getRight().deleteTree(node5);}}public TreeNode postOrderSearch(int i) {TreeNode treeNode=null;if(this.left!=null){treeNode=this.left.postOrderSearch(i);}if(this.right!=null){treeNode=this.right.postOrderSearch(i);}if(this.no==i){return this;}return treeNode;}public TreeNode infixOrderSearch(int i) {TreeNode treeNode=null;if(this.left !=null){treeNode=this.left.infixOrderSearch(i);}if(treeNode!=null){return treeNode;}if(this.no==i){return this;}if(this.right !=null){treeNode=this.right.infixOrderSearch(i);}return treeNode;}//前序遍歷查找public TreeNode preOrderSerach(int i) {if(this.no==i)return this;//用來返回,如果沒有找到就返回這個nullTreeNode treeNode = null;if(this.left!=null)treeNode=this.left.preOrderSerach(i);if(treeNode != null){return treeNode;}if(this.right!=null)treeNode=this.right.preOrderSerach(i);return treeNode;}//后序遍歷public void postOrder() {if(this.getLeft()!=null){this.getLeft().postOrder();}if(this.getRight()!=null){this.getRight().postOrder();}System.out.println(this.no);}//中序遍歷public void infixOrder() {if(this.getLeft()!=null){this.left.infixOrder();}System.out.println(this.no);if(this.getRight()!=null){this.right.infixOrder();}}//前序遍歷public void preOrder() {System.out.println(this.getNo());if(this.getLeft()!=null){this.getLeft().preOrder();}if(this.getRight()!=null){this.getRight().preOrder();}}public int getNo() {return no;}public TreeNode getLeft() {return left;}public TreeNode getRight() {return right;}public void setNo(int no) {this.no = no;}public void setLeft(TreeNode left) {this.left = left;}public void setRight(TreeNode right) {this.right = right;} }

順序存儲二叉樹

思想
從數據存儲來看，數組存儲方式和樹的存儲方式可以相互轉換，即數組可以轉換成樹，樹也可以轉換成數組。
順序存儲二叉樹的特點:
順序二叉樹通常只考慮完全二叉樹
第n個元素的左子節點為 2 * n + 1
第n個元素的右子節點為 2 * n + 2
第n個元素的父節點為 (n-1) / 2
最后一個葉子節點為 數組長度/2-1

代碼

public class ArrBinaryTreeDemo {public static void main(String[] args) {int[] arr = { 1, 2, 3, 4, 5, 6, 7 };BinaryTree tree=new BinaryTree(arr);tree.preOrder();} } class BinaryTree{//用數組存儲樹private int[] root;public BinaryTree(int[] arr) {this.root=arr;}//前序遍歷 中 左 右public void preOrder() {preOrder(0);}private void preOrder(int i) {System.out.println(root[i]);if(2*i+1<root.length){preOrder(2*i+1);}if(2*i+2<root.length){preOrder(2*i+2);}} }

線索化二叉樹

思想
線索化二叉樹 本質上是將 一個復雜的非線性結構轉換為線性結構，使每個結點都有了唯一前驅和后繼節點
優點
(1)利用線索二叉樹進行中序遍歷時，不必采用堆棧處理，速度較一般二叉樹的遍歷速度快，且節約存儲空間(使用while循環即可遍歷樹，不用遞歸調用了)
(2)任意一個結點都能直接找到它的前驅和后繼結點
缺點
(1)結點的插入和刪除麻煩，且速度也較慢
(2)線索子樹不能共用
圖解

代碼

赫夫曼樹

思想
給定n個權值作為n個葉子結點，構造一棵二叉樹，若該樹的帶權路徑長度(wpl)達到最小，稱這樣的二叉樹為赫夫曼樹
權值較大的結點離根較近，權值較小的結點離根較遠(權值一般為節點出現個數)
代碼

赫夫曼編碼

思想

代碼

二叉排序樹

思想

一棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小于它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大于它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
（4）沒有鍵值相等的結點。

平衡二叉樹中的AVL樹

思想

代碼

總結

以上是生活随笔為你收集整理的树-志宇的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。