怎樣用Java來(lái)體現(xiàn)二叉樹(shù)（順便加上注釋）

二叉樹(shù)，和數(shù)據(jù)庫(kù)的B樹(shù)操作流程是一樣的，例如：有如下字段

從策劃到設(shè)計(jì)制作，每一步都追求做到細(xì)膩，制作可持續(xù)發(fā)展的企業(yè)網(wǎng)站。為客戶提供網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)、網(wǎng)站策劃、網(wǎng)頁(yè)設(shè)計(jì)、申請(qǐng)域名、網(wǎng)頁(yè)空間、網(wǎng)絡(luò)營(yíng)銷(xiāo)、VI設(shè)計(jì)、 網(wǎng)站改版、漏洞修補(bǔ)等服務(wù)。為客戶提供更好的一站式互聯(lián)網(wǎng)解決方案,以客戶的口碑塑造優(yōu)易品牌,攜手廣大客戶,共同發(fā)展進(jìn)步。

F,C,B,H,K,I；

如果要形成二叉樹(shù)的話，則，首先取第一個(gè)數(shù)據(jù)作為根節(jié)點(diǎn)，所以，現(xiàn)在是 F ，如果字段比根節(jié)點(diǎn)小，則保存在左子樹(shù)，如果比根節(jié)點(diǎn)大或者等于根節(jié)點(diǎn)則保存在右子樹(shù)，最后按左---根-----右輸出所以數(shù)據(jù)。

所以，實(shí)現(xiàn)的關(guān)鍵就是在于保存的數(shù)據(jù)上是否存在大小比較功能，而String類(lèi)中compareTo()有這個(gè)能力,節(jié)點(diǎn)類(lèi)要保存兩類(lèi)數(shù)據(jù)，左節(jié)點(diǎn)，右節(jié)點(diǎn)

class Node

{

private String data;

private Node left;

private Node right;

public Node (String data){

this.data = data;

}

public void setLeft(Node left) {

this.left = left;

}

public void setRight(Node right){

this.right = right;

}

public String getDate() {

return this.data;

}

public Node getLeft(){

return this.left;

}

public Node getRight(){

return this.right;

}

public void addNode(Node newNode){

if(this.data點(diǎn)抗 pareTo(newNode.data)=0) {

if(this.left == null){

this.left = newNode;

}else {

this.left.addNode(newNode);

}

}else {

if(this.right == null) {

this.right = newNode;

} else {

this.right.addNode(newNode);

}

}

}

public void printNode(){

if(this.left!= null){

this.left.printNode();

}

System.out.println(this.data);

if(this.right != null){

this.right.printNode();

}

}

}

class BinaryTree

{

private Node root = null;

public void add(String data) {

Node newNode = new Node(data);

if(this.root == null) {

this.root = newNode;

}else{

this.root.addNode(newNode);

}

}

public void print() {

this.root.printNode();

}

}

public class Hello

{

public static void main (String args[]) {

BinaryTree link = new BinaryTree();

link.add("F");

link.add("C");

link.add("B");

link.add("H");

link.add("K");

link.add("I");

link.print();

}

}

你一看就英文就知道什么意思了，應(yīng)該可以理解了

這個(gè)二叉樹(shù)捉摸不透就別琢磨了，開(kāi)放中一般用不上

}

Java數(shù)據(jù)結(jié)構(gòu)二叉樹(shù)深度遞歸調(diào)用算法求內(nèi)部算法過(guò)程詳解

二叉樹(shù)

1

2??? 3

4 ?5 6 ?7

這個(gè)二叉樹(shù)的深度是3，樹(shù)的深度是最大結(jié)點(diǎn)所在的層，這里是3.

應(yīng)該計(jì)算所有結(jié)點(diǎn)層數(shù)，選擇最大的那個(gè)。

根據(jù)上面的二叉樹(shù)代碼，遞歸過(guò)程是：

f(1)=f(2)+1 f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)計(jì)算類(lèi)似上面，要計(jì)算左右結(jié)點(diǎn)，然后取大者

所以計(jì)算順序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然后計(jì)算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 計(jì)算完畢，計(jì)算f(1.right) f(3) 跟計(jì)算f(2)的過(guò)程一樣。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleftdepright){

return?depleft+1;

}else{

return?depright+1;

}

只有l(wèi)eft大于right的時(shí)候采取left +1，相等是取right

用java怎么構(gòu)造一個(gè)二叉樹(shù)？

二叉樹(shù)的相關(guān)操作，包括創(chuàng)建，中序、先序、后序（遞歸和非遞歸），其中重點(diǎn)的是java在先序創(chuàng)建二叉樹(shù)和后序非遞歸遍歷的的實(shí)現(xiàn)。

package com.algorithm.tree;

import java.io.File;

import java.io.FileNotFoundException;

import java.util.Queue;

import java.util.Scanner;

import java.util.Stack;

import java.util.concurrent.LinkedBlockingQueue;

public class Tree {

private Node root;

public Tree() {

}

public Tree(Node root) {

this.root = root;

}

//創(chuàng)建二叉樹(shù)

public void buildTree() {

Scanner scn = null;

try {

scn = new Scanner(new File("input.txt"));

} catch (FileNotFoundException e) {

// TODO Auto-generated catch block

e.printStackTrace();

}

root = createTree(root,scn);

}

//先序遍歷創(chuàng)建二叉樹(shù)

private Node createTree(Node node,Scanner scn) {

String temp = scn.next();

if (temp.trim().equals("#")) {

return null;

} else {

node = new Node((T)temp);

node.setLeft(createTree(node.getLeft(), scn));

node.setRight(createTree(node.getRight(), scn));

return node;

}

}

//中序遍歷(遞歸)

public void inOrderTraverse() {

inOrderTraverse(root);

}

public void inOrderTraverse(Node node) {

if (node != null) {

inOrderTraverse(node.getLeft());

System.out.println(node.getValue());

inOrderTraverse(node.getRight());

}

}

//中序遍歷(非遞歸)

public void nrInOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

System.out.println(node.getValue());

node = node.getRight();

}

}

//先序遍歷(遞歸)

public void preOrderTraverse() {

preOrderTraverse(root);

}

public void preOrderTraverse(Node node) {

if (node != null) {

System.out.println(node.getValue());

preOrderTraverse(node.getLeft());

preOrderTraverse(node.getRight());

}

}

//先序遍歷（非遞歸）

public void nrPreOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

while (node != null || !stack.isEmpty()) {

while (node != null) {

System.out.println(node.getValue());

stack.push(node);

node = node.getLeft();

}

node = stack.pop();

node = node.getRight();

}

}

//后序遍歷(遞歸)

public void postOrderTraverse() {

postOrderTraverse(root);

}

public void postOrderTraverse(Node node) {

if (node != null) {

postOrderTraverse(node.getLeft());

postOrderTraverse(node.getRight());

System.out.println(node.getValue());

}

}

//后續(xù)遍歷(非遞歸)

public void nrPostOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

Node preNode = null;//表示最近一次訪問(wèn)的節(jié)點(diǎn)

while (node != null || !stack.isEmpty()) {

while (node != null) {

stack.push(node);

node = node.getLeft();

}

node = stack.peek();

if (node.getRight() == null || node.getRight() == preNode) {

System.out.println(node.getValue());

node = stack.pop();

preNode = node;

node = null;

} else {

node = node.getRight();

}

}

}

//按層次遍歷

public void levelTraverse() {

levelTraverse(root);

}

public void levelTraverse(Node node) {

QueueNode queue = new LinkedBlockingQueueNode();

queue.add(node);

while (!queue.isEmpty()) {

Node temp = queue.poll();

if (temp != null) {

System.out.println(temp.getValue());

queue.add(temp.getLeft());

queue.add(temp.getRight());

}

}

}

}

//樹(shù)的節(jié)點(diǎn)

class Node {

private Node left;

private Node right;

private T value;

public Node() {

}

public Node(Node left,Node right,T value) {

this.left = left;

this.right = right;

this.value = value;

}

public Node(T value) {

this(null,null,value);

}

public Node getLeft() {

return left;

}

public void setLeft(Node left) {

this.left = left;

}

public Node getRight() {

return right;

}

public void setRight(Node right) {

this.right = right;

}

public T getValue() {

return value;

}

public void setValue(T value) {

this.value = value;

}

}

測(cè)試代碼：

package com.algorithm.tree;

public class TreeTest {

/**

* @param args

*/

public static void main(String[] args) {

Tree tree = new Tree();

tree.buildTree();

System.out.println("中序遍歷");

tree.inOrderTraverse();

tree.nrInOrderTraverse();

System.out.println("后續(xù)遍歷");

//tree.nrPostOrderTraverse();

tree.postOrderTraverse();

tree.nrPostOrderTraverse();

System.out.println("先序遍歷");

tree.preOrderTraverse();

tree.nrPreOrderTraverse();

//

}

}