構造滿二叉排序樹java

㈠ 給定序列 6 8 5 7 9 3構建二叉排序樹 並畫出先序索二叉樹

二叉排序樹就是中序遍歷之後是有序的；

構造二叉排序樹步驟如下；

插入法構造

中序遍歷結果是 ： 3456789；

先序遍歷結果是：6435879；

㈡ java二叉樹構造問題 要求：從控制台輸入一行擴展二叉樹的字元串，然後根據這個字元串構造二叉樹。THX..

日日財源順意來 年年福祿隨春到 橫批：新春大吉

㈢ 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 = 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;i<input.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個元素就是樹根，思路大體是這樣吧。

㈣ 二叉排序樹的構造和查找方法

二叉排序樹的構造過程：按照給定序列，以此將結點插入二叉排序樹中，在二叉排序樹中插入新結點，要保證插入後的二叉樹仍符合二叉排序樹的定義。

插入過程：若二叉排序樹為空，則待插入結點*S作為根結點插入到空樹中；

當非空時，將待插結點關鍵字S->key和樹根關鍵字t->key進行比較，

若s->key = t->key,則無須插入，若s->key< t->key,則插入到根的左子樹中，

若s->key> t->key,則插入到根的右子樹中。而子樹中的插入過程和在樹中的插入過程相同，

如此進行下去，直到把結點*s作為一個新的樹葉插入到二叉排序樹中，或者直到發現樹已有相同關鍵字的結點為止。
說明：

① 每次插入的新結點都是二叉排序樹上新的葉子結點。

② 由不同順序的關鍵字序列，會得到不同二叉排序樹。

③ 對於一個任意的關鍵字序列構造一棵二叉排序樹，其實質上對關鍵字進行排序。
查找的過程類似，從根結點開始進行比較，小於根結點的在左子樹上，大於根結點的在右子樹上，以此查找下去，直到查找成功或不成功（比較到葉子結點）。

㈤ java如何創建一顆二叉樹

計算機科學中，二叉樹是每個結點最多有兩個子樹的有序樹。通常子樹的根被稱作「左子樹」（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) ), )))

㈥ 二叉排序樹（BST） Java實現

public class Node<E> {
int key; // data used as key value
E data; // other data
Node<E> leftChild; // this node's left child
Node<E> rightChild; // this node's right child

public Node(int key, E o) {
this.key = key;
this.data = o;
}

public void displayNode() {
System.out.printf("%d, %s\n", key, data.toString());
}
}

===============================================================

package net.acoder.adt.tree;

public class Tree<E> {
private Node<E> root;

public Tree(Node<E> root) {
if (root == null) {
throw new NullPointerException("root can't be null");
}
this.root = root;
}

public Tree(int key, E o) {
this(new Node<E>(key, o));
}

public Node<E> getRoot() {
return root;
}

/**
* find a node by its key
*
* @ key
* @return
*/
public Node<E> find(int key) {
Node<E> current = root;
while (current.key != key) {
if (key < current.key) {
current = root.leftChild;
} else {
current = root.rightChild;
}
if (current == null) {
return null;
}
}
return current;
}

/**
* insert a node to this tree
*
* @param key
* @param o
*/
public void insert(int key, E o) {
Node<E> aNode = new Node<E>(key, o);
if (root == null) {
this.root = aNode;
return;
}

Node<E> current = root;
Node<E> parent = root;
while (true) {
parent = current;
if (key < parent.key) {
current = parent.leftChild;
if (current == null) {
parent.leftChild = aNode;
return;
}
} else {
current = parent.rightChild;
if (current == null) {
parent.rightChild = aNode;
return;
}
}
}
}

public boolean delete(int key) {
Node<E> current = root;
Node<E> parent = root;
boolean isLeftChild = true;
// search for node
while (current.key != key) {
parent = current;
if (key < current.key) {
isLeftChild = true;
current = current.leftChild;
} else {
isLeftChild = false;
current = current.rightChild;
}
if (current == null) {
return false;
}
}

// if no children, simply delete it
if (current.leftChild == null && current.rightChild == null) {
if (current == parent) {
root = null;
} else if (isLeftChild == true) {
parent.leftChild = null;
} else if (isLeftChild == false) {
parent.rightChild = null;
}
return true;
}

// if no left children, replace with right subtree
if (current.leftChild == null) {
if (current == root) {
root = current.rightChild;
} else if (isLeftChild) {
parent.leftChild = current.rightChild;
} else if (!isLeftChild) {
parent.leftChild = current.rightChild;
}
return true;
}

// if no right children, replace with left subtree
if (current.rightChild == null) {
if (current == root) {
root = current.leftChild;
} else if (isLeftChild) {
parent.leftChild = current.leftChild;
} else if (!isLeftChild) {
parent.leftChild = current.leftChild;
}
return true;
}

// get successor of node to delete
Node<E> successor = getSuccessor(current);
if (current == root) {
current = successor;
} else if (isLeftChild) {
parent.leftChild = successor;
} else {
parent.rightChild = successor;
}
successor.leftChild = current.leftChild;
return true;
}

private Node<E> getSuccessor(Node<E> delNode) {
Node<E> successorParent = delNode;
Node<E> successor = delNode;
Node<E> current = delNode.rightChild;
while (current != null) {
successorParent = successor;
successor = current;
current = current.leftChild;
}

if (successor != delNode.rightChild) {
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;

}
return successor;
}

public void inOrder(Node<E> aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
aNode.displayNode();
inOrder(aNode.rightChild);
}
}

public void preOrder(Node<E> aNode) {
if (aNode != null) {
aNode.displayNode();
inOrder(aNode.leftChild);
inOrder(aNode.rightChild);
}
}

public void backOrder(Node<E> aNode) {
if (aNode != null) {
inOrder(aNode.leftChild);
inOrder(aNode.rightChild);
aNode.displayNode();
}
}

public Node<E> minimum() {
Node<E> current = this.root;
Node<E> result = null;
while (current != null) {
result = current;
current = current.leftChild;
}
return result;
}

public Node<E> maximum() {
Node<E> current = this.root;
Node<E> result = null;
while (current != null) {
result = current;
current = current.rightChild;
}
return result;
}
}

以前的代碼, 記得沒寫完, 好像就是BST

㈦ 二叉排序樹怎麼構造

假設二叉排序樹T為空，則創建一個keyword為k的結點。將其作為根結點。

否則將k和根結點的keyword進行比較，假設相等則返回，假設k小於根結點的keyword則插入根結點的左子樹中，否則插入根結點的右子樹中。

int InsertBST(BSTNode *p, KeyType k)
{
if(p==NULL)
{
p=(BSTNode*)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if(k==p->key)
return 0;
else if(k<p->key)
return InsertBST(p->lchild, k);
else
return InsertBST(p->rchild, k);
}
二叉排序樹的生成演算法：
BSTNode *CreateBST(KeyType A[], int n)
{
BSTNode *bt=NULL;
int i=0;
while(i<n)
{
InsertBST(bt, A[i]);
i++;
}
return bt;
}

(7)構造滿二叉排序樹java擴展閱讀：

在一般情況下，設 P（n，i）為它的左子樹的結點個數為 i 時的平均查找長度。如圖的結點個數為 n = 6 且 i = 3; 則 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6

注意：這里 P(3)、P(2) 是具有 3 個結點、2 個結點的二叉分類樹的平均查找長度。 在一般情況，P（i）為具有 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 = 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(front<rear)
{
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 == null&&right == 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 = leftHeight<rightHeight?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(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?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==null&&right == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子樹若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本節點，放在中間表示中跟移走...
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());
}