摘要:樹和樹的算法一樹樹的概念樹英語是一種抽象數據類型或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。一種時間復雜度額外空間復雜度的二叉樹的遍歷方式,為二叉樹的節點個數。
樹和樹的算法 一、樹 1.1 樹的概念
樹(英語:tree)是一種抽象數據類型(ADT)或是實作這種抽象數據類型的數據結構,用來模擬具有樹狀結構性質的數據集合。它是由n(n>=1)個有限節點組成一個具有層次關系的集合。把它叫做“樹”是因為它看起來像一棵倒掛的樹,也就是說它是根朝上,而葉朝下的。它具有以下的特點:
每個節點有零個或多個子節點;
沒有父節點的節點稱為根節點;
每一個非根節點有且只有一個父節點;
除了根節點外,每個子節點可以分為多個不相交的子樹;
1.2 樹的術語節點的度:一個節點含有的子樹的個數稱為該節點的度;
樹的度:一棵樹中,最大的節點的度稱為樹的度;
葉節點或終端節點:度為零的節點;
父親節點或父節點:若一個節點含有子節點,則這個節點稱為其子節點的父節點;
孩子節點或子節點:一個節點含有的子樹的根節點稱為該節點的子節點;
兄弟節點:具有相同父節點的節點互稱為兄弟節點;
節點的層次:從根開始定義起,根為第1層,根的子節點為第2層,以此類推;
樹的高度或深度:樹中節點的最大層次;
堂兄弟節點:父節點在同一層的節點互為堂兄弟;
節點的祖先:從根到該節點所經分支上的所有節點;
子孫:以某節點為根的子樹中任一節點都稱為該節點的子孫。
森林:由m(m>=0)棵互不相交的樹的集合稱為森林;
1.3 樹的種類 1.3.1無序樹:樹中任意節點的子節點之間沒有順序關系,這種樹稱為無序樹,也稱為自由樹;
1.3.2 有序樹樹中任意節點的子節點之間有順序關系,這種樹稱為有序樹;
二叉樹:每個節點最多含有兩個子樹的樹稱為二叉樹;
完全二叉樹:對于一顆二叉樹,假設其深度為d(d>1)。除了第d層外,其它各層的節點數目均已達最大值,且第d層所有節點從左向右連續地緊密排列,這樣的二叉樹被稱為完全二叉樹,其中滿二叉樹的定義是所有葉節點都在最底層的完全二叉樹;
平衡二叉樹(AVL樹):當且僅當任何節點的兩棵子樹的高度差不大于1的二叉樹;
排序二叉樹(二叉查找樹(英語:Binary Search Tree),也稱二叉搜索樹、有序二叉樹)
霍夫曼樹(用于信息編碼):帶權路徑最短的二叉樹稱為哈夫曼樹或最優二叉樹;
B樹:一種對讀寫操作進行優化的自平衡的二叉查找樹,能夠保持數據有序,擁有多余兩個子樹。
順序存儲:將數據結構存儲在固定的數組中,然在遍歷速度上有一定的優勢,但因所占空間比較大,是非主流二叉樹。二叉樹通常以鏈式存儲。
1.5 常見的一些樹的應用場景xml,html等,那么編寫這些東西的解析器的時候,不可避免用到樹
路由協議就是使用了樹的算法
mysql數據庫索引
文件系統的目錄結構
所以很多經典的AI算法其實都是樹搜索,此外機器學習中的decision tree也是樹結構
二、二叉樹 2.1 二叉樹的基本概念二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”(left subtree)和“右子樹”(right subtree)
2.2 二叉樹的性質(特性)性質1: 在二叉樹的第i層上至多有2^(i-1)個結點(i>0)
性質2: 深度為k的二叉樹至多有2^k - 1個結點(k>0)
性質3: 對于任意一棵二叉樹,如果其葉結點數為N0,而度數為2的結點總數為N2,則N0=N2+1;
性質4:具有n個結點的完全二叉樹的深度必為 log2(n+1)
性質5:對完全二叉樹,若從上至下、從左至右編號,則編號為i 的結點,其左孩子編號必為2i,其右孩子編號必為2i+1;其雙親的編號必為i/2(i=1 時為根,除外)
(1)完全二叉樹——若設二叉樹的高度為h,除第 h 層外,其它各層 (1~h-1) 的結點數都達到最大個數,第h層有葉子結點,并且葉子結點都是從左到右依次排布,這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
2.3 二叉樹的節點表示以及樹的創建 2.3.1 Python 建樹通過使用Node類中定義三個屬性,分別為elem本身的值,還有lchild左孩子和rchild右孩子
class Node(object): """節點類""" def __init__(self, elem=-1, lchild=None, rchild=None): self.elem = elem self.lchild = lchild self.rchild = rchild 樹的創建,創建一個樹的類,并給一個root根節點,一開始為空,隨后添加節點 class Tree(object): """樹類""" def __init__(self, root=None): self.root = root def add(self, elem): """為樹添加節點""" node = Node(elem) #如果樹是空的,則對根節點賦值 if self.root == None: self.root = node else: queue = [] queue.append(self.root) #對已有的節點進行層次遍歷 while queue: #彈出隊列的第一個元素 cur = queue.pop(0) if cur.lchild == None: cur.lchild = node return elif cur.rchild == None: cur.rchild = node return else: #如果左右子樹都不為空,加入隊列繼續判斷 queue.append(cur.lchild) queue.append(cur.rchild)2.3.2 Java的建樹
Node節點類:
class Node{ public int value; public Node lChild; public Node rChild; public Node(int value){ this.value = value; } }
Tree類:
class Tree{ public Node root; //根節點初始化 public Tree(Node node){ root = node; } //樹中通過廣度優先遍歷的方式尋找空位置加新節點 public void add(int value){ Node temp = new Node(value); if(root==null){ root = temp; } Queue三、二叉樹的遍歷queue = new LinkedList (); queue.add(root); while(!queue.isEmpty()) { Node curNode = queue.poll(); if (curNode.lChild == null) { curNode.lChild = temp; return; } else if (curNode.rChild == null) { curNode.rChild = temp; return; } else { queue.add(curNode.lChild); queue.add(curNode.rChild); } } } }
樹的遍歷是樹的一種重要的運算。所謂遍歷是指對樹中所有結點的信息的訪問,即依次對樹中每個結點訪問一次且僅訪問一次,我們把這種對所有節點的訪問稱為遍歷(traversal)。那么樹的兩種重要的遍歷模式是深度優先遍歷和廣度優先遍歷,深度優先一般用遞歸,廣度優先一般用隊列。一般情況下能用遞歸實現的算法大部分也能用堆棧來實現(掌握先序、中序、后序的非遞歸方式)。
3.1 深度優先遍歷對于一顆二叉樹,深度優先搜索(Depth First Search)是沿著樹的深度遍歷樹的節點,盡可能深的搜索樹的分支。
那么深度遍歷有重要的三種方法。這三種方式常被用于訪問樹的節點,它們之間的不同在于訪問每個節點的次序不同。這三種遍歷分別叫做先序遍歷(preorder),中序遍歷(inorder)和后序遍歷(postorder)。我們來給出它們的詳細定義,然后舉例看看它們的應用。
遞歸實現先序、中序、后序非常強大的地方是每個都會訪問同一個節點三次,所以三個遍歷方式只是調換一下函數執行順序。
無論是否是遞歸方式都用到了棧(函數棧也是棧):因為樹的結構是從上到下訪問,如果要返回去訪問另一處的節點,那么必須要有棧來“記憶”。
3.1.1 先序遍歷在先序遍歷中,我們先訪問根節點,然后遞歸使用先序遍歷訪問左子樹,再遞歸使用先序遍歷訪問右子樹
根節點->左子樹->右子樹
Python代碼實現:
def preorder(self, root): """遞歸實現先序遍歷""" if root == None: return print root.elem self.preorder(root.lchild) self.preorder(root.rchild)
Java代碼實現(遞歸方式):
public class PreOrder { private void preOrder(Node node){ if(node == null){ return; } System.out.println(node.value); preOrder(node.lChild); preOrder(node.rChild); } public static void main(String[] args){ PreOrder sort = new PreOrder(); Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); sort.preOrder(tree.root); } }
Java 代碼實現(非遞歸方式):
public void preOrderUnRecur(Node head){ System.out.print("preOrder:"); if(head!=null){ //利用棧來實現 Stack3.1.2 中序遍歷stack = new Stack (); stack.push(head); while(!stack.isEmpty()){ Node node = stack.pop(); System.out.print(node.value + " "); //先壓進右孩子,利用先進后出原則 if(node.rChild!=null){ stack.push(node.rChild); } if(node.lChild!=null){ stack.push(node.lChild); } } } }
在中序遍歷中,我們遞歸使用中序遍歷訪問左子樹,然后訪問根節點,最后再遞歸使用中序遍歷訪問右子樹
左子樹->根節點->右子樹
Python代碼實現:
def inorder(self, root): """遞歸實現中序遍歷""" if root == None: return self.inorder(root.lchild) print root.elem self.inorder(root.rchild)
Java代碼實現(遞歸方式):
public class InOrder { public void inOrder(Node node){ if(node==null){ return; } inOrder(node.lChild); System.out.println(node.value); inOrder(node.rChild); } public static void main(String[] args){ Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); InOrder sort = new InOrder(); sort.inOrder(tree.root); } }
Java實現(非遞歸方式):
public void inOrderUnRecur(Node head){ System.out.print("InOrder:"); if(head!=null){ Stack3.1.3 后序遍歷stack = new Stack<>(); while(!stack.isEmpty() || head!=null){ if(head != null){ stack.push(head); head = head.lChild; }else{ head = stack.pop(); System.out.print(head.value + " "); head = head.rChild; } } } }
在后序遍歷中,我們先遞歸使用后序遍歷訪問左子樹和右子樹,最后訪問根節點
左子樹->右子樹->根節點
Python代碼實現:
def postorder(self, root): """遞歸實現后續遍歷""" if root == None: return self.postorder(root.lchild) self.postorder(root.rchild) print root.elem
Java代碼實現(遞歸方式):
public class PostOrder { public void postOrder(Node node){ if(node==null){ return; } postOrder(node.lChild); postOrder(node.rChild); System.out.println(node.value); } public static void main(String[] args) { Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); PostOrder sort = new PostOrder(); sort.postOrder(tree.root); } }
Java代碼實現(非遞歸方式:采用輔助空間方式,把先序(中右左)存儲到輔助棧,然后根據先進后出打印出結果就是后序遍歷結果(左右中)):
public void postOrderUnRecur(Node head){ System.out.print("postOrder:"); if(head!=null){ Stackstack1 = new Stack (); Stack stack2 = new Stack (); stack1.push(head); while(!stack1.isEmpty()){ head = stack1.pop(); stack2.push(head); //與先序的不同:先序打印,后序存儲起來 if(head.lChild!=null){ stack1.push(head.lChild); } if(head.rChild!=null){ stack1.push(head.rChild); } } //利用棧先進后出原則輸出后序遍歷結果 while(!stack2.isEmpty()){ head = stack2.pop(); System.out.print(head.value + " "); } } }
思考:哪兩種遍歷方式能夠唯一的確定一顆樹???
3.2 廣度優先遍歷(層次遍歷)通過一個隊列的方法來實現
從樹的root開始,從上到下從從左到右遍歷整個樹的節點
def breadth_travel(self, root): """利用隊列實現樹的層次遍歷""" if root == None: return queue = [] queue.append(root) while queue: node = queue.pop(0) print node.elem, if node.lchild != None: queue.append(node.lchild) if node.rchild != None: queue.append(node.rchild)3.3 Morris 遍歷
二叉樹的遍歷一般額外空間復雜度為O(logn),根據高度來的(節點回到自身需要保存到棧中),要回到上一個很難(通過棧解決)。
一種時間復雜度O(n),額外空間復雜度O(1)的二叉樹的遍歷方式,N為二叉樹的節點個數。
Morris 遍歷規則:
來到當前節點,記為cur,如果cur無左孩子,cur向右移動cur = cur.right
如果cur有左孩子:找到左子樹上最右節點,記為mostright,①如果mostright的right指針指向空,讓其指向cur,然后cur向左移動cur = cur.left ②如果mostright指向cur,讓其指向空,cur向右移動。
public static void morrisIn(Node head){ if(head == null){ return; } Node cur = head; Node mostRight = null; while(cur!=null){ mostRight = cur.left; if(mostRight!=null){ //有左孩子,找到左子樹的最右節點 while(mostRight.right!=null && mostRight.right!=cur){ mostRight = mostRight.right; } if(mostRight.right == null){ mostRight.right = cur; cur = cur.left; continue; }else{ mostRight.right = null; } } System.out.print(cur.value + " ");//要往右節點走了,就是中序遍歷 cur = cur.right; } }
如果一個節點有左子樹,morris能回到節點兩次。如果沒有左子樹,只到節點一次。
morris改先序遍歷
public static void morrisPre(Node head){ if(head == null){ return; } Node cur = head; Node mostRight = null; while(cur!=null){ mostRight = cur.left; if(mostRight!=null){ while(mostRight.right!=null && mostRight.right!=cur){ mostRight = mostRight.right; } if(mostRight.right == null){ mostRight.right = cur; System.out.print(cur.value + " ") cur = cur.left; continue; }else{ mostRight.right = null; } }else{ System.out.print(cur.value + " "); } cur = cur.right; } System.out.println(); }
后序遍歷是第三次回到節點時候打印的,但是morris沒有回到節點第三次的。
怎么做?
先去關注能回到節點兩次的節點,逆序打印它左子樹的右邊界。退出函數時多帶帶打印整棵樹的右邊界
public static void morrisPos(Node head){ if(head == null){ return; } Node cur1 = head; Node cur2 = head; while(cur1 !=null) { cur2 = cur1.left; if(cur2!=null){ while(cur2.right!=null && cur2.right!=cur1){ cur2 = cur2.right; } if(cur2.right==null){ cur2.right = cur1; cur1 = cur1.left; continue; }else{ cur2.right = null; printEdge(cur1.left); } } cur1 = cur1.right; } printEdge(head); System.out.println(); }
怎么實現逆序打印?
采用鏈表逆序的方法,打印完再調整回來,這樣就沒有引入額外空間復雜度
先序 + 中序
思想:
先序取第一位即是根,然后根據這個元素找到中序的左子樹和右子樹
先判斷左子樹,先序除了第一位后是連續的一塊左子樹的元素和連續的一塊右子樹元素,去先序連續一塊左子樹的第一位,再到中序去分割新的左子樹和右子樹
通過重復2,可以畫出一個樹
中序+后序也可以
4.2 二叉樹中找到一個節點的后繼節點題目:現有一種新的二叉樹節點類型如下
public class Node{ public int value; public Node left; public Node right; public Node parent; public Node(int value){ this.value = value; } }
這個結構只比普通二叉樹節點結構多了一個指向父節點的parent指針。假設一棵Node類型的節點組成的二叉樹,樹中每個節點的parent指針都正確地指向父節點,頭節點的parent指向Null,只給一個在二叉樹中的某個節點Node,請實現返回node的后繼節點的函數。在二叉樹的中序遍歷的序列中,node的下一個節點叫作node的后繼節點。
解決思路:如果一個節點有右子樹,那么右子樹的左邊界(整個樹最左下角)節點一定是它的后繼節點;如果沒有右子樹,通過這個節點的父指針parent指向父節點,如果發現這個節點是父節點的右孩子,就繼續往上,一直到某個節點是它父節點的左孩子,那么這個最初節點的后繼就是這個父節點。
Java 代碼創建特殊的節點類:
public class FatherPointNode { public int value; public FatherPointNode lChild; public FatherPointNode rChild; public FatherPointNode parent; public FatherPointNode(int value){ this.value = value; } }
Java 代碼創建特殊的樹類:
public class FatherPointTree { public FatherPointNode root; //根節點初始化 public FatherPointTree(FatherPointNode node){ root = node; } //樹中通過廣度優先遍歷的方式尋找空位置加新節點 public void add(int value){ FatherPointNode temp = new FatherPointNode(value); if(root==null){ root = temp; } Queuequeue = new LinkedList (); queue.add(root); while(!queue.isEmpty()) { FatherPointNode curNode = queue.poll(); if (curNode.lChild == null) { curNode.lChild = temp; temp.parent = curNode; //與原來的樹不同地方:添加父節點 return; } else if (curNode.rChild == null) { curNode.rChild = temp; temp.parent = curNode; return; } else { queue.add(curNode.lChild); queue.add(curNode.rChild); } } } }
Java 代碼找后繼節點:
public class SuccessorNode { public FatherPointNode successorNode(FatherPointNode node){ if(node==null){ return null; } if(node.rChild!=null){ return getLeftMost(node); //找右子樹的左邊界節點 }else{ while(node.parent!=null && node.parent.lChild!=node){ node = node.parent; } return node.parent; } } public FatherPointNode getLeftMost(FatherPointNode node){ if(node!=null){ while(node.lChild!=null){ node = node.lChild; } return node; } return null; } public static void main(String[] args) { FatherPointTree tree = new FatherPointTree(new FatherPointNode(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); SuccessorNode sn = new SuccessorNode(); FatherPointNode result = sn.successorNode(tree.root.lChild.rChild);//節點4,后序節點應該是為0; System.out.println(tree.root.lChild.rChild.value + " 后續節點:" + result.value); result = sn.successorNode(tree.root.lChild);//節點3,后序節點應該是為1; System.out.println(tree.root.lChild.value + " 后續節點:" + result.value); } }
先驅節點:節點有左子樹,那么左子樹的右節點一定是它的前驅。如果沒有左子樹,往上找,如果一個節點是父節點的右孩子,那么這個父節點就是前驅節點
4.3 二叉樹的序列化與反序列化序列化:
eg:
1
2 3
4 5 6 7
先先序遍歷變成字符串:1_2_4_#_#_5_#_#_3_6_#_#_7_#_#_
用“#”來占住位置,用_可以區分節點,否則124,都在一起無法區分了
Java代碼實現:
public class SerialTree { //通過先序遍歷改編成序列化,原來打印處改為添加到字符串 public static String serialTree(Node curNode){ if(curNode==null){ return "#_"; //子節點為null用#占住 } String res = ""; res += curNode.value+"_"; res += serialTree(curNode.lChild); res += serialTree(curNode.rChild); return res; } public static void main(String[] args) { Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); String result = serialTree(tree.root); System.out.println(result); } }
序列化+反序列化完整代碼:
import java.util.LinkedList; import java.util.Queue; public class SerialTree { public static String serialTree(Node curNode){ if(curNode==null){ return "#_"; } String res = ""; res += curNode.value+"_"; res += serialTree(curNode.lChild); res += serialTree(curNode.rChild); return res; } //解析字符串,將節點信息存入到隊列中 public static Node reconByPreString(String preString){ String[] value = preString.split("_"); Queuequeue = new LinkedList (); for (int i = 0; i < value.length; i++) { queue.offer(value[i]); } return reconPreOrder(queue); } //根據隊列的信息遞歸生成節點 public static Node reconPreOrder(Queue queue){ String value = queue.poll(); if(value.equals("#")){ return null; } Node head = new Node(Integer.valueOf(value)); head.lChild = reconPreOrder(queue); head.rChild = reconPreOrder(queue); return head; } //采用先序遍歷打印來驗證反序列化結果是否正確 public static void preOrder(Node node){ if(node == null){ return; } System.out.print(node.value + " "); preOrder(node.lChild); preOrder(node.rChild); } public static void main(String[] args) { Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); String result = serialTree(tree.root); System.out.println(result); Node head = reconByPreString(result); System.out.println("驗證反序列化樹(先序遍歷結果):"); preOrder(head); } }
同理可以學習中序、后序,層次化的序列化和反序列化4.4 判斷二叉樹是否是平衡二叉樹
平衡二叉樹:一個樹的任一節點的左子樹和右子樹的高度差不超過1。
套路:遞歸函數
有什么特點?到達一個節點三次!
第一次來到這個節點,左子樹轉一圈完回到這個節點,右子樹轉一圈完回到這個節點
解題思路:以每個節點為頭的子樹判斷是否平衡,如果都平衡那么這個樹就是平衡的。
對于每個節點的判斷:
左樹是否平衡?如果不平衡后續就不用判斷了
右樹是否平衡?
左樹平衡和右樹平衡的情況下,需要左樹和右樹高度信息
因此遞歸函數需要返回兩個信息(通過一個對象返回,成員變量為 ①是否平衡 ②高度)
Java 代碼實現:
//創建返回數據類:攜帶是否平衡信息和高度信息 class ReturnData{ public boolean isB; public int high; public ReturnData(boolean isB, int high){ this.isB = isB; this.high = high; } } public class IsBalanceTree { public static ReturnData processData(Node head){ if(head==null){ return new ReturnData(true, 0); } ReturnData leftData = processData(head.lChild); if(!leftData.isB){ return new ReturnData(false,0); } ReturnData rightData = processData(head.rChild); if(!rightData.isB){ return new ReturnData(false,0); } if(Math.abs(leftData.high-rightData.high)>1){ return new ReturnData(false,0); } return new ReturnData(true,Math.max(leftData.high,rightData.high)+1); } public static boolean isBalance(Node head){ return processData(head).isB; } public static void main(String[] args) { Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); Boolean result = isBalance(tree.root); System.out.println("是否是平衡樹?:" + result); } }4.5 如何判斷一棵樹是二叉搜索樹
二叉搜索樹:任何一個節點,左子樹都比它小,右子樹都比它大。
解題思路:二叉樹的中序遍歷節點是依次升序的就是搜索二叉樹。用非遞歸版本的中序遍歷中與前一個值進行比較:一旦產生前一個節點比后一個節點要大,說明不是二叉搜索樹。
通常搜索二叉樹是不出現重復節點的,一般重復的節點的信息都是壓到一個節點內的(如前綴樹)。
Java代碼實現:
import java.util.Stack; public class IsBST { public static boolean isBST(Node head){ if(head==null){ return false; } Stackstack = new Stack<>(); int value = Integer.MIN_VALUE; while(!stack.isEmpty() || head!=null){ if(head!=null){ //注意判斷條件不要寫成了head.lChild!=null stack.push(head); head = head.lChild; }else{ head = stack.pop(); if(head.value 4.6 怎么判斷一棵樹是否是完全二叉樹 判斷方式:二叉樹按層遍歷
判斷依據:一個節點有右孩子但是沒有左孩子 ,一定不是完全二叉樹
如果一個節點不是左右孩子都全,在1的條件下,后面遇到的所有節點都必須是葉節點,否則就不是完全二叉樹
Java 代碼實現:
import java.util.LinkedList; import java.util.Queue; public class IsCBT { public static boolean isCBT(Node head){ if(head==null){ return false; } Queuequeue = new LinkedList (); queue.offer(head); Node lChild = null; Node rChild = null; boolean leaf = false; while(!queue.isEmpty()){ head = queue.poll(); lChild = head.lChild; rChild = head.rChild; //判斷第一種情況:右孩子不為null,左孩子為null if((leaf && (lChild!=null && rChild!=null)) || (lChild==null && rChild!=null)){ return false; } if(lChild!=null){ queue.offer(lChild); }else{ leaf = true; //出現情況:左孩子不為Null,右孩子為Null 或者 左右孩子都為Null,之后為葉節點。 } } return true; } } 補充知識:使用二叉樹實現堆比數組的節省了擴容代價4.7 已知一棵完全二叉樹,求節點的個數題目要求:時間復雜度低于O(n),n為這棵樹的節點個數
時間復雜度低于O(n),說明無法采用廣度優先遍歷的方式獲取解題思路:
先遍歷左子樹的左邊界,記錄層數(完全二叉樹性質,這個就是樹的層數),時間復雜度為O(logn)
遍歷右子樹的左邊界,是不是到了最后一層,如果到達最后一層那么左子樹就是滿二叉樹,如果不是,那么左子樹可能滿可能不滿。
如果右子樹的左邊界不是到最后一層(右子樹少一層:右子樹節點總數=1<<(h-level-1)),那么節點總數等于 1<<(h-level-1)+左樹遞歸求總數
補充知識點:如果一棵樹是一棵滿二叉樹,高度是l,那么節點個數是2^l -1Java 代碼實現:
public class TreeNodeNum { public static int treeNodeNum(Node head){ if(head==null){ return 0; } return bs(head,1, mostLeftLevel(head,1)); } //h:樹的深度, level:當前層數 public static int bs(Node node, int level, int h){ //如果level==h,說明當前節點是葉節點,節點個數為1 if(level == h){ return 1; } if(mostLeftLevel(node.rChild,level + 1) == h){ System.out.println("左子樹滿"); return (1<<(h-level)) + bs(node.rChild,level+1, h); }else{ System.out.println("左子樹不一定滿"); return (1 << (h-level-1)) + bs(node.lChild, level+1, h); } } public static int mostLeftLevel(Node node,int level){ while(node!=null){ level++; node = node.lChild; } return level-1; } public static void main(String[] args) { Tree tree = new Tree(new Node(0)); tree.add(1); tree.add(2); tree.add(3); tree.add(4); int result = treeNodeNum(tree.root); System.out.println("完全二叉樹的節點數目:" + result); } }結果:算法的時間復雜度 O(logn)平方
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/42397.html
摘要:通過主機名,最終得到該主機名對應的地址的過程叫做域名解析或主機名解析。因此去掉不必要的資源和資源合并包括及資源合并雪碧圖等才會成為性能優化繞不開的方案。 作者:李佳曉 原文:學而思網校技術團隊 前言 合格的開發者知道怎么做,而優秀的開發者知道為什么這么做。 這句話來自《web性能權威指南》,我一直很喜歡,而本文嘗試從瀏覽器渲染原理探討如何進行性能提升。全文將從網絡通信以及頁面渲染兩個...
摘要:圖是構成網頁的超文本標記語言中的標簽相互關聯關系所構成的樹。節點節點是樹的基本構成部分。子樹子樹是一個父節點的某個子節點的所有邊和后代節點所構成的集合。高度樹的高度等于所有節點的層數的最大值。每個子樹的根節點和其父樹的根節點之間通過邊相連。 樹的例子 我們已經學過了像棧和隊列這樣的線性數據結構,同時我們對遞歸也有了一定的了解,現在讓我們來看看另一種常見的數據結構——樹(Tree)。樹在...
摘要:很多文章或書籍在介紹紅黑樹的時候直接上來就是紅黑樹的個基本性質插入刪除操作等。這也不奇怪,算法的作者就是紅黑樹的作者之一。所以,理解樹對掌握紅黑樹是至關重要的。 本文主要包括以下內容: 什么是2-3樹 2-3樹的插入操作 紅黑樹與2-3樹的等價關系 《算法4》和《算法導論》上關于紅黑樹的差異 紅黑樹的5條基本性質的分析 紅黑樹與2-3-4樹的等價關系 紅黑樹的插入、刪除操作 JDK ...
閱讀 3154·2021-11-22 14:45
閱讀 3300·2019-08-29 13:11
閱讀 2306·2019-08-29 12:31
閱讀 922·2019-08-29 11:21
閱讀 2991·2019-08-29 11:09
閱讀 3616·2019-08-28 18:11
閱讀 1420·2019-08-26 13:58
閱讀 1273·2019-08-26 13:27