摘要:節(jié)點類二叉樹類實現(xiàn)了二叉樹插入刪除查找前序遍歷中序遍歷后序遍歷層序遍歷二叉樹序列化和反序列化二叉樹的常見操作增加刪除查找先序中序后序?qū)有虮闅v序列化二叉樹先序?qū)有蛐蛄谢头葱蛄谢刃蚍葱蛄谢瘜有蛐蛄谢瘜有蚍葱蛄谢瘮?shù)據(jù)測試建立一棵二叉樹參考資料
節(jié)點類
public class Node { public Node left; public Node right; public int data; public Node(int data){ this.left = null; this.right = null; this.data = data; } }二叉樹類
實現(xiàn)了二叉樹插入、刪除、查找、前序遍歷、中序遍歷、后序遍歷、層序遍歷、二叉樹序列化和反序列化
import java.util.LinkedList; import java.util.Queue; import java.util.Stack; public class BinaryTree { public Node root; public BinaryTree() { this.root=null; } /** * 二叉樹的常見操作 * 增加、刪除、查找 */ public void insert(int data){ Node node=new Node(data); if(this.root==null){ this.root=node; }else{ Node current=this.root; Node parent; while(true){ parent=current; if(data /** * 先序、中序、后序、層序遍歷 */ public void preOrderCur(Node head){ if(head==null){ return; } System.out.println(head.data+" "); preOrder(head.left); preOrder(head.right); } public void preOrder(Node head){ if(head!=null){ Stackstack=new Stack (); stack.add(head); while(!stack.isEmpty()){ head=stack.pop(); System.out.println(head.data+" "); if(head.right!=null){ stack.push(head.right); } if(head.left!=null){ stack.push(head.left); } } } } public void inOrderCur(Node head){ if(head==null){ return ; } preOrder(head.left); System.out.println(head.data+" "); preOrder(head.right); } public void inOrder(Node head){ if(head!=null){ Stack stack=new Stack (); while(!stack.isEmpty()||head!=null){ if(head!=null){ stack.push(head); head=head.left; }else{ head=stack.pop(); System.out.println(head.data+" "); head=head.right; } } } } public void posOrderCur(Node head){ if(head==null){ return; } preOrder(head.left); preOrder(head.right); System.out.println(head.data+" "); } public void posOrder(Node head){ if(head!=null){ Stack stack=new Stack (); stack.push(head); Node c=null; while(!stack.isEmpty()){ c=stack.peek(); if(c.left!=null&&head!=c.left&&head!=c.right){ stack.push(c.left); }else if(c.right!=null &&head!=c.right){ stack.push(c.right); }else{ System.out.println(stack.pop().data+" "); head=c; } } } } public void levelOrder(Node head){ if(head==null){ return; } Queue queue=new LinkedList (); queue.offer(head); while(!queue.isEmpty()){ head=queue.poll(); System.out.println(head.data); if(head.left!=null){ queue.offer(head.left); } if(head.right!=null){ queue.offer(head.right); } } } /** * 序列化二叉樹 * 先序、層序序列化和反序列化 */ public String serialPre(Node head){ if(head==null){ return "#!"; } String str=head.data+"!"; str+=serialPre(head.left); str+=serialPre(head.right); return str; } /*先序反序列化*/ public Node recoByPre(String preStr){ String[] values=preStr.split("!"); Queue數(shù)據(jù)測試queue=new LinkedList (); for(int i=0;i!=values.length;i++){ queue.offer(values[i]); } return reconPreOrder(queue); } public Node reconPreOrder(Queue 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 String serialLevel(Node head){ if(head==null){ return "#!"; } String res=head.data+"!"; Queue queue=new LinkedList (); queue.offer(head); while(!queue.isEmpty()){ head=queue.poll(); if(head.left!=null){ res+=head.left.data+"!"; queue.offer(head.left); }else{ res+="#!"; } if(head.right!=null){ res+=head.right.data+"!"; queue.offer(head.right); }else{ res+="#"; } } return res; } /*層序反序列化*/ public Node reconLevel(String str){ String[] values=str.split("!"); int index=0; Node head=createNode(values[index++]); Queue queue=new LinkedList (); if(head!=null){ queue.offer(head); } Node node=null; while(!queue.isEmpty()){ node=queue.poll(); node.left=createNode(values[index++]); node.right=createNode(values[index++]); if(node.left!=null){ queue.offer(node.left); } if(node.right!=null){ queue.offer(node.right); } } return head; } public Node createNode(String val){ if(val.equals("#")){ return null; } return new Node(Integer.valueOf(val)); } } public class test { public static void main(String[] args) { BinaryTree binTree=new BinaryTree(); //建立一棵二叉樹 int[] data={25,15,10,5,36,65,52,45,42}; for(int i=0;i參考資料 《IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》左程云
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/65166.html
摘要:另外,由于篇幅有限,本篇的重點在于二叉樹的常見算法以及實現(xiàn)。常見的二叉樹實現(xiàn)代碼之前寫過相關(guān)的文章,是關(guān)于如何創(chuàng)建及遍歷二叉樹的,這里不再贅述。同時我們注意到,在二叉樹深度比較大的時候,我們光是比較左右是不夠的。 本篇為復(fù)習(xí)過程中遇到過的總結(jié),同時也給準備面試的同學(xué)一份參考。另外,由于篇幅有限,本篇的重點在于二叉樹的常見算法以及實現(xiàn)。 常見的二叉樹實現(xiàn)代碼 之前寫過相關(guān)的文章,是關(guān)于如...
摘要:什么是樹前面說到的幾種數(shù)據(jù)結(jié)構(gòu)都是線性的,例如鏈表棧隊列等,今天就來學(xué)習(xí)一種非線性的數(shù)據(jù)結(jié)構(gòu)樹。在上圖中的幾種二叉樹中,有兩個是比較特殊的,分別是滿二叉樹和完全二叉樹。除了使用數(shù)組存儲二叉樹外,最常用的便是使用鏈表法來儲存二叉樹了。 1. 什么是樹? 前面說到的幾種數(shù)據(jù)結(jié)構(gòu)都是線性的,例如鏈表、棧、隊列等,今天就來學(xué)習(xí)一種非線性的數(shù)據(jù)結(jié)構(gòu)——樹。先來看看幾種樹的結(jié)構(gòu): showImg(...
摘要:并且,我們的底層都是紅黑樹來實現(xiàn)的。紅黑樹是一種平衡二叉樹因此它沒有節(jié)點。 前言 聲明,本文用得是jdk1.8 前面已經(jīng)講了Collection的總覽和剖析List集合: Collection總覽 List集合就這么簡單【源碼剖析】 原本我是打算繼續(xù)將Collection下的Set集合的,結(jié)果看了源碼發(fā)現(xiàn):Set集合實際上就是HashMap來構(gòu)建的! showImg(https:/...
摘要:所以,如果中序遍歷二叉搜索樹,會得到一個有序的數(shù)據(jù),時間復(fù)雜度是,所以二叉搜索樹又叫做二叉排序樹。所以,我們需要一種方式來維持二叉樹的平衡,最好是將其維持為滿二叉樹或者完全二叉樹,這就是后面會說到的平衡二叉查找樹,常見的有樹,紅黑樹。 1. 概述 前面的文章說到了二叉樹,其實今天講的二叉搜索(查找)樹就是二叉樹最常用的一種形式,它支持高效的查找、插入、刪除操作,它的定義是這樣的:對于樹...
閱讀 1519·2021-11-23 09:51
閱讀 3639·2021-09-26 09:46
閱讀 2125·2021-09-22 10:02
閱讀 1818·2019-08-30 15:56
閱讀 3319·2019-08-30 12:51
閱讀 2224·2019-08-30 11:12
閱讀 2060·2019-08-29 13:23
閱讀 2323·2019-08-29 13:16