java构建二叉树代码 java实现二叉树的构建

java如何创建一颗二叉树

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

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

树是由一个或多个结点组成的有限集合，其中java构建二叉树代码：

⒈必有一个特定的称为根(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) ), )))

相关问答

Q1: 数据结构-二叉树的创建？

如果要在内存中建立一个如下左图这样java构建二叉树代码的树java构建二叉树代码，wield能让每个结点确认是否有左右孩子，我们对它进行扩展，变成如下右图的样子，也就是将二叉树中的每个结点的空指针引出一个虚结点，其值为一个特定值，比如”#”，称之为扩展二叉树。扩展二叉树就可以做到一个遍历序列确定一棵二叉树java构建二叉树代码了。如前序遍历序列为AB#D##C##。

有了这样的准备，就可以看看如何生成一棵二叉树了。假设二叉树的结点均为一个字符，把刚才前序遍历序列AB#D##C##用键盘挨个输入，实现的算法如下所示。

二叉树建立实现代码一，如下所示。

//创建树

//按先后次序输入二叉树中结点的值(一个字符),#表示空树

//构造二叉链表表示的二叉树

BiTree CreateTree(BiTree t)

{

    char ch;

    scanf("%c", ch);

 

    if(ch == '#')

    {

        t = NULL;

    }

    else

    {

        t = (BitNode *)malloc(sizeof(BitNode));

        if(t == NULL)

        {

            fprintf(stderr, "malloc() error in CreateTree.\n");

            return;

        }

 

        t-data = ch;                        //生成根结点

        t-lchild = CreateTree(t-lchild);    //构造左子树

        t-rchild = CreateTree(t-rchild);    //构造右子树

    }

    return t;

}

二叉树建立实现代码二，如下所示。

//创建树方法二

int CreateTree2(BiTree *t)

{

    char ch;

    scanf("%c", ch);

 

    if(ch == '#')

    {

        (*t) = NULL;

    }

    else

    {

        (*t) = (BiTree)malloc(sizeof(BitNode));

        if((*t) == NULL)

        {

            fprintf(stderr, "malloc() error in CreateTree2.\n");

            return ERROR;

        }

 

        (*t)-data = ch;

        CreateTree2(((*t)-lchild));

        CreateTree2(((*t)-rchild));

    }

    return OK;

}

其实建立二叉树，也是利用了递归的原理。只不过在原来应该打印结点的地方，改成生成结点、给结点赋值的操作而已。因此，完全可以用中序或后序遍历的方式实现二叉树的建立，只不过代码里生成结点和构造左右子树的代码顺序交互一下即可。

Q2: java构建二叉树算法

//******************************************************************************************************//

//*****本程序包括简单java构建二叉树代码的二叉树类java构建二叉树代码的实现和前序,中序,后序,层次遍历二叉树算法,*******//

//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//

//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//

//*******************************CopyRight By phoenix*******************************************//

//************************************Jan 12,2008*************************************************//

//****************************************************************************************************//

public class BinTree {

public final static int MAX=40;

private Object data; //数据元数

private BinTree left,right; //指向左,右孩子结点的链

BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点

int front;//层次遍历时队首

int rear;//层次遍历时队尾

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

{

String innerNode = "";

if(this == null)

return;

//若本节点是叶节点java构建二叉树代码，则将其移走

if(left==nullright == null)

{

System.out.print(this + " ");

data = null;

return;

}

//移走左子树若其存在

if(left!=null){

left.defoliate();

left = null;

}

//移走本节点java构建二叉树代码，放在中间表示中跟移走...

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

}

Q3: Java二叉树构造问题 要求：从控制台输入一行扩展二叉树的字符串，然后根据这个字符串构造二叉树。THX..

测试类：

package tree;

import java.util.*;

public class Test {

public static void main(String[] args){

ListTree trees=new ArrayListTree();

int id=1;

Tree tree1=new Tree(0,id++,"张三丰");

Tree tree2=new Tree(tree1.getId(),id++,"武当宋大侠宋远桥");

Tree tree3=new Tree(tree1.getId(),id++,"武当俞二侠俞莲舟");

Tree tree4=new Tree(tree1.getId(),id++,"武当俞三侠俞岱岩");

Tree tree5=new Tree(tree1.getId(),id++,"武当张四侠张松溪");

Tree tree6=new Tree(tree1.getId(),id++,"武当张五侠张翠山");

Tree tree7=new Tree(tree1.getId(),id++,"武当殷六侠殷梨亭");

Tree tree8=new Tree(tree1.getId(),id++,"武当莫七侠莫声谷");

Tree tree9=new Tree(tree6.getId(),id++,"明教张无忌");

Tree tree13=new Tree(tree2.getId(),id++,"叛徒宋青书");

Tree tree10=new Tree(0,id++,"任java构建二叉树代码我行");

Tree tree11=new Tree(tree10.getId(),id++,"令狐冲");

Tree tree12=new Tree(tree10.getId(),id++,"任盈盈");

trees.add(tree1);

trees.add(tree2);

trees.add(tree3);

trees.add(tree4);

trees.add(tree5);

trees.add(tree6);

trees.add(tree7);

trees.add(tree8);

trees.add(tree9);

trees.add(tree10);

trees.add(tree11);

trees.add(tree12);

trees.add(tree13);

for(int i=0;itrees.size();i++){

Tree tree=trees.get(i);

if(tree.getParentId()==0){

tree.showChildTree(trees);

}

}

}

}

树类：

package tree;

import java.util.List;

public class Tree {

private int parentId;

private int id;

private String showStr;

private String Spaces="";

public Tree() {

// TODO Auto-generated constructor stub

}

public Tree(int parentId,int id,String showStr){

this.parentId=parentId;

this.id=id;

this.showStr=showStr;

}

public void showChildTree(ListTree trees){

if(parentId!=0){

trees.get(id-1).setSpaces(trees.get(parentId-1).getSpaces()+" ");

}

System.out.println(trees.get(id-1).getSpaces()+showStr);

for(int i=0;itrees.size();i++){

Tree tree=trees.get(i);

if(tree.getParentId()==id){

tree.showChildTree(trees);

}

}

}

public int getParentId() {

return parentId;

}

public void setParentId(int parentId) {

this.parentId = parentId;

}

public int getId() {

return id;

}

public void setId(int id) {

this.id = id;

}

public String getShowStr() {

return showStr;

}

public void setShowStr(String showStr) {

this.showStr = showStr;

}

public String getSpaces() {

return Spaces;

}

public void setSpaces(String spaces) {

Spaces = spaces;

}

}

控制台效果图：

张三丰

武当宋大侠宋远桥

叛徒宋青书

武当俞二侠俞莲舟

武当俞三侠俞岱岩

武当张四侠张松溪

武当张五侠张翠山

明教张无忌

武当殷六侠殷梨亭

武当莫七侠莫声谷

任java构建二叉树代码我行

令狐冲

任盈盈

Q4: java 构建二叉树

首先java构建二叉树代码我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,

树是树形的, 似乎不太合适。

其实也可以用数组完成，而且效率更高.

关键是我觉得java构建二叉树代码你这个输入本身就是一个二叉树啊，

String input = "ABCDE F G";

节点编号从0到8. 层次遍历的话:

对于节点i.

leftChild = input.charAt(2*i+1); //做子树

rightChild = input.charAt(2*i+2);//右子树

如果你要将带有节点信息的树存到LinkedList里面, 先建立一个节点类:

class Node{

public char cValue;

public Node leftChild;

public Node rightChild;

public Node(v){

this.cValue = v;

}

}

然后遍历input,建立各个节点对象.

LinkedList tree = new LinkedList();

for(int i=0;i input.length;i++)

LinkedList.add(new Node(input.charAt(i)));

然后为各个节点设置左右子树:

for(int i=0;iinput.length;i++){

((Node)tree.get(i)).leftChild = (Node)tree.get(2*i+1);

((Node)tree.get(i)).rightChild = (Node)tree.get(2*i+2);

}

这样LinkedList 就存储了整个二叉树. 而第0个元素就是树根，思路大体是这样吧。

java构建二叉树代码的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于java实现二叉树的构建、java构建二叉树代码的信息别忘了在本站进行查找喔。