快捷導(dǎo)航

Java如何實現(xiàn)N叉樹數(shù)據(jù)結(jié)構(gòu)

更新時間：2024年05月11日 09:28:00 作者：allway2

這篇文章主要介紹了Java如何實現(xiàn)N叉樹數(shù)據(jù)結(jié)構(gòu)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

Java實現(xiàn)N叉樹數(shù)據(jù)結(jié)構(gòu)

package MaximumDepthNAryTreeNew;
 
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
// class representing node of n-ary tree
class Node {
	int val;
	ArrayList<Node> children;
 
	public Node(int val) {
		this.val = val;
		this.children = new ArrayList<>();
	}
}
 
class NumberOfSiblingsOfAGivenNodeInNAryTree {
 
	public static int maxDepth(Node root) {
		if (root == null)
			return 0;
		int max = 0;
		for (Node n : root.children) {
			max = Math.max(max, maxDepth(n));
		}
		return max + 1;
	}
 
	private static int siblings(Node root, int target) {
		// if the given node is equals to the root or root is null, return 0
		if (root == null || root.val == target) {
			return 0;
		}
		// create a queue of nodes
		Queue<Node> queue = new LinkedList<>();
		// push the root to queue
		queue.add(root);
		// do a BFS of the tree
		while (!queue.isEmpty()) {
			// remove one element from the queue
			Node curr = queue.poll();
			// traverse its children
			for (int i = 0; i < curr.children.size(); i++) {
				// current child
				Node currChild = curr.children.get(i);
				// if current child is the target, return (parent's children count - 1)
				if (currChild.val == target) {
					return (curr.children.size() - 1);
				}
				// add the child to the queue
				queue.add(currChild);
			}
		}
		// if there is no match, return -1
		return -1;
	}
 
	public static void main(String[] args) {
		// Example n-ary tree
		Node root = new Node(51);
		// children of 51
		root.children.add(new Node(10));
		root.children.add(new Node(41));
		root.children.add(new Node(6));
		root.children.add(new Node(32));
		// children of 10
		root.children.get(0).children.add(new Node(53));
		// children of 41
		root.children.get(1).children.add(new Node(95));
		// children of 6
		root.children.get(2).children.add(new Node(28));
		// children of 32
		root.children.get(3).children.add(new Node(9));
		root.children.get(3).children.add(new Node(11));
		// children of 53
		root.children.get(0).children.get(0).children.add(new Node(5));
		root.children.get(0).children.get(0).children.add(new Node(7));
		// children of 11
		root.children.get(3).children.get(1).children.add(new Node(3));
		root.children.get(3).children.get(1).children.add(new Node(8));
		System.out.println(siblings(root, 10));
		System.out.println(siblings(root, 11));
		System.out.println(maxDepth(root));
	}
}

N叉樹的結(jié)點定義

N叉樹

public class TreeNode{
  public int data;
  public TreeNode firstChild;
  public TreeNode secondChild;
  public TreeNode thirdChild;
  ...
  ...
}

由于并不是在所有的情況下都需要使用所有的指針，所以將導(dǎo)致大量的內(nèi)存浪費，此外，另外一個問題是事先不知道節(jié)點個數(shù)

N叉樹的表示

因為需要遍歷樹中的所有節(jié)點，所以一種可能的解決方法是：

1.同一個雙親節(jié)點（兄弟）孩子節(jié)點從左至右排列

2.雙親節(jié)點只能指向第一個孩子節(jié)點，刪除從雙親節(jié)點到其他孩子節(jié)點的指針鏈接，

上述的具體含義是，如果孩子節(jié)點之間有一條鏈路相連，那么雙親節(jié)點就不需要額外的指針指向所有的孩子節(jié)點。這是因為從雙親節(jié)點的第一個孩子節(jié)點開始就能夠遍歷所有節(jié)點，因此，只要雙親節(jié)點用一個指針指向其第一個孩子節(jié)點，且同一個雙親節(jié)點的所有孩子之間都有鏈路，就可以解決上述問題

代碼定義表示

public class TreeNode{
  public int data;
  public TreeNode firstChild;
  public TreeNode nextSibling;
  
  public int getData(){
    return data;
  }
  
  public void setData(int data){
    this.data = data;
  }

  public BinaryTreeNode getFirstChild(){
    return firstChild;
  }

  public void setFirstChild(BinaryTreeNode firstChild){
    this.firstChild = firstChild;
  }

  public BinaryTreeNode getNextSibling(){
    return nextSibling;
  }

  public void setNextSibling(BinaryTreeNode nextSib ling){
    this.nextSibling = nextSibling;
  }


}