摘要:二叉樹是數據結構中很重要的結構類型,學習數據結構也是深入學習編程的必由之路,這里我們簡單介紹下我對于二叉樹的理解,水平有限,如有錯誤還請不吝賜教。
二叉樹是數據結構中很重要的結構類型,學習數據結構也是深入學習編程的必由之路,這里我們簡單介紹下我對于二叉樹的理解,水平有限,如有錯誤還請不吝賜教。
首先照例定義一個二叉樹的節點類class Node { private int value;//二叉樹的值 private Node leftChild;//左孩子節點 private Node rightChild;//右孩子節點 public Node(int value, Node leftChild, Node rightChild) { this.value = value; this.leftChild = leftChild; this.rightChild = rightChild; } }插入節點
本次用到的二叉樹是順序二叉樹,即判斷當前插入的節點值與二叉樹中父節點比較,如果value值大于父節點,插入父節點的右子樹種,反之,插入左子樹種,以此類推,直到找到相應的字節點插入。
public void insert(int value) { if (parent == null) {//父節點為空判斷 Node node = new Node(value, null, null); parent = node; length++; } else { currentPoint = parent;//將當前結點指向父節點 while(true){//循環遍歷節點,查找適合的插入位置 if(currentPoint.value>value){ if(currentPoint.leftChild!=null){ currentPoint=currentPoint.leftChild; }else{ currentPoint.leftChild=new Node(value,null,null); length++; break; } }else{ if(currentPoint.rightChild!=null){ currentPoint=currentPoint.rightChild; }else{ currentPoint.rightChild=new Node(value,null,null); length++; break; } } } } }中序遍歷二叉樹節點
public String visit(Node node) { sb.append(node.value+"("); if (node.leftChild != null) visit(node.leftChild);//遞歸遍歷左子樹 if (node.rightChild != null) visit(node.rightChild);//遞歸遍歷右子樹 sb.append(")"); return sb.toString(); }整體代碼
public class BinaryTree { private Node parent; private Node currentPoint; private StringBuffer sb; private int length=0; class Node { private int value; private Node leftChild; private Node rightChild; public Node(int value, Node leftChild, Node rightChild) { this.value = value; this.leftChild = leftChild; this.rightChild = rightChild; } } public Node getParent(){ return parent; } public BinaryTree() { sb=new StringBuffer(); } public void insert(int value) { if (parent == null) { Node node = new Node(value, null, null); parent = node; length++; } else { currentPoint = parent; while(true){ if(currentPoint.value>value){ if(currentPoint.leftChild!=null){ currentPoint=currentPoint.leftChild; }else{ currentPoint.leftChild=new Node(value,null,null); length++; break; } }else{ if(currentPoint.rightChild!=null){ currentPoint=currentPoint.rightChild; }else{ currentPoint.rightChild=new Node(value,null,null); length++; break; } } } } } public String visit(Node node) { sb.append(node.value+"("); if (node.leftChild != null) visit(node.leftChild); if (node.rightChild != null) visit(node.rightChild); sb.append(")"); return sb.toString(); } public int getLength(){ return length; } @Override public String toString() { return visit(parent); } }main函數測試
public static void main(String[] args) { BinaryTree bt = new BinaryTree(); bt.insert(1); bt.insert(3); bt.insert(2); bt.insert(5); bt.insert(6); bt.insert(7); bt.insert(8); bt.insert(9); bt.insert(10); bt.insert(11); bt.insert(12); bt.insert(13); bt.insert(14); bt.insert(15); System.out.println(bt.getLength()); System.out.println(bt.toString()); }結果輸出
其中括號表示層級包含關系,
我的文章列表
Email:sxh13208803520@gmail.com
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/66960.html
摘要:數據結構之二叉樹本文講解二叉樹的基本操作查找節點計算樹的高度清空樹遞歸遍歷先序遍歷中序遍歷后序遍歷按層遍歷來看一下樹的結構首先,為了方便后面看到效果,先手動初始化一個有個節點的二叉樹查找節點查找節點遞歸左子樹遞歸右子樹計算樹的深度計算樹的深 數據結構之二叉樹 本文講解二叉樹的基本操作: 查找節點 計算樹的高度 清空樹 遞歸遍歷:先序遍歷、中序遍歷、后序遍歷 按層遍歷 來看一下樹的結...
摘要:例如輸入前序遍歷序列和中序遍歷序列,則重建二叉樹并返回。操作給定的二叉樹,將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目,就是下面的這道,之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。 開篇 以下內容可能偏應試但很好理解,所以大家一定要堅持看下去,因為我們變強的過程注定孤獨的,堅持下來就會看到明天的太陽。 回顧 showImg(https://user-...
摘要:回來更新一波,最近刷劍指,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用,我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識,發現也用不上,我想說的是,讀一本書體現不了這本書 回來更新一波,最近刷《劍指offer》,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊~ /** * PHP二叉樹算法 * Create...
摘要:回來更新一波,最近刷劍指,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用,我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識,發現也用不上,我想說的是,讀一本書體現不了這本書 回來更新一波,最近刷《劍指offer》,才又發現樹真是一個大頭,二叉樹的題目和變化運用好多啊~ /** * PHP二叉樹算法 * Create...
閱讀 2234·2021-11-17 09:33
閱讀 2774·2021-11-12 10:36
閱讀 3396·2021-09-27 13:47
閱讀 884·2021-09-22 15:10
閱讀 3485·2021-09-09 11:51
閱讀 1392·2021-08-25 09:38
閱讀 2757·2019-08-30 15:55
閱讀 2608·2019-08-30 15:53