數據結構之二叉樹

lansheng228 發布于2019-08-15 15:24 / 651人閱讀

摘要：數據結構之二叉樹本文講解二叉樹的基本操作查找節點計算樹的高度清空樹遞歸遍歷先序遍歷中序遍歷后序遍歷按層遍歷來看一下樹的結構首先，為了方便后面看到效果，先手動初始化一個有個節點的二叉樹查找節點查找節點遞歸左子樹遞歸右子樹計算樹的深度計算樹的深

數據結構之二叉樹

本文講解二叉樹的基本操作：

查找節點

計算樹的高度

清空樹

遞歸遍歷：先序遍歷、中序遍歷、后序遍歷

按層遍歷

來看一下樹的結構：

class TreeNode {
    String value;
    TreeNode left;
    TreeNode right;
    public TreeNode() {
        
    }
    public TreeNode(String value) {
        this.value = value;
    }
}

首先，為了方便后面看到效果，先手動初始化一個有4個節點的二叉樹：

Tree tree = new Tree();
TreeNode root = new TreeNode("root");
TreeNode node1 = new TreeNode("ndoe1");
TreeNode node2 = new TreeNode("ndoe2");
TreeNode node3 = new TreeNode("ndoe3");
root.left = node1;
root.right = node2;
node1.left = node3;

查找節點

//查找節點
public TreeNode findNode(TreeNode treeNode, String value) {
  if(null == treeNode)
    return null;

  if(treeNode.value.equals(value))
    return treeNode;

  TreeNode leftNode = findNode(treeNode.left, value);//遞歸左子樹
  TreeNode rightNode = findNode(treeNode.right, value);//遞歸右子樹
  if(leftNode.value.equals(value))
    return leftNode;
  if(rightNode.value.equals(value))
    return rightNode;

  return null;
}

計算樹的深度

//計算樹的深度
//遞歸方法
public int deepth(TreeNode treeNode) {
  if(treeNode == null)
    return 0;
  int left = deepth(treeNode.left);
  int right = deepth(treeNode.right);
  return left > right? left + 1: right + 1;
}

清空樹

//清空二叉樹
public void clearTreeNode(TreeNode treeNode) {
  if(null != treeNode) {
    clearTreeNode(treeNode.left);
    clearTreeNode(treeNode.right);
    treeNode = null;
  }
}

遞歸遍歷

//遍歷1 先序遍歷
public void showDLR(TreeNode treeNode) {
  if(null != treeNode) {
    showData(treeNode);
    showDLR(treeNode.left);
    showDLR(treeNode.right);
  }
}
//遍歷2 中序遍歷
public void showLDR(TreeNode treeNode) {
  if(null != treeNode) {
    showLDR(treeNode.left);
    showData(treeNode);
    showLDR(treeNode.right);
  }
}
//遍歷3 后序遍歷
public void showLRD(TreeNode treeNode) {
  if(null != treeNode) {
    showLRD(treeNode.left);
    showLRD(treeNode.right);
    showData(treeNode);
  }
}

按層遍歷

//遍歷4 按層遍歷 借助隊列 先進先出
public void showByLevel(TreeNode treeNode) {
  if(null == treeNode)
    return;

  LinkedList list = new LinkedList<>();
  TreeNode current;
  list.offer(treeNode);//將根節點入隊

  while(!list.isEmpty()) {
    current = list.poll();//隊首出隊
    showData(current);//打印節點
    if(null != current.left) {
      list.offer(current.left);
    }
    if(null != current.right) {
      list.offer(current.right);
    }
  }
}

運行結果：

樹的深度是：3
先序遍歷：
root-->ndoe1-->ndoe3-->ndoe2-->
中序遍歷：
ndoe3-->ndoe1-->root-->ndoe2-->
后序遍歷：
ndoe3-->ndoe1-->ndoe2-->root-->
按層遍歷
root-->ndoe1-->ndoe2-->ndoe3-->

云服務器 GPU云服務器二叉樹的存儲結構 c語言二叉樹輸入數據二叉樹 python二叉樹

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/69041.html

數據結構之二叉樹（java版）

摘要：二叉樹是數據結構中很重要的結構類型，學習數據結構也是深入學習編程的必由之路，這里我們簡單介紹下我對于二叉樹的理解，水平有限，如有錯誤還請不吝賜教。二叉樹是數據結構中很重要的結構類型，學習數據結構也是深入學習編程的必由之路，這里我們簡單介紹下我對于二叉樹的理解，水平有限，如有錯誤還請不吝賜教。首先照例定義一個二叉樹的節點類 class Node { private int ...

JayChen 2019-08-14 18:02 評論0 收藏0
PHPer面試必看：分門別類帶你擼《劍指Offer》之二叉樹

摘要：例如輸入前序遍歷序列和中序遍歷序列，則重建二叉樹并返回。操作給定的二叉樹，將其變換為源二叉樹的鏡像。劍指中還有一道類似的變種題目，就是下面的這道，之字形遍歷二叉樹。最后下面的兩道題目分別運用了二叉樹先序中序遍歷算法。開篇以下內容可能偏應試但很好理解，所以大家一定要堅持看下去，因為我們變強的過程注定孤獨的，堅持下來就會看到明天的太陽。回顧 showImg(https://user-...

li21 2019-07-01 10:26 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章五）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

developerworks 2019-06-27 16:27 評論0 收藏0
利用PHP實現常用的數據結構之二叉樹（小白系列文章六）

摘要：回來更新一波，最近刷劍指，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊二叉樹算法引子很多人說二叉樹沒什么卵用，我覺得是他的工資和公司讓他跨不過這個坎還有很多人學了一些樹的知識，發現也用不上，我想說的是，讀一本書體現不了這本書回來更新一波，最近刷《劍指offer》，才又發現樹真是一個大頭，二叉樹的題目和變化運用好多啊～ /** * PHP二叉樹算法 * Create...

Cympros 2019-06-28 13:56 評論0 收藏0