锐客网

  1. 首页 > 睿知 > it技术 > >

二叉树代码java 二叉树代码c语言

IT技术binTree

java 构建二叉树首先我想问为什么要用LinkedList 来建立二叉树呢? LinkedList 是线性表,
树是树形的, 似乎不太合适 。
其实也可以用数组完成，而且效率更高.
关键是我觉得你这个输入本身就是一个二叉树啊，
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 = https://www.04ip.com/post/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数据结构二叉树深度递归调用算法求内部算法过程详解二叉树
1
23
45 67
这个二叉树的深度是3，树的深度是最大结点所在的层，这里是3.
应该计算所有结点层数，选择最大的那个 。
根据上面的二叉树代码，递归过程是：
f(1)=f(2) 1f(3)1 ? f(2)1 : f(3)1
f(2) 跟f(3)计算类似上面 ， 要计算左右结点，然后取大者
所以计算顺序是f(4.left) = 0, f(4.right) = 0
f(4) = f(4.right)1 = 1
然后计算f(5.left) = 0,f(5.right) = 0
f(5) = f(5.right)1 =1
f(2) = f(5)1 =2
f(1.left) 计算完毕，计算f(1.right) f(3) 跟计算f(2)的过程一样 。
得到f(3) = f(7)1 = 2
f(1) = f(3)1 =3
if(depleftdepright){
return depleft 1;
}else{
return depright 1;
}
只有left大于right的时候采取left1 ， 相等是取right
java如何创建一颗二叉树计算机科学中 ， 二叉树是每个结点最多有两个子树的有序树 。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree） 。二叉树常被用作二叉查找树和二叉堆或是二叉排序树 。
二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒 。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n21 。
树是由一个或多个结点组成的有限集合，其中：
⒈必有一个特定的称为根(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) ),)))
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 = https://www.04ip.com/post/data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = https://www.04ip.com/post/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)
{
【二叉树代码java 二叉树代码c语言】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 1heightOfTree;
}
//如果对象不在树中,结果返回-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;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this" ");
data = https://www.04ip.com/post/null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点 ， 放在中间表示中跟移走...
innerNode= this" ";
data = https://www.04ip.com/post/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中把数组以二叉树形式打印出来你说的意思应该是用数组的方式存储二叉树，这需要利用到完全二叉树的性质，
,完全二叉树通常采用数组而不是链表存储,其存储结构如下:
var
tree:array[1..n]of
longint;{n:integer;n=1}
对于tree[i]，有如下特点：
（1）若i为奇数且i1，那么tree的左兄弟为tree[i-1]；
（2）若i为偶数且in，那么tree的右兄弟为tree[i 1]；
（3）若i1，tree的双亲为tree[i
div
2]；
（4）若2*i=n，那么tree的左孩子为tree[2*i]；若2*i 1=n，那么tree的右孩子为tree[2*i 1]；
（5）若in
div
2,那么tree[i]为叶子结点（对应于（3））；
（6）若i(n-1)
div
2.那么tree[i]必有两个孩子（对应于（4）） 。
（7）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树 。
完全二叉树第i层至多有2^（i-1）个节点，共i层的完全二叉树最多有2^i-1个节点 。
代码简单，网上很多，不懂也可以问我
java 由字符串构成的二叉树java构造二叉树二叉树代码java，可以通过链表来构造二叉树代码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 = https://www.04ip.com/post/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 1heightOfTree;}//如果对象不在树中,结果返回-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;//若本节点是叶节点二叉树代码java，则将其移走if(left==nullright == null){System.out.print(this" ");data = https://www.04ip.com/post/null;return;}//移走左子树若其存在if(left!=null){left.defoliate();left = null;}//移走本节点，放在中间表示中跟移走...String innerNode= this" ";data = https://www.04ip.com/post/null;//移走右子树若其存在if(right!=null){right.defoliate();right = null;}}/*** @param args*/public static void main(String[] args) {// TODO Auto-generated method stubBinTree 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和二叉树代码c语言的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站 。

    推荐阅读


    上一篇：如何在Apex Legends中切换服务器？ apexl怎么切换服务器

    下一篇：怎样删除微信直播商品订单，微信上的直播怎么删除