๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐ŸŽ› Others.../- ์ž๋ฃŒ๊ตฌ์กฐ & ์•Œ๊ณ ๋ฆฌ์ฆ˜

[์ž๋ฃŒ๊ตฌ์กฐ] ๋…ธ๋“œ๋กœ ์ด๋ฃจ์–ด์ง„ ํŠธ๋ฆฌ ๊ตฌํ˜„ํ•˜๊ธฐ (By Java)

by Wonit 2020. 9. 23.

์˜ค๋Š˜์€ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํŠธ๋ฆฌ๋ฅผ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋Œ€ํšŒ๋‚˜ ๋ฌธ์ œ์—์„œ ํ’€๊ธฐ ์‰ฝ๊ฒŒ ํ•œ ๋ฒˆ์— ๊ตฌํ˜„ํ•˜๋Š” ๋ฐฉ๋ฒ•์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณผ ๊ฒƒ์ด๋‹ค.

ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ

ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ๋Š” ์ง€๋‚œ ํŠธ๋ฆฌ ์ž๋ฃŒ ๊ตฌ์กฐ(1)-๊ธฐ๋ณธ ํŠธ๋ฆฌ ์šฉ์–ด ๋ฐ ๊ฐœ๋… ํŒŒํŠธ์—์„œ ์„ค๋ช…ํ–ˆ์œผ๋ฏ€๋กœ ์ƒ๋žตํ•˜๊ณ  ๋ฐ”๋กœ ๊ตฌํ˜„์„ ํ•ด๋ณด๋„๋ก ํ•˜๊ฒ ๋‹ค.

ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์˜ ํ•ต์‹ฌ

ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ์˜ ํ•ต์‹ฌ์€ ๋ฐ”๋กœ ๋…ธ๋“œ์ด๋‹ค.

์—ฌ๊ธฐ์„œ ๋…ธ๋“œ๋ž€ ํŠธ๋ฆฌ ์ž๋ฃŒ๊ตฌ์กฐ์— ๋ฐ์ดํ„ฐ๋ฅผ ์ €์žฅํ•˜๊ณ  ์žˆ๋Š” ํ•˜๋‚˜ ํ•˜๋‚˜์˜ ์›์†Œ์ธ ์…ˆ์ด๋‹ค.

๋…ธ๋“œ๋Š” ํฌ๊ฒŒ Data Field์™€ Link Field๋กœ ๋‚˜๋‰˜์–ด์ ธ ์žˆ๋‹ค.

์ €๊ธฐ ์œ„์—์„œ ๋ณด๋ฉด ๊ฐ๊ฐ์˜ ์ˆซ์ž์— ํ•ด๋‹นํ•˜๋Š” ๋ถ€๋ถ„์ด Data Field์ด๋ฉฐ ์—ฐ๊ฒฐ๋˜์–ด ์žˆ๋Š” ๊ฐ„์„ ์€ Link Field์ด๋‹ค.

๊ทธ๋ ‡๋‹ค๋ฉด ์œ„์—์„œ ๋ง ํ–ˆ๋“ฏ์ด ๋…ธ๋“œ๋Š” Data Field์™€ Link Field๊ฐ€ ํ•ฉ์ณ์ง„ ๊ตฌ์กฐ์ด๋ฏ€๋กœ ์ด๋ฅผ ๊ทธ๋ฆผ์œผ๋กœ ๊ทธ๋ฆฐ๋‹ค๋ฉด ์•„๋ž˜์™€ ๊ฐ™์€ ๊ทธ๋ฆผ์˜ ํ˜•์ƒ์„ ํ•˜๊ณ  ์žˆ์„ ๊ฒƒ์ด๋‹ค.

๊ทธ๋Ÿผ ์œ„์— ์กด์žฌํ•˜๋Š” ํŠธ๋ฆฌ๋ฅผ ๋…ธ๋“œ๋กœ ๋„์‹ํ™” ํ•˜์—ฌ ๋ณด์—ฌ์ค€๋‹ค๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™์€ ํ˜•ํƒœ๊ฐ€ ๋‚˜ํƒ€๋‚˜๊ฒŒ ๋œ๋‹ค.

๋งํฌ ํ•„๋“œ์—์„œ๋Š” ๋‹ค์Œ ๋…ธ๋“œ๋ฅผ ๊ฐ€๋ฆฌํ‚ฌ ์ˆ˜ ์žˆ๋Š” ์ฃผ์†Œ๊ฐ€ ๋‹ด๊ฒจ ์žˆ๋Š” ํ˜•ํƒœ์ด๋‹ค.

์ž๋ฐ”๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ

์ด์ œ ์ž๋ฐ”๋กœ ๊ตฌํ˜„ํ•ด๋ณด์ž.

๊ตฌํ˜„ ๋‹จ๊ณ„๋Š” 2๋‹จ๊ณ„๋กœ

  1. ๋…ธ๋“œ ๊ตฌํ˜„ํ•˜๊ธฐ
  2. ๋…ธ๋“œ ์—ฐ๊ฒฐ๊ด€๊ณ„ ์ถ”๊ฐ€ํ•˜๊ธฐ
class MyNode {
    int data;
    MyNode left;
    MyNode right;
}

class Tree {
    public MyNode root;

    public void setRoot(MyNode node) {
        this.root = root;
    }

    public MyNode getRoot() {
        return root;
    }

    public MyNode addNode(MyNode left, int data, MyNode right){
        MyNode node = new MyNode();
        node.data = data;
        node.left = left;
        node.right = right;

        return node;
    }
}

๋Œ“๊ธ€