算法入門篇七 前綴樹

牛客網 左程云老師的算法入門課

找二叉樹的節點的后繼節點

原則

  • 如果節點有右子樹，那么后繼節點就是右子樹的最左邊的第一個節點
  • 如果節點沒有右子樹，如果節點是父節點的右孩子，就繼續往上找，直到找到一個父節點是沿途節點的父節點，且沿途節點是其的左孩子

題目要求

新的二叉樹的類型如下

public class Node{public int value;public Node left;public Node right;public Node parent;public Node(int val){value = val;}
}
  • 比傳統的二叉樹節點相比，多了一個指向父節點的parent指針
  • 頭節點的parent指向空
  • 只有一個二叉樹節點的node，請實現返回node節點的后繼函數。二叉樹的中序遍歷中，node的下一個節點叫做節點的后繼節點。請編寫程序實現此功能：?

代碼

package class05;public class Code08_SuccessorNode {public static class Node {public int value;public Node left;public Node right;public Node parent;public Node(int data) {this.value = data;}}public static Node getSuccessorNode(Node node) {if (node == null) {return node;}if (node.right != null) {return getLeftMost(node.right);} else { // 無右子樹Node parent = node.parent;while (parent != null && parent.left != node) { // 當前節點是其父親節點右孩子node = parent;parent = node.parent;}return parent;}}public static Node getLeftMost(Node node) {if (node == null) {return node;}while (node.left != null) {node = node.left;}return node;}public static void main(String[] args) {Node head = new Node(6);head.parent = null;head.left = new Node(3);head.left.parent = head;head.left.left = new Node(1);head.left.left.parent = head.left;head.left.left.right = new Node(2);head.left.left.right.parent = head.left.left;head.left.right = new Node(4);head.left.right.parent = head.left;head.left.right.right = new Node(5);head.left.right.right.parent = head.left.right;head.right = new Node(9);head.right.parent = head;head.right.left = new Node(8);head.right.left.parent = head.right;head.right.left.left = new Node(7);head.right.left.left.parent = head.right.left;head.right.right = new Node(10);head.right.right.parent = head.right;Node test = head.left.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left.left.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.left.right.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.left.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.left;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right;System.out.println(test.value + " next: " + getSuccessorNode(test).value);test = head.right.right; // 10's next is nullSystem.out.println(test.value + " next: " + getSuccessorNode(test));}}

二叉樹的序列化/反序列化

  • 使用#代表null
  • 每輸出一個數值，就輸出一個_來隔離元素
  • 由樹形結構到字符串的過程叫做序列化，由字符串到樹形結構的過程是反序列化

代碼

package class05;import java.util.LinkedList;
import java.util.Queue;public class Code09_SerializeAndReconstructTree {public static class Node {public int value;public Node left;public Node right;public Node(int data) {this.value = data;}}// 以head為頭的樹，請序列化成字符串返回public static String serialByPre(Node head) {if (head == null) {return "#_";}String res = head.value + "_";res += serialByPre(head.left);res += serialByPre(head.right);return res;}public static Node reconByPreString(String preStr) {String[] values = preStr.split("_");Queue<String> queue = new LinkedList<String>();for (int i = 0; i != values.length; i++) {queue.add(values[i]);}return reconPreOrder(queue);}public static Node reconPreOrder(Queue<String> queue) {String value = queue.poll();if (value.equals("#")) {return null;}Node head = new Node(Integer.valueOf(value));head.left = reconPreOrder(queue);head.right = reconPreOrder(queue);return head;}public static String serialByLevel(Node head) {if (head == null) {return "#!";}String res = head.value + "_";Queue<Node> queue = new LinkedList<Node>();queue.add(head);while (!queue.isEmpty()) {head = queue.poll();if (head.left != null) {res += head.left.value + "_";queue.add(head.left);} else {res += "#_";}if (head.right != null) {res += head.right.value + "_";queue.add(head.right);} else {res += "#_";}}return res;}public static Node reconByLevelString(String levelStr) {String[] values = levelStr.split("_");int index = 0;Node head = generateNodeByString(values[index++]);Queue<Node> queue = new LinkedList<Node>();if (head != null) {queue.add(head);}Node node = null;while (!queue.isEmpty()) {node = queue.poll();node.left = generateNodeByString(values[index++]);node.right = generateNodeByString(values[index++]);if (node.left != null) {queue.add(node.left);}if (node.right != null) {queue.add(node.right);}}return head;}public static Node generateNodeByString(String val) {if (val.equals("#")) {return null;}return new Node(Integer.valueOf(val));}// for test -- print treepublic static void printTree(Node head) {System.out.println("Binary Tree:");printInOrder(head, 0, "H", 17);System.out.println();}public static void printInOrder(Node head, int height, String to, int len) {if (head == null) {return;}printInOrder(head.right, height + 1, "v", len);String val = to + head.value + to;int lenM = val.length();int lenL = (len - lenM) / 2;int lenR = len - lenM - lenL;val = getSpace(lenL) + val + getSpace(lenR);System.out.println(getSpace(height * len) + val);printInOrder(head.left, height + 1, "^", len);}public static String getSpace(int num) {String space = " ";StringBuffer buf = new StringBuffer("");for (int i = 0; i < num; i++) {buf.append(space);}return buf.toString();}public static void main(String[] args) {Node head = null;printTree(head);String pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);String level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");head = new Node(1);printTree(head);pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");head = new Node(1);head.left = new Node(2);head.right = new Node(3);head.left.left = new Node(4);head.right.right = new Node(5);printTree(head);pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");head = new Node(100);head.left = new Node(21);head.left.left = new Node(37);head.right = new Node(-42);head.right.left = new Node(0);head.right.right = new Node(666);printTree(head);pre = serialByPre(head);System.out.println("serialize tree by pre-order: " + pre);head = reconByPreString(pre);System.out.print("reconstruct tree by pre-order, ");printTree(head);level = serialByLevel(head);System.out.println("serialize tree by level: " + level);head = reconByLevelString(level);System.out.print("reconstruct tree by level, ");printTree(head);System.out.println("====================================");}
}

如何判斷一棵子樹是不是另外一棵二叉樹的子樹

  • KMP算法

折紙問題

要求

參考

代碼

package class05;public class Code10_PaperFolding {public static void printAllFolds(int N) {printProcess(1, N, true);}// 遞歸過程，來到了某一個節點，// i是節點的層數，N一共的層數，down == true  凹    down == false 凸public static void printProcess(int i, int N, boolean down) {if (i > N) {return;}printProcess(i + 1, N, true);System.out.println(down ? "凹 " : "凸 ");printProcess(i + 1, N, false);}public static void main(String[] args) {int N = 3;printAllFolds(N);}
}

前綴樹

  • 存儲在邊上，不是節點
  • 節點存放信息:pass創建節點的時候通過這個節點幾次；end：當前節點是多少字符串的結尾
  • 沿途節點的pass++；末尾節點的end++；

例子

加入節點

  • 加入節點ab，使得沿途a之后節點p=3，沿途b之后節點p=2，e=1；
  • 加入節點bcs，使得沿途bc之后節點++，使得s的p=2，e=2；

實現功能

  • 可以查詢abc加入的次數，看的是e的值
  • 可以查詢以ab作為前綴的次數，看的是p的值

刪除節點

  • 沿途節點的p值減1，被刪除的節點的p減1，e減1；并且內存釋放。

代碼

package class07;import java.util.HashSet;public class Code01_TrieTree {public static class TrieNode {public int pass;public int end;// HashMap<Char, Node> nexts;// TreeMap<Char, Node> nexts;public TrieNode[] nexts;public TrieNode() {pass = 0;end = 0;// nexts[0] == null 沒有走向‘a’的路// nexts[0] != null 有走向‘a’的路// ...// nexts[25] != null 有走向‘z’的路nexts = new TrieNode[26];}}public static class Trie {private TrieNode root;public Trie() {root = new TrieNode();}public void insert(String word) {if (word == null) {return;}char[] chs = word.toCharArray();TrieNode node = root;node.pass++;int index = 0;for (int i = 0; i < chs.length; i++) { // 從左往右遍歷字符index = chs[i] - 'a'; // 由字符，對應成走向哪條路if (node.nexts[index] == null) {node.nexts[index] = new TrieNode();}node = node.nexts[index];node.pass++;}node.end++;}public void delete(String word) {if (search(word) != 0) { // 確定樹中確實加入過word，才刪除char[] chs = word.toCharArray();TrieNode node = root;node.pass--;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (--node.nexts[index].pass == 0) {// java C++ 要遍歷到底去析構node.nexts[index] = null;// ...return;}node = node.nexts[index];}node.end--;}}public void deleteCPP(String word) {if (search(word) != 0) { // 確定樹中確實加入過word，才刪除char[] chs = word.toCharArray();TrieNode node = root;node.pass--;int index = 0;TrieNode a = null;int deleteIndex = -1;HashSet<TrieNode> deleteSet = new HashSet<>();for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (--node.nexts[index].pass == 0) {a = a == null ? node : a;deleteIndex = deleteIndex == -1 ? index : deleteIndex;deleteSet.add(node.nexts[index]);}node = node.nexts[index];}node.end--;a.nexts[deleteIndex] = null;// deleteSet ... 析構}}// word這個單詞之前加入過幾次public int search(String word) {if (word == null) {return 0;}char[] chs = word.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.end;}// 所有加入的字符串中，有幾個是以pre這個字符串作為前綴的public int prefixNumber(String pre) {if (pre == null) {return 0;}char[] chs = pre.toCharArray();TrieNode node = root;int index = 0;for (int i = 0; i < chs.length; i++) {index = chs[i] - 'a';if (node.nexts[index] == null) {return 0;}node = node.nexts[index];}return node.pass;}}public static void main(String[] args) {Trie trie = new Trie();System.out.println(trie.search("zuo"));trie.insert("zuo");System.out.println(trie.search("zuo"));trie.delete("zuo");System.out.println(trie.search("zuo"));trie.insert("zuo");trie.insert("zuo");trie.delete("zuo");System.out.println(trie.search("zuo"));trie.delete("zuo");System.out.println(trie.search("zuo"));trie.insert("zuoa");trie.insert("zuoac");trie.insert("zuoab");trie.insert("zuoad");trie.delete("zuoa");System.out.println(trie.search("zuoa"));System.out.println(trie.prefixNumber("zuo"));}}

?

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/447211.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/447211.shtml
英文地址，請注明出處：http://en.pswp.cn/news/447211.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

VLC視頻播放器原理詳細分析含TS流格式分析

VLC視頻播放器原理詳細分析含TS流格式分析

vlc是一個功能強大的玩意&#xff0c;能做很多有意思的事情。最簡單的&#xff0c;從界面打開一個文件播放&#xff0c;也可以在命令行下使用&#xff0c;如C:\Program Files\VideoLAN\VLC>vlc.exe test.ts獲取內置的幫助&#xff0c;會寫到vlc-help.txtC:\Program Files\Vi…
閱讀更多...
算法入門篇八 貪心算法

算法入門篇八 貪心算法

牛客網 左程云老師的算法入門課 貪心算法 貪心算法的解題步驟 例子 題目要求 解題策略 按照結束時間早的會議先安排&#xff0c;比如先安排【2&#xff0c;4】&#xff0c;當4結束了&#xff0c;所有開始時間小于4的全部淘汰&#xff0c;【1&#xff0c;7】、【3&#xff…
閱讀更多...
算法入門篇九 暴力遞歸

算法入門篇九 暴力遞歸

牛客網 左程云老師的算法入門課 暴力遞歸 原則 漢諾塔問題 問題 打印n層漢諾塔從左邊移動到最右邊的過程 思想 一共六個過程&#xff0c;左到右、左到中&#xff0c;中到左&#xff0c;中到右&#xff0c;右到左&#xff0c;右到中&#xff0c;互相嵌套使用 左到右 將1…
閱讀更多...
rtsp和sdp

rtsp和sdp

RTSP 是由Realnetwork 和Netscape共同提出的如何有效地在IP網絡上傳輸流媒體數據的應用層協議 。 實時流協議&#xff08;RTSP&#xff09;建立并控制一個或幾個時間同步的連續流媒體&#xff0c;如音頻和視頻。盡管連續媒體流與控制流交叉是可能的&#xff0c;RTSP本身并不發…
閱讀更多...
使用javascript實現對于chineseocr的API調用

使用javascript實現對于chineseocr的API調用

ChineseOCR在線API 網頁地址 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別在線Javascript工具 在線工具網頁鏈接在線Base64 轉化工具 在線工具…
閱讀更多...
移動流媒體業務的技術與標準

移動流媒體業務的技術與標準

1 引言 　　流媒體業務是從Internet上發展起來的一種多媒體應用&#xff0c;指使用流&#xff08;Streaming&#xff09;方式在網絡上傳輸的多媒體文件&#xff0c;包括音頻、視頻和動畫等。 　　流媒體傳輸技術的主要特點是以流&#xff08;streaming&#xff09;的形式進行多…
閱讀更多...
使用python實現對于chineseocr的API調用

使用python實現對于chineseocr的API調用

ChineseOCR在線API 網頁鏈接 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別在線Base64 轉化工具 Base64在線小工具代碼修改 新增一個變量fill_w…
閱讀更多...
UDP穿透NAT

UDP穿透NAT

NAT(Network AddressTranslators)&#xff0c;網絡地址轉換&#xff1a; 網絡地址轉換是在IP地址日益缺乏的情況下產生的&#xff0c;它的主要目的就是為了能夠地址重用。NAT分為兩大類&#xff0c;基本的NAT和NAPT(Network Address/Port Translator)。 最開始NAT是運行在路由器…
閱讀更多...
算法入門篇十 圖

算法入門篇十 圖

圖的存儲方式 臨接表臨接矩陣 表達 點集/邊集有向圖/無向圖 Graph&#xff08;大結構就是圖&#xff09;&#xff08;包含點集合和邊集合&#xff09; import java.util.HashMap; import java.util.HashSet;public class Graph {public HashMap<Integer, Node> nodes;…
閱讀更多...
SDP協議 學習筆記

SDP協議 學習筆記

SDP:Session Description ProtocolSDP格式:Session descriptionv (protocolversion)o (owner/creatorand session identifier)s (sessionname)i* (sessioninformation)u* (URI ofdescription)e* (emailaddress)p* (phonenumber)c*(connection information - not required if in…
閱讀更多...
以太坊私有鏈 使用dev模式

以太坊私有鏈 使用dev模式

dev 使用dev模式&#xff0c;創建一個管理員賬號&#xff0c;控制挖礦&#xff0c;將證明機制改為POA啟動dev模式&#xff0c;需要重新創建一個文件夾&#xff0c;重新搭建私有鏈條 命令 mkdir myDevChain cd myDevChain geth --datadir . --dev console 2>output.log 實…
閱讀更多...
超文本傳輸協議

超文本傳輸協議

超文本傳輸協議 超文本傳輸協議超文件傳輸協定(HTTP&#xff0c;HyperTextTransfer Protocol)是因特網上應用最為廣泛的一種網絡傳輸協定。所有的WWW文件都必須遵守這個標準。設計HTTP最初的目的是為了提供一種發布和接收HTML頁面的方法。 目錄 介紹請求信息請求方法安全方法超…
閱讀更多...
以太坊區塊鏈 JSON-RPC

以太坊區塊鏈 JSON-RPC

RPC定義 以太坊客戶端提供了API和一組遠程調用的&#xff08;RPC&#xff09;命令&#xff0c;這些命令被編碼成json的格式&#xff0c;被叫做JSON-RPC-API。本質上&#xff0c;JSON-RPC API就是一個接口&#xff0c;允許我們編寫的程序使用以太坊客戶端作為網關&#xff0c;訪…
閱讀更多...
利用MFC調用libvlc.dll作一個簡單的播放器

利用MFC調用libvlc.dll作一個簡單的播放器

簡單介紹MFC調用libvlc.dll作一個簡單的播放器&#xff0c;拋磚引玉&#xff0c;各位VC達人繼續深入研究&#xff0c;Jeremiah對VC確實不太感興趣&#xff0c;所以就不做太深入的研究了。2009.10.29修改&#xff1a;加入clip_children屬性設置。參開第1步。環境&#xff1a; …
閱讀更多...
對于以太坊虛擬機 （EVM）及其相關知識的講解

對于以太坊虛擬機 （EVM）及其相關知識的講解

以太坊虛擬機&#xff08;EVM&#xff09; EVM是智能合約的運行環境作為區塊驗證協議的一部分&#xff0c;參與網絡的每個節點都會運行EVM&#xff0c;審查節點會檢查驗證正在驗證的區塊中列出的交易&#xff0c;并運行EVM中交易觸發的代碼EVM是沙盒封裝的&#xff0c;并且是完…
閱讀更多...
對于以太坊的Solidity語言介紹

對于以太坊的Solidity語言介紹

Solidity是什么 Solidity是一門面向合約的、為實現智能合約而創建的高級編程語言&#xff0c;主要目的是為了在以太坊虛擬機&#xff08;EVM&#xff09;上運行Solidity是靜態語言&#xff0c;支持繼承、庫和復雜的用戶定義等特性內含的類型除了常見的編程語言中的標準類型&am…
閱讀更多...
live555 接收rtsp視頻流流程分析

live555 接收rtsp視頻流流程分析

live555 接收rtsp視頻流流程分析 RTSP交互流程 C表示RTSP客戶端&#xff0c;S表示RTSP服務端 ① C->S: OPTIONrequest //詢問S有哪些方法可用 S->C: OPTION response //S回應信息中包括提供的所有可用方法 ② C->S: DESCRIBErequest //要求得到S…
閱讀更多...
使用Remix編寫Solidity語言的小例子

使用Remix編寫Solidity語言的小例子

設置數值/取數值/加法運算 講解 uint默認使用256位數的整型view表示這個函數僅僅對于數據僅僅是讀取&#xff0c;沒有修改操作returns(uint )&#xff0c;如果單純指定uint&#xff0c;返回的是函數體內的return值&#xff0c;如果包含uint sum,uint SAD_a&#xff0c;那么返…
閱讀更多...
RTP協議棧簡介

RTP協議棧簡介

流媒體指的是在網絡中使用流技術傳輸的連續時基媒體&#xff0c;其特點是在播放前不需要下載整個文件&#xff0c;而是采用邊下載邊播放的方式&#xff0c;它是視頻會議、IP電話等應用場合的技術基礎。RTP是進行實時流媒體傳輸的標準協議和關鍵技術&#xff0c;本文介紹如何在L…
閱讀更多...
深入理解Solidity

深入理解Solidity

Solidity源文件布局 pragma&#xff08;版本雜注&#xff09; 用于指定源文件的版本&#xff0c;表明編譯器的版本&#xff0c;例如 pragma solidity ^0.4.0^用于指代版本號需要大于0.4.0但是不可以超過大的層級&#xff0c;必須小于0.5.0也可以使用大于等于小于來指定版本 i…
閱讀更多...
最新文章

Copyright @ 2022~2023