二叉樹
創(chuàng)新互聯(lián)建站網(wǎng)站建設(shè)公司,提供網(wǎng)站設(shè)計(jì)、網(wǎng)站建設(shè),網(wǎng)頁設(shè)計(jì),建網(wǎng)站,PHP網(wǎng)站建設(shè)等專業(yè)做網(wǎng)站服務(wù);可快速的進(jìn)行網(wǎng)站開發(fā)網(wǎng)頁制作和功能擴(kuò)展;專業(yè)做搜索引擎喜愛的網(wǎng)站,是專業(yè)的做網(wǎng)站團(tuán)隊(duì),希望更多企業(yè)前來合作!
1
2??? 3
4 ?5 6 ?7
這個(gè)二叉樹的深度是3,樹的深度是最大結(jié)點(diǎn)所在的層,這里是3.
應(yīng)該計(jì)算所有結(jié)點(diǎn)層數(shù),選擇最大的那個(gè)。
根據(jù)上面的二叉樹代碼,遞歸過程是:
f(1)=f(2)+1 f(3) +1 ? f(2) + 1 : f(3) +1
f(2) 跟f(3)計(jì)算類似上面,要計(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)的過程一樣。
得到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
下面這個(gè)算法能幫你:
/*二叉樹的建立與遍歷
以二叉鏈表作為存儲(chǔ)結(jié)構(gòu),定義二叉樹類型 bitree;
實(shí)現(xiàn)二叉樹的以下運(yùn)算
建立 create( ) 輸入二叉樹的結(jié)點(diǎn)元素,建立二叉鏈表。
選擇一種遍歷方式(先序、中序、后序)遍歷這棵二叉樹。 */
#include stdio.h
struct node
{
char data;
struct node *lchild,*rchild;
};
/****************************二叉樹的創(chuàng)建*****************************/
struct node *creat_bintree(struct node *t)
{
char ch;
printf("\n 按照先序序列輸入二叉樹的每個(gè)值,空格代表空樹:");
ch=getchar();
getchar();
if( ch==' ')
t=NULL;
else
{
t = (struct node *)malloc(sizeof(struct node));
t-data=ch;
t-lchild = creat_bintree( t-lchild );
t-rchild = creat_bintree( t-rchild );
}
return(t);
}
/****************************二叉樹的先序遍歷*****************************/
void preorder(struct node *t )
{
if (t)
{
putchar(t-data);
preorder(t-lchild);
preorder(t-rchild);
}
}
/****************************二叉樹的中序遍歷*****************************/
void inorder(struct node *t )
{
if (t)
{
inorder(t-lchild);
putchar(t-data);
inorder(t-rchild);
}
}
/****************************二叉樹的后序遍歷*****************************/
void postorder(struct node *t )
{
if (t)
{
postorder(t-lchild);
postorder(t-rchild);
putchar(t-data);
}
}
void main()
{
struct node *t;
t=creat_bintree(t);
if (t)
{
printf("\n after preorder:\n");
preorder(t);
printf("\n after inorder:\n");
inorder(t);
printf("\n after postorder:\n");
postorder(t);
}
}
二叉樹的相關(guān)操作,包括創(chuàng)建,中序、先序、后序(遞歸和非遞歸),其中重點(diǎn)的是java在先序創(chuàng)建二叉樹和后序非遞歸遍歷的的實(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)建二叉樹
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)建二叉樹
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;//表示最近一次訪問的節(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());
}
}
}
}
//樹的節(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();
//
}
}
網(wǎng)站名稱:java二叉樹形結(jié)構(gòu)代碼 java二叉樹數(shù)據(jù)結(jié)構(gòu)
文章轉(zhuǎn)載:http://muchs.cn/article10/doccido.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián),為您提供靜態(tài)網(wǎng)站、搜索引擎優(yōu)化、營(yíng)銷型網(wǎng)站建設(shè)、品牌網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)、網(wǎng)站收錄
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主,如果涉及侵權(quán)請(qǐng)盡快告知,我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如需處理請(qǐng)聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載,或轉(zhuǎn)載時(shí)需注明來源: 創(chuàng)新互聯(lián)