جاوا

جلسه ۶۹: افزودن گره به درخت جستجوی دودویی به روش بازگشتی در جاوا

این جلسه به شما کمک می کند روش بازگشتی را از طریق درختان یاد بگیرید. موارد زیر را بیان خواهیم کرد:

  • درخت جستجوی دودویی چیست؟
  • پیاده سازی بوسیله کد
  • تفسیر کد
  • متد main
  • متد بازگشتی
  • حالت پایه
  • حالت بازگشتی
  • درک از طریق پشته

درخت جستجوی دودویی چیست؟

درخت جستجوی دودویی (Binary Search Tree یا BST) یک ساختمان داده سلسله مراتبی از رئوسی است که بوسیله یال ها به هم متصل شده اند. در این ساختمان داده مقدار درون گره سمت چپ کمتر از مقدار درون گره والد است و مقدار درون گره سمت راست بیشتر از مقدار درون گره والد است.

پیاده سازی بوسیله کد

class binarySearchTree {

	//Variables
	private Node root;
	//Getter for Root
	public Node getRoot() {
		return root;
	}
  //Setter for root
  public void setRoot(Node root) {
		this.root = root;
	}


	//Recursive function to insert a value in BST 
	public Node recursive_insert(Node currentNode, int value) {

		//Base Case
		if (currentNode == null) {
			return new Node(value);
		}

		if (value < currentNode.getData()) { //Iterate left sub-tree currentNode.setLeftChild(recursive_insert(currentNode.getLeftChild(), value)); } else if (value > currentNode.getData()) {
			//Iterate right sub-tree
			currentNode.setRightChild(recursive_insert(currentNode.getRightChild(), value));
		} else {
			// value already exists
			return currentNode;
		}

		return currentNode;
	}

	//Function to call recursive insert
	public boolean insert(int value) {

		root = recursive_insert(this.root, value);
		return true;
	}

	//Function to check if Tree is empty or not  
	public boolean isEmpty() {
		return root == null; //if root is null then it means Tree is empty
	}

	//Just for Testing purpose 
	public void printTree(Node current) {

		if (current == null) return;

		System.out.print(current.getData() + ",");
		printTree(current.getLeftChild());
		printTree(current.getRightChild());

	}
	public static void main(String args[]) {

		binarySearchTree bsT = new binarySearchTree();
		bsT.insert(6);
		bsT.insert(4);
		bsT.insert(8);
		bsT.insert(5);
		bsT.insert(2);
		bsT.insert(8);
		bsT.insert(12);
		bsT.insert(10);
		bsT.insert(14);
		bsT.printTree(bsT.getRoot());

	}
}

تفسیر کد

در کد بالا ، متد insert یک متد بازگشتی است ، زیرا یک فراخوانی بازگشتی ایجاد می کند. در زیر توضیحات کد بالا آورده شده است:

متد main

  • درون متد main، ما یک درخت جستجوی دودویی (BST) جدید ایجاد می کنیم ، به نام bsT.
  • متد ()insert مکرراً برای درج گره ها در BST فراخوانی می شود.
  • متد ()printTree درخت BST را با استفاده از پیمایش پیش ترتیب چاپ می کند. این متد برای شروع پیمایش ریشه را دریافت می کند. این فرآیند فقط BST را به ترتیب چاپ می کند.

متد بازگشتی

  • تابع ()insert یک پارامتر ورودی دارد که مقدار گره جدید است و خروجی این تابع از نوع boolean است. این متد ، متد بازگشتی اصلی recursive_insert را فراخوانی می کند این متد دو پارامتر ورودی دارد. اولین مورد گره فعلی (currentNode) از جنس Node است. مقدار پارامتر دوم ، عددی است که باید در BST وارد شود. در ادامه متد recursive_insert را نیز بررسی خواهیم کرد.

حالت پایه

  • در اولین بلوک شرطی if بین خطوط ۱۹ تا ۲۱ یک حالت پایه برای متد بازگشتی تعریف کرده ایم.
  • اگر مقدار currentNode برابر null باشد ، به این معنی است که فضایی برای قرار دادن گره فرزند جدید وجود دارد در این حالت یک گره جدید (Node) با مقدار داده شده ایجاد می شود.

حالت بازگشتی

  • اگر شرط حالت پایه برآورده نشود و مقداری که باید وارد شود کمتر از مقدار ()currentNode.getData باشد ، این تابع وارد شرط if دوم می شود ، خط ۲۵ ، جایی که یک فراخوانی بازگشتی ایجاد می کند.
  • در این فرایند ، متد recursive_insert بصورت بازگشتی است. اولین پارامتر ()currentNode.getLeftChild است و پارامتر دوم مقداری است که باید وارد شود.
  • اگر شرط حالت پایه برآورده نشود و مقداری که باید وارد شود از مقدار ()currentNode.getData بیشتر باشد ، این تابع وارد else if دوم می شود ، در خط ۲۶-۲۸ ، که در آن ، یک فراخوانی بازگشتی ایجاد می کند.
  • در این else if ، متد recursive_insert فراخوانی می شود. اولین پارامتر ()currentNode.getRightChild است و پارامتر دوم مقداری است که باید وارد شود.
  • اگر تمامی شرایط بالا برآورده نشود ، وارد بلوک else در خطوط ۲۹ تا ۳۱ می شویم که currentNode را برمی گرداند زیرا مقداری که باید وارد درخت شود از قبل در درخت وجود دارد.
  • خط ۳۴ گره currentNode را پس از قرار گرفتن در مکان مناسب درخت ، باز می گرداند.
  • فراخوانی های متوالی بازگشتی به طور مداوم انجام می شوند تا زمانی که پارامتر اول برابر با null باشد ، که نشانه وجود مکان خالی برای گره جدید است. گره جدید سپس در این موقعیت قرار می گیرد.

برای توضیح بهتر متد insert ، به بخش زیر مراجعه کنید.

درک از طریق پشته

در جلسه بعدی ، نحوه عملکرد جستجوی اول عمق یا Depth First Search (DFS) را در گراف ها خواهید آموخت.

نوشته های مشابه

دیدگاهتان را بنویسید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *

دکمه بازگشت به بالا