二叉樹的遍歷的完整代碼是什么

二叉樹遍歷代碼

成都創新互聯公司是專業的榆社網站建設公司，榆社接單;提供網站制作、做網站,網頁設計,網站設計,建網站,PHP網站建設等專業做網站服務;采用PHP框架,可快速的進行榆社網站開發網頁制作和功能擴展;專業做搜索引擎喜愛的網站,專業的做網站團隊,希望更多企業前來合作!

#include"iostream.h"

#include"stdlib.h"

#include"stdio.h"

#includestack

using namespace std;

#define NULL 0

#define OK 1

#define OVERFLOW -1

typedef int Status;

typedef struct node

{

char data;

struct node *lchild;

struct node *rchild;

}*bitree;

int k=0;

int depth(bitree T)//樹的高度

{

if(!T)return 0;

else

{

int m=depth(T-lchild); int n=depth(T-rchild); return (mn?m:n)+1;

}

}

//先序，中序 建樹

struct node *create(char *pre,char *ord,int n) {

struct node * T;

int m;

T=NULL;

if(n=0)

{

return NULL;

}

else

{

m=0;

T=new(struct node);

T-data=*pre;

T-lchild=T-rchild=NULL; while(ord[m]!=*pre)

m++;

T-lchild=create(pre+1,ord,m);

T-rchild=create (pre+m+1,ord+m+1,n-m-1); return T;

}

}

//中序遞歸遍歷

void inorder(struct node *T)

{

if(!T)

return;

else

{

inorder(T-lchild );

coutT-data;

inorder(T-rchild );

}

}

void inpre(struct node *T)

{

if(!T)

return;

else

{

coutT-data;

inpre(T-lchild );

inpre(T-rchild );

}

}

void postorder(struct node *T)

{

if(!T)

return;

else

{

postorder (T-lchild );

postorder (T-rchild );

coutT-data;

}

}

//先序非遞歸遍歷

void inpre1(struct node *T)

第2/4頁

{

struct node *p;

struct node *stack[20];

int top=0;

p=T;

cout"非遞歸先序為:"endl;

while(p||top!=0)

{

while (p)

{

stack[top++]=p;

coutp-data;

p=p-lchild;

}

p=stack[--top];

p=p-rchild ;

}

}

//中序非遞歸遍歷

void inorder1(struct node *T)

{

struct node *p;

struct node *stack[20];

int top=0;

p=T;

cout"非遞歸中序為:"endl;

while(p||top!=0)

{

while (p)

{

stack[top++]=p;

p=p-lchild ;

}

p=stack[--top];

coutp-data;

p=p-rchild ;

}

}

//主函數

int main()

{

bitree T;

char pre[30],ord[30];

第3/4頁

int n,m;

cout"請輸入先序為-+a*b%cd/ef的二叉樹:"endl; gets(pre);

cout"請輸入中序為a+b*c%d-e/f的二叉樹:"endl; gets(ord);

n=strlen(pre);

T=create(pre,ord,n);

cout "后序遍歷為:"endl;

postorder (T);

coutendl;

inpre1(T);

coutendl;

inorder1(T);

coutendl;

m=depth(T);

cout"二叉樹高度為："mendl;

return 0;

}

java 由字符串構成的二叉樹

java構造二叉樹，可以通過鏈表來構造，如下代碼：

public class BinTree {public final static int MAX=40;BinTree []elements = new BinTree[MAX];//層次遍歷時保存各個節點 int front;//層次遍歷時隊首 int rear;//層次遍歷時隊尾private Object data; //數據元數private BinTree left,right; //指向左,右孩子結點的鏈public BinTree(){}public BinTree(Object data){ //構造有值結點 this.data = data; left = right = null;}public BinTree(Object data,BinTree left,BinTree right){ //構造有值結點 this.data = data; this.left = left; this.right = right;}public String toString(){ return data.toString();}//前序遍歷二叉樹public static void preOrder(BinTree parent){ if(parent == null) return; System.out.print(parent.data+" "); preOrder(parent.left); preOrder(parent.right);}//中序遍歷二叉樹public void inOrder(BinTree parent){ if(parent == null) return; inOrder(parent.left); System.out.print(parent.data+" "); inOrder(parent.right);}//后序遍歷二叉樹public void postOrder(BinTree parent){ if(parent == null) return; postOrder(parent.left); postOrder(parent.right); System.out.print(parent.data+" ");}// 層次遍歷二叉樹 public void LayerOrder(BinTree parent){ elements[0]=parent; front=0;rear=1; while(frontrear) { try { if(elements[front].data!=null) { System.out.print(elements[front].data + " "); if(elements[front].left!=null) elements[rear++]=elements[front].left; if(elements[front].right!=null) elements[rear++]=elements[front].right; front++; } }catch(Exception e){break;} }}//返回樹的葉節點個數public int leaves(){ if(this == null) return 0; if(left == nullright == null) return 1; return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());}//結果返回樹的高度public int height(){ int heightOfTree; if(this == null) return -1; int leftHeight = (left == null ? 0 : left.height()); int rightHeight = (right == null ? 0 : right.height()); heightOfTree = leftHeightrightHeight?rightHeight:leftHeight; return 1 + heightOfTree;}//如果對象不在樹中,結果返回-1;否則結果返回該對象在樹中所處的層次,規定根節點為第一層public int level(Object object){ int levelInTree; if(this == null) return -1; if(object == data) return 1;//規定根節點為第一層 int leftLevel = (left == null?-1:left.level(object)); int rightLevel = (right == null?-1:right.level(object)); if(leftLevel0rightLevel0) return -1; levelInTree = leftLevelrightLevel?rightLevel:leftLevel; return 1+levelInTree; }//將樹中的每個節點的孩子對換位置public void reflect(){ if(this == null) return; if(left != null) left.reflect(); if(right != null) right.reflect(); BinTree temp = left; left = right; right = temp;}// 將樹中的所有節點移走,并輸出移走的節點public void defoliate(){ if(this == null) return; //若本節點是葉節點，則將其移走 if(left==nullright == null) { System.out.print(this + " "); data = null; return; } //移走左子樹若其存在 if(left!=null){ left.defoliate(); left = null; } //移走本節點，放在中間表示中跟移走... String innerNode += this + " "; data = null; //移走右子樹若其存在 if(right!=null){ right.defoliate(); right = null; }} /*** @param args*/public static void main(String[] args) { // TODO Auto-generated method stub BinTree e = new BinTree("E"); BinTree g = new BinTree("G"); BinTree h = new BinTree("H"); BinTree i = new BinTree("I"); BinTree d = new BinTree("D",null,g); BinTree f = new BinTree("F",h,i); BinTree b = new BinTree("B",d,e); BinTree c = new BinTree("C",f,null); BinTree tree = new BinTree("A",b,c); System.out.println("前序遍歷二叉樹結果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍歷二叉樹結果: "); tree.inOrder(tree); System.out.println(); System.out.println("后序遍歷二叉樹結果: "); tree.postOrder(tree); System.out.println(); System.out.println("層次遍歷二叉樹結果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的層次: "+tree.level("F")); System.out.println("這棵二叉樹的高度: "+tree.height()); System.out.println("--------------------------------------"); tree.reflect(); System.out.println("交換每個節點的孩子節點后......"); System.out.println("前序遍歷二叉樹結果: "); tree.preOrder(tree); System.out.println(); System.out.println("中序遍歷二叉樹結果: "); tree.inOrder(tree); System.out.println(); System.out.println("后序遍歷二叉樹結果: "); tree.postOrder(tree); System.out.println(); System.out.println("層次遍歷二叉樹結果: "); tree.LayerOrder(tree); System.out.println(); System.out.println("F所在的層次: "+tree.level("F")); System.out.println("這棵二叉樹的高度: "+tree.height());

用java怎么構造一個二叉樹？

二叉樹的相關操作，包括創建，中序、先序、后序（遞歸和非遞歸），其中重點的是java在先序創建二叉樹和后序非遞歸遍歷的的實現。

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;

}

//創建二叉樹

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);

}

//先序遍歷創建二叉樹

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());

}

}

//后續遍歷(非遞歸)

public void nrPostOrderTraverse() {

StackNode stack = new StackNode();

Node node = root;

Node preNode = null;//表示最近一次訪問的節點

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());

}

}

}

}

//樹的節點

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;

}

}

測試代碼：

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("后續遍歷");

//tree.nrPostOrderTraverse();

tree.postOrderTraverse();

tree.nrPostOrderTraverse();

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

tree.preOrderTraverse();

tree.nrPreOrderTraverse();

//

}

}

新聞名稱：java中二叉樹全代碼 java二叉樹有什么作用
網站網址：http://vcdvsql.cn/article30/ddegoso.html

成都網站建設公司_創新互聯，為您提供App開發、網站設計公司、做網站、虛擬主機、關鍵詞優化、靜態網站

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯