نحوه پیمایش درخت دودویی

این درخت پیمایش‌های گوناگونی دارد ولی سه تای آن‌ها اصلی‌تر و مهمتر هستند:

In-order یا LVR (چپ، ریشه، راست): در این حالت ابتدا گره‌های سمت چپ ملاقات (چاپ) می‌شوند و سپس ریشه و بعد گره‌های سمت راست.

Pre-Order یا VLR (ریشه، چپ، راست) : در این حالت ابتدا گره‌های ریشه ملاقات می‌شوند. بعد گره‌های سمت چپ و بعد گره‌های سمت راست.

Post_Order یا LRV (چپ، راست، ریشه ): در این حالت ابتدا گره‌های سمت چپ، بعد راست و نهایتا ریشه، ملاقات می‌شوند.

حتما متوجه شده‌اید که منظور از v در اینجا ریشه است و با تغییر و جابجایی مکان این سه حرف RLV میتوانید به ترکیب‌های مختلفی از پیمایش دست پیدا کنید.

اجازه دهید روی شکل بالا پیمایش LVR را انجام دهیم: همانطور که گفتیم باید اول گره‌های سمت چپ را خواند، پس از 17 به سمت 9 حرکت می‌کنیم و می‌بینیم که 9، خود والد است. پس به سمت 6 حرکت می‌کنیم و می‌بینیم که فرزند چپی ندارد؛ پس خود 6 را ملاقات می‌کنیم، سپس فرزند راست را هم بررسی می‌کنیم که فرزند راستی ندارد پس کار ما اینجا تمام است و به سمت بالا حرکت می‌کنیم. 9 را ملاقات می‌کنیم و بعد عدد 5 را و به 17 بر می‌گردیم. 17 را ملاقات کرده و سپس به سمت 15 می‌رویم و الی آخر ...

6-9-5-17-8-15-10

VLR:

17-9-6-5-15-8-10

LRV:

6-5-9-8-10-15-17

نحوه پیاده سازی درخت دودویی:

public class BinaryTree<T>
{
    /// <summary>مقدار داخل گره</summary>
    public T Value { get; set; }
 
    /// <summary>فرزند چپ گره</summary>
    public BinaryTree<T> LeftChild { get; private set; }
 
    /// <summary>فرزند راست گره</summary>
    public BinaryTree<T> RightChild { get; private set; }
   
    /// <summary>سازنده کلاس</summary>
    /// <param name="value">مقدار گره</param>
    /// <param name="leftChild">فرزند چپ</param>
    /// <param name="rightChild">فرزند راست
    /// </param>
    public BinaryTree(T value,
        BinaryTree<T> leftChild, BinaryTree<T> rightChild)
    {
        this.Value = value;
        this.LeftChild = leftChild;
        this.RightChild = rightChild;
    }
 
    /// <summary>سازنده بدون فرزند
    /// </summary>
    /// <param name="value">the value of the tree node</param>
    public BinaryTree(T value) : this(value, null, null)
    {
    }
 
    /// <summary>‏‏‎LVR پیمایش</summary>
    public void PrintInOrder()
    {
        // ملاقات فرزندان زیر درخت چپ
        if (this.LeftChild != null)
        {
            this.LeftChild.PrintInOrder();
        }
 
        // ملاقات خود ریشه
        Console.Write(this.Value + " ");
 
        // ملاقات فرزندان زیر درخت راست
        if (this.RightChild != null)
        {
            this.RightChild.PrintInOrder();
        }
    }
}
 
/// <summary>
/// نحوه استفاده از کلاس بالا
/// </summary>
public class BinaryTreeExample
{
    static void Main()
    {
        BinaryTree<int> binaryTree =
            new BinaryTree<int>(14,
                    new BinaryTree<int>(19,
                          new BinaryTree<int>(23),
                          new BinaryTree<int>(6,
                                  new BinaryTree<int>(10),
                                  new BinaryTree<int>(21))),
                    new BinaryTree<int>(15,
                          new BinaryTree<int>(3),
                          null));
 
        binaryTree.PrintInOrder();
        Console.WriteLine();
 
        // خروجی
        // 23 19 10 6 21 14 3 15
    }
}

تفاوتی که این کد با کد قبلی که برای یک درخت معمولی داشتیم، در این است که قبلا لیستی از فرزندان را داشتیم که با خاصیت Children شناخته می‌شدند، ولی در اینجا در نهایت دو فرزند چپ و راست برای هر گره وجود دارند. برای جست و جو هم از الگوریتم In_Order استفاده کردیم که از همان الگوریتم DFS آمده‌است. در آنجا هم ابتدا گره‌های سمت چپ به صورت بازگشتی صدا زده می‌شدند. بعد خود گره و سپس گره‌های سمت راست به صورت بازگشتی صدا زده می‌شدند.

برای باقی روش‌های پیمایش تنها نیاز است که این سه خط را جابجا کنید:

  // ملاقات فرزندان زیر درخت چپ
        if (this.LeftChild != null)
        {
            this.LeftChild.PrintInOrder();
        }
 
        // ملاقات خود ریشه
        Console.Write(this.Value + " ");
 
        // ملاقات فرزندان زیر درخت راست
        if (this.RightChild != null)
        {
            this.RightChild.PrintInOrder();
        }

درخت دودویی مرتب شده Ordered Binary Search Tree

تا این لحظه ما با ساخت درخت‌های پایه آشنا شدیم: درخت عادی یا کلاسیک و درخت دو دویی. ولی در بیشتر موارد در پروژه‌های بزرگ از این‌ها استفاده نمی‌کنیم چرا که استفاده از آن‌ها در پروژه‌های بزرگ بسیار مشکل است و باید به جای آن‌ها از ساختارهای متنوع دیگری از قبیل درخت‌های مرتب شده، کم عمق و متوازن و کامل و پر و .. استفاده کرد. پس اجازه دهید که مهمترین درخت‌هایی را که در برنامه نویسی استفاده می‌شوند، بررسی کنیم.

همان طور که می‌دانید برای مقایسه اعداد ما از علامتهای <>= استفاده می‌کنیم و اعداد صحیح بهترین اعداد برای مقایسه هستند. در درخت‌های جست و جوی دو دویی یک خصوصیت اضافه به اسم کلید هویت یکتا Unique identification  Key داریم که یک کلید قابل مقایسه است. در تصویر زیر ما دو گره با مقدارهای متفاوتی داریم که با مقایسه‌ی آنان می‌توانیم کوچک و بزرگ بودن یک گره را محاسبه کنیم. ولی به این نکته دقت داشته باشید که این اعداد داخل دایره‌ها، دیگر برای ما حکم مقدار ندارند و کلید‌های یکتا و شاخص هر گره محسوب می‌شوند.

خلاصه‌ی صحبت‌های بالا: در هر درخت دودویی مرتب شده، گره‌های بزرگتر در زیر درخت راست قرار دارند و گره‌های کوچکتر در زیر درخت چپ قرار دارند که این کوچکی و بزرگی بر اساس یک کلید یکتا که قابل مقایسه است استفاده می‌شود.

این درخت دو دویی مرتب شده در جست و جو به ما کمک فراوانی می‌کند و از آنجا که می‌دانیم زیر درخت‌های چپ مقدار کمتری دارند و زیر درخت‌های راست مقدار بیشتر، عمل جست و جو، مقایسه‌های کمتری خواهد داشت، چرا که هر بار مقایسه یک زیر درخت کنار گذاشته می‌شود.

برای مثال فکر کنید می‌خواهید عدد 13 را در درخت بالا پیدا کنید. ابتدا گره والد 19 را مقایسه کرده و از آنجا که 19 بزرگتر از 13 است می‌دانیم که 13 را در زیر درخت راست پیدا نمی‌کنیم. پس زیر درخت چپ را مقایسه می‌کنیم (بنابراین به راحتی یک زیر درخت از مقایسه و عمل جست و جو کنار گذاشته شد). سپس گره 11 را مقایسه می‌کنیم و از آنجا که 11 کوچکتر از 13 هست، زیر درخت سمت راست را ادامه می‌دهیم و چون 16 بزرگتر از 13 هست، زیر درخت سمت چپ را در ادامه مقایسه می‌کنیم که به 13 رسیدیم.

مقایسه گره‌هایی که برای جست و جو انجام دادیم:

19-11-16-13

درخت هر چه بزرگتر باشد این روش کارآیی خود را بیشتر نشان می‌دهد.

import { InjectionToken } from "@angular/core";

export let APP_CONFIG = new InjectionToken<string>("app.config");

export interface IAppConfig {
  apiEndpoint: string;
  loginPath: string;
  logoutPath: string;
  refreshTokenPath: string;
  accessTokenObjectKey: string;
  refreshTokenObjectKey: string;
}

export const AppConfig: IAppConfig = {
  apiEndpoint: "http://localhost:5000/api",
  loginPath: "account/login",
  logoutPath: "account/logout",
  refreshTokenPath: "account/RefreshToken",
  accessTokenObjectKey: "access_token",
  refreshTokenObjectKey: "refresh_token"
};

import { AppConfig, APP_CONFIG } from "./app.config";

@NgModule({
  providers: [
    { provide: APP_CONFIG, useValue: AppConfig }
  ]
})
export class CoreModule {}

 ng g s Core/services/Auth

   create src/app/Core/services/auth.service.ts (110 bytes)

import { AuthService } from "./services/auth.service";

@NgModule({
  providers: [
    // global singleton services of the whole app will be listed here.
    BrowserStorageService,
    AuthService,
    { provide: APP_CONFIG, useValue: AppConfig }
  ]
})
export class CoreModule {}

import { BehaviorSubject } from "rxjs/BehaviorSubject";

@Injectable()
export class AuthService {

  private authStatusSource = new BehaviorSubject<boolean>(false);
  authStatus$ = this.authStatusSource.asObservable();

  constructor() {
    this.updateStatusOnPageRefresh();
  }

  private updateStatusOnPageRefresh(): void {
    this.authStatusSource.next(this.isLoggedIn());
  }

export enum AuthTokenType {
   AccessToken,
   RefreshToken
}

import { BrowserStorageService } from "./browser-storage.service";

export enum AuthTokenType {
  AccessToken,
  RefreshToken
}

@Injectable()
export class AuthService {

  private rememberMeToken = "rememberMe_token";

  constructor(private browserStorageService: BrowserStorageService) {  }

  rememberMe(): boolean {
    return this.browserStorageService.getLocal(this.rememberMeToken) === true;
  }

  getRawAuthToken(tokenType: AuthTokenType): string {
    if (this.rememberMe()) {
      return this.browserStorageService.getLocal(AuthTokenType[tokenType]);
    } else {
      return this.browserStorageService.getSession(AuthTokenType[tokenType]);
    }
  }

  deleteAuthTokens() {
    if (this.rememberMe()) {
      this.browserStorageService.removeLocal(AuthTokenType[AuthTokenType.AccessToken]);
      this.browserStorageService.removeLocal(AuthTokenType[AuthTokenType.RefreshToken]);
    } else {
      this.browserStorageService.removeSession(AuthTokenType[AuthTokenType.AccessToken]);
      this.browserStorageService.removeSession(AuthTokenType[AuthTokenType.RefreshToken]);
    }
    this.browserStorageService.removeLocal(this.rememberMeToken);
  }

  private setLoginSession(response: any): void {
    this.setToken(AuthTokenType.AccessToken, response[this.appConfig.accessTokenObjectKey]);
    this.setToken(AuthTokenType.RefreshToken, response[this.appConfig.refreshTokenObjectKey]);
  }

  private setToken(tokenType: AuthTokenType, tokenValue: string): void {
    if (this.rememberMe()) {
      this.browserStorageService.setLocal(AuthTokenType[tokenType], tokenValue);
    } else {
      this.browserStorageService.setSession(AuthTokenType[tokenType], tokenValue);
    }
  }
}

 {"access_token":"...","refresh_token":"..."}

export interface Credentials {
   username: string;
   password: string;
   rememberMe: boolean;
}

@Injectable()
export class AuthService {
  constructor(
    @Inject(APP_CONFIG) private appConfig: IAppConfig,
    private http: HttpClient,
    private browserStorageService: BrowserStorageService   
  ) {
    this.updateStatusOnPageRefresh();
  }

  login(credentials: Credentials): Observable<boolean> {
    const headers = new HttpHeaders({ "Content-Type": "application/json" });
    return this.http
      .post(`${this.appConfig.apiEndpoint}/${this.appConfig.loginPath}`, credentials, { headers: headers })
      .map((response: any) => {
        this.browserStorageService.setLocal(this.rememberMeToken, credentials.rememberMe);
        if (!response) {
          this.authStatusSource.next(false);
          return false;
        }
        this.setLoginSession(response);
        this.authStatusSource.next(true);
        return true;
      })
      .catch((error: HttpErrorResponse) => Observable.throw(error));
  }
}

@Injectable()
export class AuthService {

  constructor(
    @Inject(APP_CONFIG) private appConfig: IAppConfig,
    private http: HttpClient,
    private router: Router
  ) {
    this.updateStatusOnPageRefresh();
  }

  logout(navigateToHome: boolean): void {
    this.http
      .get(`${this.appConfig.apiEndpoint}/${this.appConfig.logoutPath}`)
      .finally(() => {
        this.deleteAuthTokens();
        this.unscheduleRefreshToken();
        this.authStatusSource.next(false);
        if (navigateToHome) {
          this.router.navigate(["/"]);
        }
      })
      .map(response => response || {})
      .catch((error: HttpErrorResponse) => Observable.throw(error))
      .subscribe(result => {
        console.log("logout", result);
      });
  }
}

 > npm install jwt-decode --save

 import * as jwt_decode from "jwt-decode";

  getDecodedAccessToken(): any {
    return jwt_decode(this.getRawAuthToken(AuthTokenType.AccessToken));
  }

{
  "jti": "d1272eb5-1061-45bd-9209-3ccbc6ddcf0a",
  "iss": "http://localhost/",
  "iat": 1513070340,
  "http://schemas.xmlsoap.org/ws/2005/05/identity/claims/nameidentifier": "1",
  "http://schemas.xmlsoap.org/ws/2005/05/identity/claims/name": "Vahid",
  "DisplayName": "وحید",
  "http://schemas.microsoft.com/ws/2008/06/identity/claims/serialnumber": "709b64868a1d4d108ee58369f5c3c1f3",
  "http://schemas.microsoft.com/ws/2008/06/identity/claims/userdata": "1",
  "http://schemas.microsoft.com/ws/2008/06/identity/claims/role": [
    "Admin",
    "User"
  ],
  "nbf": 1513070340,
  "exp": 1513070460,
  "aud": "Any"
}

  getDisplayName(): string {
    return this.getDecodedAccessToken().DisplayName;
  }

  getAccessTokenExpirationDateUtc(): Date {
    const decoded = this.getDecodedAccessToken();
    if (decoded.exp === undefined) {
      return null;
    }
    const date = new Date(0); // The 0 sets the date to the epoch
    date.setUTCSeconds(decoded.exp);
    return date;
  }

  isAccessTokenTokenExpired(): boolean {
    const expirationDateUtc = this.getAccessTokenExpirationDateUtc();
    if (!expirationDateUtc) {
      return true;
    }
    return !(expirationDateUtc.valueOf() > new Date().valueOf());
  }

  isLoggedIn(): boolean {
    const accessToken = this.getRawAuthToken(AuthTokenType.AccessToken);
    const refreshToken = this.getRawAuthToken(AuthTokenType.RefreshToken);
    const hasTokens = !this.isEmptyString(accessToken) && !this.isEmptyString(refreshToken);
    return hasTokens && !this.isAccessTokenTokenExpired();
  }

  private isEmptyString(value: string): boolean {
    return !value || 0 === value.length;
  }

در شکل بالا دایره‌هایی برای هر بخش از اطلاعت کشیده شده و ارتباط هر کدام از آن‌ها از طریق یک خط برقرار شده است. اعداد داخل هر دایره تکراری نیست و همه منحصر به فرد هستند. پس وقتی از اعداد اسم ببریم متوجه می‌شویم که در مورد چه چیزی صحبت می‌کنیم.

در شکل بالا به هر یک از دایره‌ها یک گره Node می‌گویند و به هر خط ارتباط دهنده بین گره‌ها لبه Edge گفته می‌شود. گره‌های 19 و 21 و 14 زیر گره‌های گره 7 محسوب می‌شوند. گره‌هایی که به صورت مستقیم به زیر گره‌های خودشان اشاره می‌کنند را گره‌های والد Parent می‌گویند و زیرگره‌های 7 را گره‌های فرزند ChildNodes. پس با این حساب می‌توانیم بگوییم گره‌های 1 و 12 و 31 را هم فرزند گره 19 هستند و گره 19 والد آن هاست. همچنین گره‌های یک والد را مثل 19 و 21 و 14 که والد مشترک دارند، گره‌های خواهر و برادر یا حتی همنژاد Sibling می‌گوییم. همچنین ارتباط بین گره 7 و گره‌های سطح دوم  و الی آخر یعنی 1 و 12 و 31 و 23 و 6 را که والد بودن آن به صورت غیر مستقیم است را جد یا ancestor می‌نامیم و نوه‌ها و نتیجه‌های آن‌ها را نسل descendants.

ریشه Root: به گره‌ای می‌گوییم که هیچ والدی ندارد و خودش در واقع اولین والد محسوب می‌شود؛ مثل گره 7.

برگ  Leaf: به گره‌هایی که هیچ فرزندی ندارند، برگ می‌گوییم. مثال گره‌های 1 و12 و 31 و 23 و 6

گره‌های داخلی Internal Nodes: گره هایی که نه برگ هستند و نه ریشه. یعنی حداقل یک فرزند دارند و خودشان یک گره فرزند محسوب می‌شوند؛ مثل گره‌های 19 و 14.

مسیر Path: راه رسیدن از یک گره به گره دیگر را مسیر می‌گویند. مثلا گره‌های 1 و 19 و 7 و 21 به ترتیب یک مسیر را تشکیل می‌دهند ولی گره‌های 1 و 19 و 23 از آن جا که هیچ جور اتصالی بین آن‌ها نیست، مسیری را تشکیل نمی‌دهند.

طول مسیر Length of Path: به تعداد لبه‌های یک مسیر، طول مسیر می‌گویند که می‌توان از تعداد گره‌ها -1 نیز آن را به دست آورد. برای نمونه : مسیر 1 و19 و 7 و 21 طول مسیرشان 3 هست.

عمق Depth: طول مسیر یک گره از ریشه تا آن گره را عمق درخت می‌گویند. عمق یک ریشه همیشه صفر است و برای مثال در درخت بالا، گره 19 در عمق یک است و برای گره 23 عمق آن 2 خواهد بود.

تعریف خود درخت Tree: درخت یک ساختار داده برگشتی recursive است که شامل گره‌ها و لبه‌ها، برای اتصال گره‌ها به یکدیگر است.

جملات زیر در مورد درخت صدق می‌کند:

• هر گره می‌تواند فرزند نداشته باشد یا به هر تعداد که می‌خواهد فرزند داشته باشد.
• هر گره یک والد دارد و تنها گره‌ای که والد ندارد، گره ریشه است (البته اگر درخت خالی باشد هیچ گره ای وجود ندارد).
• همه گره‌ها از ریشه قابل دسترسی هستند و برای دسترسی به گره مورد نظر باید از ریشه تا آن گره، مسیری را طی کرد.

برای پیاده سازی یک درخت، از دو کلاس یکی جهت ساخت گره که حاوی اطلاعات است <TreeNode<T و دیگری جهت ایجاد درخت اصلی به همراه کلیه متدها و خاصیت هایش <Tree<T کمک می‌‌گیریم.

public class TreeNode<T>
{
    // شامل مقدار گره است
    private T value;
 
    // مشخص می‌کند که آیا گره والد دارد یا خیر
    private bool hasParent;
 
    // در صورت داشتن فرزند ، لیست فرزندان را شامل می‌شود
    private List<TreeNode<T>> children;
 
    /// <summary>سازنده کلاس </summary>
    /// <param name="value">مقدار گره</param>
    public TreeNode(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null value!");
        }
        this.value = value;
        this.children = new List<TreeNode<T>>();
    }
 
    /// <summary>خاصیتی جهت مقداردهی گره</summary>
    public T Value
    {
        get
        {
            return this.value;
        }
        set
        {
            this.value = value;
        }
    }
 
    /// <summary>تعداد گره‌های فرزند را بر میگرداند</summary>
    public int ChildrenCount
    {
        get
        {
            return this.children.Count;
        }
    }
 
    /// <summary>به گره یک فرزند اضافه می‌کند</summary>
    /// <param name="child">آرگومان این متد یک گره است که قرار است به فرزندی گره فعلی در آید</param>
    public void AddChild(TreeNode<T> child)
    {
        if (child == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null value!");
        }
 
        if (child.hasParent)
        {
            throw new ArgumentException(
                "The node already has a parent!");
        }
 
        child.hasParent = true;
        this.children.Add(child);
    }
 
    /// <summary>
    /// گره ای که اندیس آن داده شده است بازگردانده می‌شود
    /// </summary>
    /// <param name="index">اندیس گره</param>
    /// <returns>گره بازگشتی</returns>
    public TreeNode<T> GetChild(int index)
    {
        return this.children[index];
    }
}
 
/// <summary>این کلاس ساختار درخت را به کمک کلاس گره‌ها که در بالا تعریف کردیم میسازد</summary>
/// <typeparam name="T">نوع مقادیری که قرار است داخل درخت ذخیره شوند</typeparam>
public class Tree<T>
{
    // گره ریشه
    private TreeNode<T> root;
 
    /// <summary>سازنده کلاس</summary>
    /// <param name="value">مقدار گره اول که همان ریشه می‌شود</param>
    public Tree(T value)
    {
        if (value == null)
        {
            throw new ArgumentNullException(
                "Cannot insert null value!");
        }
 
        this.root = new TreeNode<T>(value);
    }
 
    /// <summary>سازنده دیگر برای کلاس درخت</summary>
    /// <param name="value">مقدار گره ریشه مثل سازنده اول</param>
    /// <param name="children">آرایه ای از گره‌ها که فرزند گره ریشه می‌شوند</param>
    public Tree(T value, params Tree<T>[] children)
        : this(value)
    {
        foreach (Tree<T> child in children)
        {
            this.root.AddChild(child.root);
        }
    }
 
    /// <summary>
    /// ریشه را بر میگرداند ، اگر ریشه ای نباشد نال بر میگرداند
    /// </summary>
    public TreeNode<T> Root
    {
        get
        {
            return this.root;
        }
    }
 
    /// <summary>پیمودن عرضی و نمایش درخت با الگوریتم دی اف اس </summary>
    /// <param name="root">ریشه (گره ابتدایی) درختی که قرار است پیمایش از آن شروع شود</param>
    /// <param name="spaces">یک کاراکتر جهت جداسازی مقادیر هر گره</param>
    private void PrintDFS(TreeNode<T> root, string spaces)
    {
        if (this.root == null)
        {
            return;
        }
 
        Console.WriteLine(spaces + root.Value);
 
        TreeNode<T> child = null;
        for (int i = 0; i < root.ChildrenCount; i++)
        {
            child = root.GetChild(i);
            PrintDFS(child, spaces + "   ");
        }
    }
 
    /// <summary>متد پیمایش درخت به صورت عمومی که تابع خصوصی که در بالا توضیح دادیم را صدا می‌زند</summary>
    public void TraverseDFS()
    {
        this.PrintDFS(this.root, string.Empty);
    }
}
 
/// <summary>
/// کد استفاده از ساختار درخت
/// </summary>
public static class TreeExample
{
    static void Main()
    {
        // Create the tree from the sample
        Tree<int> tree =
            new Tree<int>(7,
                new Tree<int>(19,
                    new Tree<int>(1),
                    new Tree<int>(12),
                    new Tree<int>(31)),
                new Tree<int>(21),
                new Tree<int>(14,
                    new Tree<int>(23),
                    new Tree<int>(6))
            );
 
        // پیمایش درخت با الگوریتم دی اف اس یا عمقی
        tree.TraverseDFS();
 
        // خروجی
        // 7
        //       19
        //        1
        //        12
        //        31
        //       21
        //       14
        //        23
        //        6
    }
}

پیمایش درخت به روش عمقی (DFS (Depth First Search

هدف از پیمایش درخت ملاقات یا بازبینی (تهیه لیستی از همه گره‌های یک درخت) تنها یکبار هر گره در درخت است. برای این کار الگوریتم‌های زیادی وجود دارند که ما در این مقاله تنها دو روش DFS و BFS را بررسی می‌کنیم.

روش DFS: هر گره‌ای که به تابع بالا بدهید، آن گره برای پیمایش، گره ریشه حساب خواهد شد و پیمایش از آن آغاز می‌گردد. در الگوریتم DFS روش پیمایش بدین گونه است که ما از گره ریشه آغاز کرده و گره ریشه را ملاقات می‌کنیم. سپس گره‌های فرزندش را به دست می‌آوریم و یکی از گره‌ها را انتخاب کرده و دوباره همین مورد را رویش انجام می‌دهیم تا نهایتا به یک برگ برسیم. وقتی که به برگی می‌رسیم یک مرحله به بالا برگشته و این کار را آنقدر تکرار می‌کنیم تا همه‌ی گره‌های آن ریشه یا درخت پیمایش شده باشند.

همین درخت را در نظر بگیرید:

 پیمایش درخت را از گره 7 آغاز می‌کنیم و آن را به عنوان ریشه در نظر می‌گیریم. حتی می‌توانیم پیمایش را از گره مثلا 19 آغاز کنیم و آن را برای پیمایش ریشه در نظر بگیریم ولی ما از همان 7 پیمایش را آغاز می‌کنیم:

ابتدا گره 7 ملاقات شده و آن را می‌نویسیم. سپس فرزندانش را بررسی می‌کنیم که سه فرزند دارد. یکی از فرزندان مثل گره 19 را انتخاب کرده و آن را ملاقات می‌کنیم (با هر بار ملاقات آن را چاپ می‌کنیم) سپس فرزندان آن را بررسی می‌کنیم و یکی از گره‌ها را انتخاب می‌کنیم و ملاقاتش می‌کنیم؛ برای مثال گره 1. از آن جا که گره یک، برگ است و فرزندی ندارد یک مرحله به سمت بالا برمی‌گردیم و برگ‌های 12 و 31 را هم ملاقات می‌کنیم. حالا همه‌ی فرزندان گره 19 را بررسی کردیم، بر می‌گردیم یک مرحله به سمت بالا و گره 21 را ملاقات می‌کنیم و از آنجا که گره 21 برگ است و فرزندی ندارد به بالا باز می‌گردیم و بعد گره 14 و فرزندانش 23 و 6 هم بررسی می‌شوند. پس ترتیب چاپ ما اینگونه می‌شود:

7-19-1-12-31-21-14-23-6

پیمایش درخت به روش (BFS (Breadth First Search 

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

7-19-21-14-1-12-31-23-6

اگر خوب دقت کنید می‌بینید که پیمایش سطحی است و هر سطح به ترتیب ملاقات می‌شود. به این الگوریتم، پیمایش موجی هم می‌گویند. دلیل آن هم این است که مثل سنگی می‌ماند که شما برای ایجاد موج روی دریاچه پرتاب می‌کنید.

برای این پیمایش از صف کمک گرفته می‌شود که مراحل زیر روی صف صورت می‌گیرد:

• ریشه  وارد صف Q می‌شود.
• دو مرحله زیر مرتبا تکرار می‌شوند:

1. اولین گره صف به نام V را از Q در یافت می‌کنیم و آن را چاپ می‌کنیم.
2. فرزندان گره V  را به صف اضافه می‌کنیم.

<a id="@item.Id" class="detail" data-toggle="modal" data-target=".bs-example-modal-lg" href="#">جزئیات</a>

<div class="modal fade bs-example-modal-lg" tabindex="-1" role="dialog" aria-labelledby="myLargeModalLabel" aria-hidden="true">
    <div class="modal-dialog">
        <div class="modal-content">
            // نتیجه اطلاعات
        </div><!-- /.modal-content -->
    </div><!-- /.modal-dialog -->
</div><!-- /.modal -->

<script type="text/javascript">
        $(function() {
            $('.detail').click(function () {
                var selectedId = $(this).attr('id');
                // نتیجه اکشن متد زیر یک پارشال ویو است
                $.post('@Url.Action("GetRequestById")' + "/" + selectedId, function (data) {
                    $('.modal-content').html(data);
                });
            });
        });
</script>

#region Nivo Slider

   bundles.Add(new StyleBundle("~/Content/NivoSlider").Include("~/Content/nivoSlider/nivo-slider.css"));
   bundles.Add(new StyleBundle("~/Content/NivoSliderDefaultTheme").Include("~/Content/nivoSlider/themes/default/default.css"));
   bundles.Add(new StyleBundle("~/Content/NivoSliderDarkTheme").Include("~/Content/nivoSlider/themes/dark/dark.css"));
   bundles.Add(new StyleBundle("~/Content/NivoSliderLightTheme").Include("~/Content/nivoSlider/themes/light/light.css"));
   bundles.Add(new StyleBundle("~/Content/NivoSliderBarTheme").Include("~/Content/nivoSlider/themes/bar/bar.css"));
   bundles.Add(new ScriptBundle("~/bundles/NivoSlider").Include("~/Scripts/jquery.nivo.slider.pack.js"));

#endregion

<!DOCTYPE html>
<html>
<head>
    <title>@ViewBag.Title</title>
    <script type="text/javascript" src="~/Scripts/jquery-1.9.1.min.js"></script>
    @Styles.Render("~/Content/NivoSlider", "~/Content/NivoSliderDefaultTheme","~/Content/NivoSliderLightTheme")
    @Scripts.Render("~/bundles/NivoSlider")
</head>
<body>
    @RenderBody()
    @RenderSection("scripts", required: false)
</body>
</html>

 public class NivoSliderHelper 
 {
        #region Fields

        private string _id = "nivo1";
        private List<NivoSliderItem> _models = null;
        private string _width = "100%";
        private NivoSliderTheme _theme = NivoSliderTheme.Default;
        private string _effect = "random"; // Specify sets like= 'fold;fade;sliceDown'
        private int _slices = 15; // For slice animations
        private int _boxCols = 8; // For box animations
        private int _boxRows = 4; // For box animations
        private int _animSpeed = 500; // Slide transition speed
        private int _pauseTime = 3000; // How long each slide will show
        private int _startSlide = 0; // Set starting Slide (0 index)
        private bool _directionNav = true; // Next & Prev navigation
        private bool _controlNav = true; // 1;2;3... navigation
        private bool _controlNavThumbs = false; // Use thumbnails for Control Nav
        private bool _pauseOnHover = true; // Stop animation while hovering
        private bool _manualAdvance = false; // Force manual transitions
        private string _prevText = "Prev"; // Prev directionNav text
        private string _nextText = "Next"; // Next directionNav text
        private bool _randomStart = false; // Start on a random slide
        private string _beforeChange = ""; // Triggers before a slide transition
        private string _afterChange = ""; // Triggers after a slide transition
        private string _slideshowEnd = ""; // Triggers after all slides have been shown
        private string _lastSlide = ""; // Triggers when last slide is shown
        private string _afterLoad = "";

        #endregion

        string makeParameters()
        {
            var builder = new StringBuilder();
            builder.Append("{");
            builder.Append(string.Format("effect:'{0}'", _effect));
            builder.AppendLine(string.Format(",slices:{0}", _slices));
            builder.AppendLine(string.Format(",boxCols:{0}", _boxCols));
            builder.AppendLine(string.Format(",boxRows:{0}", _boxRows));
            builder.AppendLine(string.Format(",animSpeed:{0}", _animSpeed));
            builder.AppendLine(string.Format(",pauseTime:{0}", _pauseTime));
            builder.AppendLine(string.Format(",startSlide:{0}", _startSlide));
            builder.AppendLine(string.Format(",directionNav:{0}", _directionNav.ToString().ToLower()));
            builder.AppendLine(string.Format(",controlNav:{0}", _controlNav.ToString().ToLower()));
            builder.AppendLine(string.Format(",controlNavThumbs:{0}", _controlNavThumbs.ToString().ToLower()));
            builder.AppendLine(string.Format(",pauseOnHover:{0}", _pauseOnHover.ToString().ToLower()));
            builder.AppendLine(string.Format(",manualAdvance:{0}", _manualAdvance.ToString().ToLower()));
            builder.AppendLine(string.Format(",prevText:'{0}'", _prevText));
            builder.AppendLine(string.Format(",nextText:'{0}'", _nextText));
            builder.AppendLine(string.Format(",randomStart:{0}", _randomStart.ToString().ToLower()));
            builder.AppendLine(string.Format(",beforeChange:{0}", _beforeChange));
            builder.AppendLine(string.Format(",afterChange:{0}", _afterChange));
            builder.AppendLine(string.Format(",slideshowEnd:{0}", _slideshowEnd));
            builder.AppendLine(string.Format(",lastSlide:{0}", _lastSlide));
            builder.AppendLine(string.Format(",afterLoad:{0}", _afterLoad));
            builder.Append("}");
            return builder.ToString();
        }
        public NivoSliderHelper (
            string id, 
            List<NivoSliderItem> models,
            string width = "100%", 
            NivoSliderTheme theme = NivoSliderTheme.Default,
            string effect = "random", 
            int slices = 15, 
            int boxCols = 8, 
            int boxRows = 4,
            int animSpeed = 500, 
            int pauseTime = 3000, 
            int startSlide = 0,
            bool directionNav = true, 
            bool controlNav = true,
            bool controlNavThumbs = false, 
            bool pauseOnHover = true, 
            bool manualAdvance = false,
            string prevText = "Prev",
            string nextText = "Next", 
            bool randomStart = false,
            string beforeChange = "function(){}", 
            string afterChange = "function(){}",
            string slideshowEnd = "function(){}", 
            string lastSlide = "function(){}", 
            string afterLoad = "function(){}")
        {
            _id = id;
            _models = models;
            _width = width;
            _theme = theme;
            _effect = effect;
            _slices = slices;
            _boxCols = boxCols;
            _boxRows = boxRows;
            _animSpeed = animSpeed;
            _pauseTime = pauseTime;
            _startSlide = startSlide;
            _directionNav = directionNav;
            _controlNav = controlNav;
            _controlNavThumbs = controlNavThumbs;
            _pauseOnHover = pauseOnHover;
            _manualAdvance = manualAdvance;
            _prevText = prevText;
            _nextText = nextText;
            _randomStart = randomStart;
            _beforeChange = beforeChange;
            _afterChange = afterChange;
            _slideshowEnd = slideshowEnd;
            _lastSlide = lastSlide;
            _afterLoad = afterLoad;
        }
        public IHtmlString GetHtml()
        {
            var thm = "theme-" + _theme.ToString().ToLower();
            var sb = new StringBuilder();
            sb.AppendLine("<div style='width:" + _width + ";height:auto;margin:0px auto' class='" + thm + "'>");
            sb.AppendLine("<div id='" + _id + "' class='nivoSlider'>");
            foreach (var model in _models)
            {
                string img = string.Format("<img src='{0}' alt='{1}' title='{2}' />", model.ImageFilePath, "", model.Caption);
                string item = "";
                if (model.LinkUrl.Trim().Length > 0 &&
                    Uri.IsWellFormedUriString(model.LinkUrl, UriKind.RelativeOrAbsolute))
                {
                    item = string.Format("<a href='{0}'>{1}</a>", model.LinkUrl, img);
                }
                else
                {
                    item = img;
                }
                sb.AppendLine(item);
            }
            sb.AppendLine("</div>");
            sb.AppendLine("</div>");

            sb.AppendLine("<script type='text/javascript'>");
            //sb.AppendLine("$('#" + _id + "').parent().ready(function () {");
            sb.Append("$(document).ready(function(){");
            sb.AppendLine("$('#" + _id + "').nivoSlider(" + makeParameters() + ");");
            //sb.AppendLine("$('.nivo-controlNav a').empty();");//semi hack for rtl layout
            //sb.AppendLine("$('#" + _id + "').nivoSlider();");
            sb.AppendLine("});");
            sb.AppendLine("</script>");

            return new HtmlString(sb.ToString());
        }
    }

    public enum NivoSliderTheme
    {
        Default, Light, Dark, Bar,
    }

    public class NivoSliderItem
    {
        public string ImageFilePath { get; set; }
        public string Caption { get; set; }
        public string LinkUrl { get; set; }
    }

 public class HomeController : Controller
    {
        public ActionResult Index()
        {
            return View();
        }
        public virtual ActionResult NivoSlider()
        {
            var models = new List<NivoSliderItem>
            {
                new NivoSliderItem()
                    {
                        ImageFilePath =Url.Content("~/Images/img1.jpg"),
                        Caption = "عنوان اول",
                        LinkUrl = "http://www.google.com",
                    },
                new NivoSliderItem()
                    {
                        ImageFilePath =Url.Content("~/Images/img2.jpg"),
                        Caption = "#htmlcaption",
                        LinkUrl = "",
                    },
                new NivoSliderItem()
                    {
                        ImageFilePath =Url.Content("~/Images/img3.jpg"),
                        Caption = "عنوان سوم",
                        LinkUrl = "",
                    },
                new NivoSliderItem()
                    {
                        ImageFilePath =Url.Content("~/Images/img4.jpg"),
                        Caption = "عنوان چهارم",
                        LinkUrl = "",
                    },
                new NivoSliderItem()
                    {
                        ImageFilePath =Url.Content("~/Images/img5.jpg"),
                        Caption = "عنوان پنجم",
                        LinkUrl = "",
                    }
            };
            return PartialView("_NivoSlider", models);
        }
    }

import { BrowserModule } from '@angular/platform-browser';
import { NgModule } from '@angular/core';

import { AppComponent } from './app.component';
import { HttpClientModule } from "@angular/common/http";
import { ApolloModule, APOLLO_OPTIONS } from "apollo-angular";
import { HttpLinkModule, HttpLink } from "apollo-angular-link-http";
import { InMemoryCache } from "apollo-cache-inmemory";


@NgModule({
  declarations:
    [
      AppComponent
    ],
  imports:
    [
      BrowserModule,
      HttpClientModule,
      ApolloModule,
      HttpLinkModule
    ],
  providers:
    [
      {
        provide: APOLLO_OPTIONS,
        useFactory: (httpLink: HttpLink) => {
          return {
            cache: new InMemoryCache(),
            link: httpLink.create({
              uri: "https://localhost:5001/graphql"
            })
          }
        },
        deps:
          [
            HttpLink
          ]
      }],
  bootstrap:
    [
      AppComponent
    ]
})
export class AppModule { }