二叉樹常用方法（一）

樹節點

public class Node {public int data;public Node leftNode;public Node rightNode;public Node(){this.data = -1;}public Node(int data){this.data = data;this.leftNode = null;this.rightNode = null;}}

二叉樹方法

二叉樹

public class Tree {private Node root;public Tree(){root = null;} }

前序數組創建二叉樹

public int creatTreeByPre(Node node, int[] treeNodes, int n){//如果提供空節點,那么需要創建根節點并保持到root中if (node == null) {root = new Node();node = root;}//給當前節點賦值node.data = treeNodes[n];//記錄左子樹和右子樹放回的位置int left =0,right=0;//前序//如果下一個節點是空的話（-1）,那么直接跳過，否則創建節點，向下遞歸if(treeNodes[n+1] != -1){node.leftNode = new Node();left = creatTreeByPre(node.leftNode,treeNodes,n+1);}else {//下一個是空，那么再下一個left = n+1+1;}//同理if (treeNodes[left]!=-1){node.rightNode = new Node();right = creatTreeByPre(node.rightNode,treeNodes,left);}else {right = left+1;}return right;}

前序遍歷

public void printNodeByPre(Node root){if (root==null) return;System.out.print(root.data+"\t");printNodeByPre(root.leftNode);printNodeByPre(root.rightNode);}

求樹最大深度

public int maxDeath(Node node){if (node == null) return 0;int left = maxDeath(node.leftNode);int right = maxDeath(node.rightNode);return Math.max(left,right)+1;}

求二叉樹節點個數

public int getNodenum(Node root){if (root == null) return 0;int left = getNodenum(root.leftNode);int right = getNodenum(root.rightNode);return left+right+1;}

求樹最小深度

public int minDeath(Node root){if (root == null) return 0;int left = minDeath(root.leftNode);int right = minDeath(root.rightNode);return Math.min(left,right)+1;}

求左右樹節點個數(不包含根節點)

public int getNumOfChildNode(Node root){if (root == null) return 0;int left = getNumOfChildNode(root.leftNode);int right = getNumOfChildNode(root.rightNode);return left+right;}

判斷是否為平衡二叉樹

//平衡樹條件:一顆樹沒一層節點的左子樹和右子樹的最大層數不能相差超過一 public boolean isbalancedTree(Node root){//-1表示破壞平衡，return getAbsDeath(root,1)!=-1; }//當樹中出現左右子樹的深度差大于n時放回-1，否則返回最大深度 public int getAbsDeath(Node root,int n){//空返回0if (root == null) return 0;//獲取左右子樹的深度int left = getAbsDeath(root.leftNode,n);int right = getAbsDeath(root.rightNode,n);//左右深度相差>2，破壞相對條件，返回-1，左右子樹哪一邊破開相對條件也返回-1if (left ==-1 || right==-1 || Math.abs(left-right)>n) return -1;//相對條件沒被破壞，繼續統計層數return Math.max(left,right)+1; }

判斷是否為完美樹

public boolean isCompleteTree(Node root){if (root == null) return false;//判斷是否為完美二叉樹，需要一層一層從左往右掃描,所以用到隊列，先進先出頂多特點Queue<Node> queue = new LinkedList<>();//當出現只有一個子節點或沒有子節點的節點時，后面的所以節點必須沒有子節點，//否則該二叉樹不是完美二叉樹。有沒子節點是判斷的分界，判斷不同。boolean hasChild = true;while (!queue.isEmpty()){//有子節點的-----------------------if (hasChild){if (root.leftNode == null &&root.rightNode == null)hasChild = false;if (root.leftNode != null && root.rightNode == null){hasChild = false;queue.add(root.leftNode);}if (root.leftNode == null && root.rightNode != null){return false;}if (root.leftNode != null && root.rightNode !=null){queue.add(root.leftNode);queue.add(root.rightNode);}//沒子節點的-------------------------}else {if (root.leftNode != null || root.rightNode != null)return false;}}return true;}

判斷兩棵樹是否相等

public boolean isSameTree(Node root,Node otherroot){//先判斷節點是否都存在if (otherroot == null && root == null) return true;else if (otherroot != null && root == null) return false;else if (otherroot == null && root != null) return false;//判斷數據和左右子樹的結果boolean mainresult = (otherroot.data == root.data);boolean leftresult = isSameTree(root.leftNode,otherroot.leftNode);boolean rightresult = isSameTree(root.rightNode,otherroot.rightNode);//結果三個結果做綜合判斷return mainresult && leftresult && rightresult;}

總結

以上是生活随笔為你收集整理的二叉树常用方法（一）的全部內容，希望文章能夠幫你解決所遇到的問題。

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