مشکلی در درخت

[alijuventusi]

سلام دوستان
در نوشتن درخت دودویی به مشکلی برخوردم که مطرحش میکنم.
119860همین طور که در شکل میبینید عضو ها فقط در چپ قرار میگیرند.لطفا مرا راهنمایی کنید تا قرار گیری اعض اول عضو چپ ، چپ و راستش و سپس عضو راست ، چپ و راستش پر شود.
این هم کدی که نوشتم.



public void insert(int k) {
TreeNode q = new TreeNode(k);
insertm(this.root, q);

}
private void insertm(TreeNode l, TreeNode q) {
boolean flag = false;

if (l == null) {
this.root = q;
} else {
if (l.left == null) {
l.left = q;
q.father = l;
flag = true;

} else if (l.right == null) {
l.right = q;
q.father = l;
flag = true;
}
if (!flag) {
if (l.left != null || l.right != null) {
insertm(l.left, q);
}
}
}

}

[vahid-p]

الان این شکلی که کشیدیدن، شکل مطلوبتونه؟
قاعده اضافه شدن به چه صورته؟ یه خورده دقیقتر بگید میخواید چیکار کنید؟

یعنی درختتون الان اینجوریه و نمیخواید اینجوری باشه؟
یعنی میخواید سطری درخت پر بشه درسته؟ یعنی 5 و 6 فرزند 2 بشن؟ اون 10 اون بالا اتفاقیه؟

[alijuventusi]

الان این شکلی که کشیدیدن، شکل مطلوبتونه؟
قاعده اضافه شدن به چه صورته؟ یه خورده دقیقتر بگید میخواید چیکار کنید؟

یعنی درختتون الان اینجوریه و نمیخواید اینجوری باشه؟
یعنی میخواید سطری درخت پر بشه درسته؟ یعنی 5 و 6 فرزند 2 بشن؟ اون 10 اون بالا اتفاقیه؟
شکلی که میخوام نهایت اضافه شدن اعضا پدید بیاد این شکل است که ضمیمه کردم در این پست.همه ی نودهای هم سطح عضو چپ و راست داشته باشند سپس به چپ ترین نود برای اضافه کردن عضو جدید برود.
مشکلی که برام به وجود اومده سطر اول گره چپ راست و دارم اما اط سطر بعد فقط گره های چپ ترین اضافه میشه
119873

[vahid-p]

خب پس شما یک درخت کامل رو میخواید.

برای پیاده سازی درخت کامل چندین روش وجود داره. ساده ترین هاش پیاده سازی با آرایه یا ArrayList هست که نیازی به اشاره گر حتی نداره. چون در درخت کامل دقیقا هر گره از روی شمارش میشه گره های فرزند رو پیدا کنید. البته میتونید با پوینتر هم درست کنید، اما حتما کنارش یک Queue لازم دارید که parent ها رو نگه داری کنه. تو اینترنت هم هست مطمئنا، ولی خب چون سادست خودم میگم :
اگر بخواید از آرایه استفاده کنید باید ماکزیمم تعداد گره هاش رو بدونید.
شماره گذاری در درخت کامل از چپ به راست ( در یک سطح ) و سپس رفتن به سطح های پایینتر است. پس اگر گره parent را گره i ام در نظر بگیریم، فرزند چپ آن 2i و فرزند راست 2i+1 است. این قاعده کلی برای تمام مراحل است.

آرایه ای :
public class ArrayCompleteTree<T> {

private final int maxSize;
private int cSize;
private final T tree[];

public ArrayCompleteTree(int capacity) {
maxSize = capacity;
tree = (T[]) new Object[capacity];
cSize = 0;
}

public boolean add(T p) {
if(cSize>=maxSize) return false;
tree[cSize]=p;
cSize++;
return true;
}

public T getLeftChild(int parentIndex){
int leftChild=2*parentIndex;
if(leftChild>=maxSize) return null;
return tree[leftChild];
}

public T getRightChild(int parentIndex){
int rightChild=2*parentIndex+1;
if(rightChild>=maxSize) return null;
return tree[rightChild];
}
}


ArrayList :

public class ArrayListCompleteTree<T> {
private final ArrayList<T> tree;

public ArrayListCompleteTree() {
tree =new ArrayList<>();
}

public boolean add(T p) {
return tree.add(p);
}

public T getLeftChild(int parentIndex){
int leftChild=2*parentIndex;
if(leftChild>=tree.size()) return null;
return tree.get(leftChild);
}

public T getRightChild(int parentIndex){
int rightChild=2*parentIndex+1;
if(rightChild>=tree.size()) return null;
return tree.get(rightChild);
}
}

[alijuventusi]

ممنون از توضیح خوب و کاملتون اما پیاده سازی با آرایه مورد نیاز بنده نیست حتما باید از لینک لیست استفاده بشه و به همین ترتیبی کدی که نوشتم.
الان در این کد بنده همه چیز درست است اما نودهای راست پر نمیشه نمیدونم چرا ؟

[vahid-p]

اینم با اشاره گر : ( نکته ای که فقط میمونه اگر درخت کامل بخوای یه گره رو حذف کنی و همچنان درخت کامل بمونه یا باید گره آخر رو حذف کنی و پدرش رو به صف برگردونی ( اگر گره فرزند سمت راست پدر بود وگرنه خودش تو صف هست ) یا هم اگر هر گره ای رو بخوای حذف کنی، اونوقت باید کل درخت رو از اول درست کنی. یا اگر بعد از حذف مهم نیست کامل بمونه، خب میتونی گره پدر رو اول صف قرار بدی ( که برای اینکار باید گره پدر رو در صف جدیدی قرار بدی و کل صف قبلی رو به صف حاضر addAll کنی ))


public class PointerCompleteTree<T> {
private Node<T> root;
private Queue<Node<T>> queue;
public PointerCompleteTree() {
queue=new LinkedList<>();
}

public boolean add(Node<T> p) {
if(root==null){
root=p;
return queue.add(p);
}
Node<T> parent=queue.peek();
if(parent.getLeftChild()==null){
parent.setLeftChild(p);
queue.add(p);
}else {
parent.setRightChild(p);
queue.add(p);
queue.remove();
}
return queue.add(p);
}

public Node<T> getLeftChild(Node<T> parent){
return parent.getLeftChild();
}

public Node<T> getRightChild(Node<T> parent){
return parent.getLeftChild();
}
}

[vahid-p]

خب مشکل کار شما اینجاست :

if (!flag) {
if (l.left != null || l.right != null) {
insertm(l.left, q);
}
}


اون شرط داخلیه که نمیخواد ولی باز ببینید رو شکل براتون مثال بزنم. گفته اگر فرزندهای 10 هر دو پر شده بودند، گره سمت چپ رو پدر قرار بده ( طبق چیزی که فهمیدم گره L همون پدر هست ) و گره q رو فرزند گره سمت چپ قرار بده. خب این همیشه چپ رو اضافه میکنه. اگر شما مجاز به استفاده از صف باشید که خب پیاده سازیش رو بالا گفتم. اگر نباشید، کارتون سخت میشه. میدونی چرا؟ چون فرض کن تو رسیدی به سطر سوم. شما باید اول چک کنید ببینید اگر فرزند سمت راست داره، اگر جدشون ( پدر پدر ) فرزنداشون تا سطح سوم پر هستند، اونوقت میتونی به سطح بعدی بری. در کل چند سطح که بیای پایینتر هی باید تا اون سطح تمام اجداد فرزنداشون رو تا اون سطح پر باشه تا بتونی سطح بعدی رو اضافه کنی. این کار سخت و زمانگیریه.

راه حل همون ایجاد صف هست که parent های بدون گره فرزند رو در خودش به ترتیب از چپ به راست با اولویت بندی ذخیره میکنه و همیشه میدونی کی فرزندش تکمیل نیست و اولویت با اونه..