java二叉樹父節點

1. 求數據結構二叉樹查找結點及其父節點的代碼，謝謝！！！

#include<iostream>

#include<map>

using namespace std;

const int N=15e3+100;

struct node{

int v;//結點值

int l,r;//左右孩子的下標

st()

{//初始化

l=r=-1;

}

}tree[4*N];//4倍空間,用來儲存二叉樹

map<int,int>mp;//儲存數值在數組a中的下標

int a[N];//基礎數組,數組tree在其基礎上建樹

int n=1;//1 5 8 0 0 0 6 0 0

void build_tree(int rt,int &num)

{//構建二叉樹

if(a[num]==0)

{//a[num]==0,表示空結點

tree[rt].v=-1;

}

else

{

if(mp.count(a[num])==0)

mp[a[num]]=rt;//儲存a[num]在樹中的位置

tree[rt].v=a[num];//結點賦值

num++;

build_tree(2*rt,num);//左孩子

num++;

build_tree(2*rt+1,num);//右孩子

}

}

/*

1 5 8 0 0 0 6 0 0

3

8 1 6

*/

int main()

{

int x=1,m=0;

do

{

cin>>a[n++];//儲存結點值

}

while(getchar()!=' ');//回車結束輸入

build_tree(1,x);//構建二叉樹(結構體數組模擬)

cin>>m;//查詢次數

for(int i=0;i<m;i++)

{

int num,y;

cin>>num;//查詢值

y=mp[num];//mp[num]是num在tree數組中的位置,查詢效率O(log2n)

y/=2;//左右孩子的下標除以2，就是父節點的下標

if(y==0)

{//父節點下標為0，既是根節點

cout<<0<<endl;

}

else

{//輸出父節點值

cout<<tree[y].v<<endl;

}

}

return 0;

}

2. java二叉樹一個方法求解釋

既然涉及到二叉樹了，遞歸就肯定存在了

private Baumknoten deleteMaxValue() {

Baumknoten newRoot; //一個節點

if (this.rightTree == null) { //右子節點 == null

newRoot = this.leftTree; //賦值
} else {

this.rightTree = this.rightTree.deleteMaxValue(); //本節點 = 本節點的右子節點的這個方法（也就是你貼出來的方法）返回的節點。
newRoot = this; //節點賦值
}

return newRoot; //返回節點
}

這就是一個遞歸，或許樹的定義是左子節點比父節點小，右子節點比父節點大，

但有些出路，不能肯定。

遞歸的意思就是在方法內部調用自己，滿足一定條件後跳出，可以理解為循環，

但有些循環是不能實現某些遞歸能實現的功能的。

我給你講解下這個方法的意思吧：

其實這個方法的需求是找出二叉樹中最大的值，並返回。

假設樹的定義是左子節點比父節點小，右子節點比父節點大的常規樹：

進入方法，定義一個節點，然後判斷當前節點的右節點是不是空，如果是空就證

明當前節點是最大值了，返回當前節點就行了（但他返回的是當前節點的左子節

點，詫異！），如果不是空就調用當前節點的右子節點的deleteMaxValue方法

（也就是你貼出來的方法，是自己，這就構成了遞歸），並把右子節點的

deleteMaxValue方法的返回值返回到父節點的方法里，父節點的方法接收返回值

並返回給調用者，進入右子節點的deleteMaxValue方法後，繼續上面的操作，直

到滿足了條件跳出為止，條件就是if (this.rightTree == null)。

典型的遞歸。

3. java二叉樹的順序表實現

做了很多年的程序員，覺得什麼樹的設計並不是非常實用。二叉樹有順序存儲，當一個insert大量同時順序自增插入的時候，樹就會失去平衡。樹的一方為了不讓塌陷，會增大樹的高度。性能會非常不好。以上是題外話。分析需求在寫代碼。
import java.util.List;

import java.util.LinkedList;

public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;

private static class Node {
Node leftChild;
Node rightChild;
int data;

Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}

// 創建二叉樹
public void createBintree() {
nodeList = new LinkedList<Node>();

// 將數組的值轉換為node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}

// 對除最後一個父節點按照父節點和孩子節點的數字關系建立二叉樹
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}

// 最後一個父節點
int lastParentIndex = array.length / 2 - 1;

// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果為奇數，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}

// 前序遍歷
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

// 中序遍歷
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}

inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}

// 後序遍歷
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}

postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}

public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);

System.out.println("前序遍歷：");
preOrderTraverse(root);
System.out.println();

System.out.println("中序遍歷：");
inOrderTraverse(root);
System.out.println();

System.out.println("後序遍歷：");
postOrderTraverse(root);
}
}

4. 怎麼得到二叉樹的父節點

那你定義節點的時候需要有指向父節點的指針
要不然就只有遞歸遍歷找了

5. 用java建立二叉樹

數據結構的教材里有，
建立兩個類就應該可以了。

一個是樹的節點，一個是樹，這個是我以前編寫的寬度優先遍歷的樹的構建和遍歷，希望對你有幫助。文件名是：Tree.java

import java.util.ArrayList;

// 樹的一個節點
class TreeNode {

Object _value = null; // 他的值
TreeNode _parent = null; // 他的父節點，根節點沒有PARENT
ArrayList _childList = new ArrayList(); // 他的孩子節點

public TreeNode( Object value, TreeNode parent ){
this._parent = parent;
this._value = value;
}

public TreeNode getParent(){
return _parent;
}

public String toString() {
return _value.toString();
}
}

public class Tree {

// 給出寬度優先遍歷的值數組，構建出一棵多叉樹
// null 值表示一個層次的結束
// "|" 表示一個層次中一個父親節點的孩子輸入結束
// 如：給定下面的值數組：
// { "root", null, "left", "right", null }
// 則構建出一個根節點，帶有兩個孩子("left","right")的樹
public Tree( Object[] values ){
// 創建根
_root = new TreeNode( values[0], null );

// 創建下面的子節點
TreeNode currentParent = _root; // 用於待創建節點的父親
//TreeNode nextParent = null;
int currentChildIndex = 0; // 表示 currentParent 是他的父親的第幾個兒子
//TreeNode lastNode = null; // 最後一個創建出來的TreeNode，用於找到他的父親
for ( int i = 2; i < values.length; i++ ){

// 如果null ,表示下一個節點的父親是當前節點的父親的第一個孩子節點
if ( values[i] == null ){
currentParent = (TreeNode)currentParent._childList.get(0);
currentChildIndex = 0;
continue;
}

// 表示一個父節點的所有孩子輸入完畢
if ( values[i].equals("|") ){
if ( currentChildIndex+1 < currentParent._childList.size() ){
currentChildIndex++;
currentParent = (TreeNode)currentParent._parent._childList.get(currentChildIndex);
}
continue;
}

TreeNode child = createChildNode( currentParent, values[i] );
}
}

TreeNode _root = null;

public TreeNode getRoot(){
return _root;
}
/**
// 按寬度優先遍歷，列印出parent子樹所有的節點
private void printSteps( TreeNode parent, int currentDepth ){
for ( int i = 0; i < parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
System.out.println(currentDepth+":"+child);
}
if ( parent._childList.size() != 0 ) System.out.println(""+null);// 為了避免葉子節點也會列印null

//列印 parent 同層的節點的孩子
if ( parent._parent != null ){ // 不是root
int i = 1;
while ( i < parent._parent._childList.size() ){// parent 的父親還有孩子
TreeNode current = (TreeNode)parent._parent._childList.get(i);
printSteps( current, currentDepth );
i++;
}
}

// 遞歸調用，列印所有節點
for ( int i = 0; i < parent._childList.size(); i++ ){
TreeNode child = (TreeNode)parent._childList.get(i);
printSteps( child, currentDepth+1 );
}

}

// 按寬度優先遍歷，列印出parent子樹所有的節點
public void printSteps(){
System.out.println(""+_root);
System.out.println(""+null);

printSteps(_root, 1 );
}**/

// 將給定的值做為 parent 的孩子，構建節點
private TreeNode createChildNode( TreeNode parent, Object value ){
TreeNode child = new TreeNode( value , parent );
parent._childList.add( child );
return child;
}

public static void main(String[] args) {

Tree tree = new Tree( new Object[]{ "root", null,
"left", "right", null,
"l1","l2","l3", "|", "r1","r2",null } );
//tree.printSteps();

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(1) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(0) )._childList.get(2) );

System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(0) );
System.out.println(""+ ( (TreeNode)tree.getRoot()._childList.get(1) )._childList.get(1) );

}

}

6. 如何用java實現二叉樹的構建

樹的構建方法

注意：

1. 父節點數組下標從0到 n/2 -1 ，但是遍歷時要小於n/2-1，因為最後一個父節點可能沒有右孩子，當n/2-1為奇數時才有右孩子，為偶數時只有左孩子。

2. 結點左孩子下標為2n+1，右孩子下標為2n+2。

7. 求數據結構（JAVA版）實驗樹和二叉樹題目答案

/**
* @param args
之前在大學的時候寫的一個二叉樹演算法，運行應該沒有問題，就看適不適合你的項目了 */
public static void main(String[] args) {

BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("遞歸前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非遞歸前序遍歷二叉樹結果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("遞歸中序遍歷二叉樹的結果為:");
tree.inOrder(tree);
System.out.println();
System.out.println("非遞歸中序遍歷二叉樹的結果為:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("遞歸後序遍歷二叉樹的結果為:");
tree.postOrder(tree);
System.out.println();
System.out.println("非遞歸後序遍歷二叉樹的結果為:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("遞歸求二叉樹中所有結點的和為:"+getSumByRecursion(tree));
System.out.println("非遞歸求二叉樹中所有結點的和為:"+getSumByNoRecursion(tree));

System.out.println("二叉樹中,每個節點所在的層數為:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的層為:" + tree.level(p));
System.out.println("二叉樹的高度為:" + height(tree));
System.out.println("二叉樹中節點總數為:" + nodes(tree));
System.out.println("二叉樹中葉子節點總數為:" + leaf(tree));
System.out.println("二叉樹中父節點總數為:" + fatherNodes(tree));
System.out.println("二叉樹中只擁有一個孩子的父節點數:" + oneChildFather(tree));
System.out.println("二叉樹中只擁有左孩子的父節點總數:" + leftChildFather(tree));
System.out.println("二叉樹中只擁有右孩子的父節點總數:" + rightChildFather(tree));
System.out.println("二叉樹中同時擁有兩個孩子的父節點個數為:" + doubleChildFather(tree));
System.out.println("--------------------------------------");
tree.exChange();
System.out.println("交換每個節點的左右孩子節點後......");
System.out.println("遞歸前序遍歷二叉樹結果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非遞歸前序遍歷二叉樹結果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("遞歸中序遍歷二叉樹的結果為:");
tree.inOrder(tree);
System.out.println();
System.out.println("非遞歸中序遍歷二叉樹的結果為:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("遞歸後序遍歷二叉樹的結果為:");
tree.postOrder(tree);
System.out.println();
System.out.println("非遞歸後序遍歷二叉樹的結果為:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結果: ");
tree.LayerOrder(tree);
System.out.println();

System.out.println("遞歸求二叉樹中所有結點的和為:"+getSumByRecursion(tree));
System.out.println("非遞歸求二叉樹中所有結點的和為:"+getSumByNoRecursion(tree));

System.out.println("二叉樹中,每個節點所在的層數為:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的層為:" + tree.level(p));
System.out.println("二叉樹的高度為:" + height(tree));
System.out.println("二叉樹中節點總數為:" + nodes(tree));
System.out.println("二叉樹中葉子節點總數為:" + leaf(tree));
System.out.println("二叉樹中父節點總數為:" + fatherNodes(tree));
System.out.println("二叉樹中只擁有一個孩子的父節點數:" + oneChildFather(tree));
System.out.println("二叉樹中只擁有左孩子的父節點總數:" + leftChildFather(tree));
System.out.println("二叉樹中只擁有右孩子的父節點總數:" + rightChildFather(tree));
System.out.println("二叉樹中同時擁有兩個孩子的父節點個數為:" + doubleChildFather(tree));
}
}

8. java如何求二叉樹中任意兩個節點的最大距離

兩個節點的距離的定義是這兩個節點間邊的個數，
比如某個孩子節點和父節點間的距離是1，和相鄰兄弟節點間的距離是2，
優化時間空間復雜度。
代碼：
void MaxDistance(Tree* root,int &deep,int & maxdis)
{
if(root)
{
deep=0;
maxdis=0;
}
int l_deep,l_maxdis;
int r_deep,r_maxdis;
if(root->left!=null)
MaxDistance(root->left,l_deep,l_maxdis);
if(root->right!=null)
MaxDistance(root->right,r_deep,r_maxdis);
deep=(l_deep>r_deep?l_deep:r_deep)+1;
maxdis=l_maxdis>r_maxdis?l_maxdis:r_maxdis;
maxdis=(l_deep+r_deep)>maxdis?l_deep+r_deep:maxdis;
}
}

9. 求教,java二叉樹節點

以下代碼是裸寫，沒有經過測試，你可以參考下：
為空的情況你已經寫了，非空時的邏輯如下（以左邊為例，右側同理）：
新建一個節點A
把左邊掛在A下
把A掛在左邊
BinaryTreeNodenewLeft=newBinaryTreeNode(d);
if(left==null)
{
left=newLeft;
}
esle
{
newLeft.left=left;//這里的邏輯可以再豐富下，可以掛在newLeft.right
left=newLeft;
}

10. 如何用java實現二叉樹

import java.util.List;
import java.util.LinkedList;

public class Bintrees {
private int[] array = {1, 2, 3, 4, 5, 6, 7, 8, 9};
private static List<Node> nodeList = null;

private static class Node {
Node leftChild;
Node rightChild;
int data;

Node(int newData) {
leftChild = null;
rightChild = null;
data = newData;
}
}

// 創建二叉樹
public void createBintree() {
nodeList = new LinkedList<Node>();

// 將數組的值轉換為node
for (int nodeIndex = 0; nodeIndex < array.length; nodeIndex++) {
nodeList.add(new Node(array[nodeIndex]));
}

// 對除最後一個父節點按照父節點和孩子節點的數字關系建立二叉樹
for (int parentIndex = 0; parentIndex < array.length / 2 - 1; parentIndex++) {
nodeList.get(parentIndex).leftChild = nodeList.get(parentIndex * 2 + 1);
nodeList.get(parentIndex).rightChild = nodeList.get(parentIndex * 2 + 2);
}

// 最後一個父節點
int lastParentIndex = array.length / 2 - 1;

// 左孩子
nodeList.get(lastParentIndex).leftChild = nodeList.get(lastParentIndex * 2 + 1);

// 如果為奇數，建立右孩子
if (array.length % 2 == 1) {
nodeList.get(lastParentIndex).rightChild = nodeList.get(lastParentIndex * 2 + 2);
}
}

// 前序遍歷
public static void preOrderTraverse(Node node) {
if (node == null) {
return;
}
System.out.print(node.data + " ");
preOrderTraverse(node.leftChild);
preOrderTraverse(node.rightChild);
}

// 中序遍歷
public static void inOrderTraverse(Node node) {
if (node == null) {
return;
}

inOrderTraverse(node.leftChild);
System.out.print(node.data + " ");
inOrderTraverse(node.rightChild);
}

// 後序遍歷
public static void postOrderTraverse(Node node) {
if (node == null) {
return;
}

postOrderTraverse(node.leftChild);
postOrderTraverse(node.rightChild);
System.out.print(node.data + " ");
}

public static void main(String[] args) {
Bintrees binTree = new Bintrees();
binTree.createBintree();
Node root = nodeList.get(0);

System.out.println("前序遍歷：");
preOrderTraverse(root);
System.out.println();

System.out.println("中序遍歷：");
inOrderTraverse(root);
System.out.println();

System.out.println("後序遍歷：");
postOrderTraverse(root);
}
}

輸出結果：
前序遍歷：
1 2 4 8 9 5 3 6 7
中序遍歷：
8 4 9 2 5 1 6 3 7
後序遍歷：
8 9 4 5 2 6 7 3 1