/

[Tree2java] Create on 2008-10-20 下午03:03:24

Copyright (c) 2008 by iTrusChina

/

/

@author WangXuanmin

@version 010

/

public class Tree2Bef {

private StringBuffer bef=new StringBuffer();

//传入中序遍历和后序遍历,返回前序遍历字串

public String getBef(String mid, String beh) {

//若节点存在则向bef中添加该节点,继续查询该节点的左子树和右子树

if (root(mid, beh) != -1) {

int rootindex=root(mid, beh);

char root=midcharAt(rootindex);

befappend(root);

Systemoutprintln(beftoString());

String mleft, mright;

mleft = midsubstring(0,rootindex);

mright = midsubstring(rootindex+1);

getBef(mleft,beh);

getBef(mright,beh);

}

//所有节点查询完毕,返回前序遍历值

return beftoString();

}

//从中序遍历中根据后序遍历查找节点索引值index

private int root(String mid, String beh) {

char[] midc = midtoCharArray();

char[] behc = behtoCharArray();

for (int i = behclength-1; i > -1; i--) {

for (int j = 0; j < midclength; j++) {

if (behc[i] == midc[j])

return j;

}

}

return -1;

}

public static void main(String[] args) {

Tree2Bef tree=new Tree2Bef();

String mid="84925163A7B";

String bef="894526AB731";

Systemoutprintln(treegetBef(mid,bef));

}

}

树结构如图:

1

|-------|

2 3

|---| |---|

4 5 6 7

|-| |-|

8 9 A B

/

二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能

够前序、中序、后序、按层遍历二叉树的方法以及一个返回遍历结果asString的

方法。

/

public class BitTree {

public static Node2 root;

public static String asString;

//事先存入的数组,符号#表示二叉树结束。

public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};

//用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。

static int index;

//构造函数

public BitTree() {

Systemoutprint("测试二叉树的顺序表示为：");

Systemoutprintln(treeLine);

thisindex = 0;

root = thissetup(root);

}

//创建二叉树的递归程序

private Node2 setup(Node2 current) {

if (index >= treeLinelength) return current;

if (treeLine[index] == '#') return current;

if (treeLine[index] == ' ') return current;

current = new Node2(treeLine[index]);

index = index 2 + 1;

currentleft = setup(currentleft);

index ++;

currentright = setup(currentright);

index = index / 2 - 1;

return current;

}

//二叉树是否为空。

public boolean isEmpty() {

if (root == null) return true;

return false;

}

//返回遍历二叉树所得到的字符串。

public String toString(int type) {

if (type == 0) {

asString = "前序遍历：\t";

thisfront(root);

}

if (type == 1) {

asString = "中序遍历：\t";

thismiddle(root);

}

if (type == 2) {

asString = "后序遍历：\t";

thisrear(root);

}

if (type == 3) {

asString = "按层遍历：\t";

thislevel(root);

}

return asString;

}

//前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树，

//出栈，访问其右子树，然后该次循环结束。

private void front(Node2 current) {

StackL stack = new StackL((Object)current);

do {

if (current == null) {

current = (Node2)stackpop();

current = currentright;

} else {

asString += currentch;

current = currentleft;

}

if (!(current == null)) stackpush((Object)current);

} while (!(stackisEmpty()));

}

//中序遍历二叉树

private void middle(Node2 current) {

if (current == null) return;

middle(currentleft);

asString += currentch;

middle(currentright);

}

//后序遍历二叉树的递归算法

private void rear(Node2 current) {

if (current == null) return;

rear(currentleft);

rear(currentright);

asString += currentch;

}

}

/

二叉树所使用的节点类。包括一个值域两个链域

/

public class Node2 {

char ch;

Node2 left;

Node2 right;

//构造函数

public Node2(char c) {

thisch = c;

thisleft = null;

thisright = null;

}

//设置节点的值

public void setChar(char c) {

thisch = c;

}

//返回节点的值

public char getChar() {

return ch;

}

//设置节点的左孩子

public void setLeft(Node2 left) {

thisleft = left;

}

//设置节点的右孩子

public void setRight (Node2 right) {

thisright = right;

}

//如果是叶节点返回true

public boolean isLeaf() {

if ((thisleft == null) && (thisright == null)) return true;

return false;

}

}

一个作业题，里面有你要的东西。

主函数自己写吧。当然其它地方也有要改的。

计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。

树是由一个或多个结点组成的有限集合，其中：

⒈必有一个特定的称为根(ROOT)的结点；

二叉树

⒉剩下的结点被分成n>=0个互不相交的集合T1、T2、Tn，而且， 这些集合的每一个又都是树。树T1、T2、Tn被称作根的子树(Subtree)。

树的递归定义如下：（1）至少有一个结点（称为根）（2）其它是互不相交的子树

1树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为2;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点。

2树的深度——组成该树各结点的最大层次。

3森林——指若干棵互不相交的树的集合，如上图，去掉根结点A，其原来的二棵子树T1、T2、T3的集合{T1,T2,T3}就为森林；

4有序树——指树中同层结点从左到右有次序排列，它们之间的次序不能互换，这样的树称为有序树，否则称为无序树。

树的表示

树的表示方法有许多，常用的方法是用括号：先将根结点放入一对圆括号中，然后把它的子树由左至右的顺序放入括号中，而对子树也采用同样的方法处理；同层子树与它的根结点用圆括号括起来，同层子树之间用逗号隔开，最后用闭括号括起来。如右图可写成如下形式：

二叉树

(a( b(d,e), c( f( ,g(h,i) ), )))

#include#includeinti=0;typedefstructtreeNODE{chardata;structtreeNODElchild,rchild,parent;}treenode,tree;///////////////////////////////////////////////////////////////////////////////////////二叉树的建立treecreat(treeroot){charch;ch=getchar();if(ch=='#')root=NULL;else{root=(treenode)malloc(sizeof(treenode));root->data=ch;root->lchild=creat(root->lchild);root->rchild=creat(root->rchild);}returnroot;}//////////////////////////////////////////////////////////////////////////////////////中序遍历voidtraverse(treeroot){if(root){traverse(root->lchild);printf("%c",root->data);traverse(root->rchild);}}//////////////////////////////////////////////////////////////////////////////////////先序遍历voidtraverse1(treeroot){if(root){printf("%c",root->data);traverse(root->lchild);traverse(root->rchild);}}/////////////////////////////////////////////////////////////////////////////////////后序遍历voidtraverse2(treeroot){if(root){traverse(root->lchild);traverse(root->rchild);printf("%c",root->data);}}/////////////////////////////////////////////////////////////////////////////////////////计算叶子数intleaf(treeroot){intnum1=0,num2=0;if(root==NULL)return0;if(root->lchild==NULL&&root->rchild==NULL)return1;else{num1++;leaf(root->lchild);num2++;leaf(root->rchild);returnnum1+num2;}}///////////////////////////////////////////////////////////////////////////////////////结点数intnode(treeroot){intnum1,num2;if(!root)return0;if(root->lchild==NULL&&root->rchild==NULL)return1;else{num1=node(root->lchild);num2=node(root->rchild);}returnnum1+num2+1;}////////////////////////////////////////////////////////////////////////////////////////复制二叉树treecopy(treeroot){treeroot1;//root1=(treenode)malloc(sizeof(treenode));if(!root)returnNULL;{root1=(treenode)malloc(sizeof(treenode));root1->data=root->data;root->lchild=root1->lchild=copy(root->lchild);root->rchild=root1->rchild=copy(root->rchild);returnroot1;}}////////////////////////////////////////////////////////左右子树交换voidchage(treep){treet;if(p==NULL)return;else{chage(p->lchild);chage(p->rchild);t=p->lchild;p->lchild=p->rchild;p->rchild=t;}}///////////////////////////voidmain(){treet=NULL,node1;printf("输入树的数据\n");t=creat(t);printf("中序遍历\n");traverse(t);printf("\n");printf("先序遍历\n");traverse1(t);printf("\n");printf("后序遍历\n");traverse2(t);printf("\n");printf("叶子数%d\n",leaf(t));printf("节点数%d\n",node(t));node1=copy(t);traverse(node1);printf("\n");chage(t);traverse(t);}

#include <stdioh>

typedef struct node

{

char data;

struct node lchild;

struct node rchild;

}BTNode;

BTNode PreCreate() //先序建立

{

char ch = getchar();

if (ch = '')

return NULL;

else

{

BTNode p = (BTNode )malloc(sizeof(BTNode));

p->data = ch;

p->lchild = PreCreate();

p->rchild = PreCreate();

return p;

}

}

int leafNode(BTNode t) //求叶子节点

{

if (t == NULL)

return 0;

else

{

int lleafCount = leafNode(t->lchild);

int rleafCount = leafNode(t->rchild);

if (!lleafCount && !rleafCount)

return 1;

else

return lleafCount + rleafCount;

}

}

void InOrderTraverse(BTNode t)

{

InOrderTraverse(t->lchild);

printf("%c ", t->data);

InOrderTraverse(t->rchild);

}

void PostOrderTraverse(BTNode t)

{

PostOrderTraverse(t->lchild);

PostOrderTraverse(t->rchild);

printf("%c ", t->data);

}

我有很多个(假设10万个)数据要保存起来，以后还需要从保存的这些数据中检索是否存在某

个数据，（我想说出二叉树的好处，该怎么说呢？那就是说别人的缺点），假如存在数组中，

那么，碰巧要找的数字位于99999那个地方，那查找的速度将很慢，因为要从第1个依次往

后取，取出来后进行比较。平衡二叉树（构建平衡二叉树需要先排序，我们这里就不作考虑

了）可以很好地解决这个问题，但二叉树的遍历（前序，中序，后序）效率要比数组低很多，

public class Node {

public int value;

public Node left;

public Node right;

public void store(intvalue)

rightvalue=value;

}

else

{

rightstore(value);

}

}

}

public boolean find(intvalue)

{

Systemoutprintln("happen" +thisvalue);

if(value ==thisvalue)

{

return true;

}

else if(value>thisvalue)

{

if(right ==null)returnfalse;

return rightfind(value);

}else

{

if(left ==null)returnfalse;

return leftfind(value);

}

}

public void preList()

{

Systemoutprint(thisvalue+ ",");

if(left!=null)leftpreList();

if(right!=null) rightpreList();

}

public void middleList()

{

if(left!=null)leftpreList();

Systemoutprint(thisvalue+ ",");

if(right!=null)rightpreList();

}

public void afterList()

{

if(left!=null)leftpreList();

if(right!=null)rightpreList();

Systemoutprint(thisvalue+ ",");

}

public static voidmain(String [] args)

{

int [] data =new int[20];

for(inti=0;i<datalength;i++)

{

data[i] = (int)(Mathrandom()100)+ 1;

Systemoutprint(data[i] +",");

}

Systemoutprintln();

Node root = new Node();

rootvalue = data[0];

for(inti=1;i<datalength;i++)

{

rootstore(data[i]);

}

rootfind(data[19]);

rootpreList();

Systemoutprintln();

rootmiddleList();

Systemoutprintln();

rootafterList();

}

}