# 数据结构

## 1、哈希表

哈希表也叫散列函数，它对不同的输入值得到一个固定长度的消息摘要。理想的哈希函数对于不同的输入应该产生不同的结果，同时散列结果应当具有同一性和雪崩效应。

在js中，object属性的实现就是hash表，因此只要在object上简单封装方法，就可以使用object管理实现高效的hashtable了。

```
    class HashTable  {
        constructor() {
            this.hashTable = new Object();
            this.size = 0;
        }

        _hasKey(key) { // private fucntion
            return (key in this.hashTable);
        }

        add(key, value) {
            if(!this._hasKey(key)) {
                this.hashTable[key] = value;
                this.size++;
            }
        }

        remove(key) {
            if(this._hasKey) {
                delete this.hashTable[key];
                this.size--;
            }
        }

        getValue(key) {
            if(this._hasKey(key)) {
                return this.hashTable[key];
            }
            return null;
        }

        getSize() {
            return this.size;
        }

        clear() {
            this.hashTable = new Object();
            this.size = 0;
        }
    }
```

## 2、队列

队列是FIFO的有序集合，新增加的元素放在队尾，要移除的元素在队列的顶部。

```
        class Queue {
            constructor() {
                this.queue = [];
            }

            enqueue(item) { // 添加元素
                if (typeof item != 'undefined') {
                    this.queue.push(item);
                }
            }

            dequeue() { // 移除队顶元素
                if (this.queue.length > 0) {
                    return this.queue.shift();
                }
                return undefined;
            }

            front() { // 获取队顶元素，不移除
                if (this.queue.size > 0) {
                    return this.queue[0];
                }
                return undefined;
            }

            isEmpty() { // 判断队列是否为空
                if (this.queue.size > 0) {
                    return false;
                }
                return true;
            }

            getLength() { // 获取队列长度
                let length = this.queue.length;
                return length;
            }

            clear() { // 清空队列
                this.queue = [];
            }

            print() { // 用于打印观察队列的情况
                this.queue.forEach((item, index) => {
                    console.log(`${index} = ${item}`);
                })
            }
        }
```

## 3、栈

栈是LIFO的有序集合，只在表尾进行删除和插入的操作。

```
        class Stack {
            constructor() {
                this.stack = [];
            }

            push(item) { // 入栈
                this.stack.push(item);
            }

            pop() { // 出栈
                return this.stack.pop();
            }

            peak() { // 返回栈顶元素
                if (this.stack.length > 0) {
                    return this.stack[this.stack.length - 1];
                }
                return undefined;
            }

            clear() { // 清空栈内所有元素
                this.stack = [];
            }

            isEmpty() { // 判断是否为空
                return !(this.stack.length > 0);
            }

            print() { // 用于打印观察栈的情况
                this.stack.forEach((item, index) => {
                    console.log(`${index} = ${item}`);
                })
            }
        }
```

## 4、链表

链表是由一组节点组成的集合，每个节点都使用一个对象的索引来指向它后一个节点。指向另一个节点的引用叫做链。

```
        class Node {
            constructor(element) {
                this.element = element; // 当前节点的元素
                this.next = null; // 指向下一个节点
            }
        }

        class LList {
            constructor(element) {
                let node = new Node(element);
                this.headNode = node; // 头结点
            }

            insert(newElement, element) { // 插入节点
                let preNode = this.find(element);
                if (preNode) {
                    let node = new Node(newElement);
                    node.next = preNode.next;
                    preNode.next = node;
                }
            }

            remove(element) { // 删除节点，注意headNode的指向
                if(this.headNode.element == element) {
                    this.headNode = this.headNode.next;
                    return true;
                }
                let preNode = this.findPrev(element);
                if (preNode) {
                    preNode.next = preNode.next.next;
                }
            }

            find(element) { // 查找节点
                let currentNode = this.headNode;
                while (currentNode != null && currentNode.element != element) {
                    currentNode = currentNode.next;
                }
                return currentNode;
            }

            findPrev(element) { // 查找前一个节点
                let preNode = null, currentNode = this.headNode;
                while (currentNode != null && currentNode.element != element) {
                    preNode = currentNode;
                    currentNode = currentNode.next;
                }
                if (currentNode == null) {
                    return null;
                }
                return preNode;
            }
        }
```

## 5、双向链表

虽然从链表的头结点遍历链表很简单，但是反过来，从后向前遍历就很难。为了使从后向前的遍历变得简单，我们给Dnode类增加一个previous属性，指向前一个元素，这就是双向链表。

```
        class Dnode {
            constructor(element) {
                this.element = element;
                this.next = null;
                this.previous = null;
            }
        }

        class DlList {
            constructor(element) {
                let headNode = new Dnode(element);
                this.headNode = headNode;
            }

            insert(newElement, element) { // 插入节点
                let preNode = this.find(element);
                if (preNode) {
                    let node = new Dnode(newElement);
                    node.previous = preNode;
                    node.next = preNode.next;
                    preNode.next = node;
                    node.next && (node.next.previous = node);
                }
            }

            remove(element) { // 删除节点,注意headNode的指向
                let currentNode = this.find(element);
                if(this.headNode.element == element) {
                    this.headNode = this.headNode.next;
                }
                currentNode.previous && (currentNode.previous.next = currentNode.next);
                currentNode.next && (currentNode.next.previous = currentNode.previous);
            }

            find(element) { // 查找节点
                let currentNode = this.headNode;
                while (currentNode != null && currentNode.element != element) {
                    currentNode = currentNode.next;
                }
                return currentNode;
            }
        }
```

## 6、二叉树和平衡二叉树

二叉树是一种树型结构，它的特点是每个结点至多只有两个子树，并且，二叉树有左右之分，次序不能随意颠倒。

> 二叉树的性质：

```
（一）在二叉树的第i（i>=1）层至多有2^(i-1)个结点。
（二）深度为k（k>=1）的二叉树至多有2^K-1个结点。
（三）对于任何一颗二叉树T，如果其终端结点为n0,度为2的结点数为n2,则n0=n2+1。
      满二叉树是深度为k且有2^k-1个结点的二叉树。
      完全二叉树：深度为k的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时的二叉树。
（四）一个具有n个结点的完全二叉树的深度为Math.floor(log2 n)+1。
（五）如果对一颗有n个结点的完全二叉树（其深度为Math.floor(log2 n)+1）的结点按层编号，则对任一结点（1<=i<=n）有：
     a.如果i=1，则结点i是二叉树的根接点，没有双亲。如果i>1,则其双亲parent(i)是结点Math.floor(i/2);
     b.如果2*i>n，则结点i无左孩子。否则其左孩子结点是2*i;
     c.如果2*1+1>n,则结点无右孩子。否则其右孩子结点是2*i+1。
（六）平衡二叉树满足以下条件：一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
```

![二叉树](https://1260246514-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LIF00j7ciYvi9a1zYf_%2F-LJ2xuZfkqx2aJvjei1q%2F-LJ2xxHk8qsSG7GiZWD0%2F%E4%BA%8C%E5%8F%89%E6%A0%91.jpg?generation=1533369900358560\&alt=media)

> 二叉树的遍历方式：

```
（一）先序遍历：先访问根节点，然后再分别先序遍历左子树和右子树。
（二）中序遍历：先中序遍历左子树，然后访问根节点和中序遍历右子树。
（三）后序遍历：先后序遍历左子树和右子树。然后访问根节点。
```

二叉树的数据结构和遍历算法实现如下：

```
        class TNode {
            constructor(element, leftChild, rightChild) {
                this.element = element;
                this.leftChild = leftChild || null;
                this.rightChild = rightChild || null;
            }
        }

        class BinaryTree {
            constructor(element) {
                this.rootNode = new TNode(element);
            }

            add(element, parent, type) { // 添加结点
                let node = new TNode(element);
                let parentNode = this.find(parent, this.rootNode);
                if(parentNode) {
                    parentNode[type] = node;
                }
            }

            find(element, rootNode) { // 查找结点
                if (!rootNode) {
                    return null;
                }
                if (rootNode.element === element) {
                    return rootNode;
                } else {
                    return this.find(element,rootNode.leftChild) || this.find(element,rootNode.rightChild);
                }
            }

            visit(node) { // 遍历
                console.log(node.element);
            }

            preOrderTraverse(rootNode) { // 先序遍历
                rootNode = rootNode || this.rootNode;
                this.visit(rootNode);
                rootNode.leftChild && this.preOrderTraverse(rootNode.leftChild);
                rootNode.rightChild && this.preOrderTraverse(rootNode.rightChild);
            }

            inOrderTraverse(rootNode) { // 中序遍历
            rootNode = rootNode || this.rootNode;
            rootNode.leftChild && this.inOrderTraverse(rootNode.leftChild);
            this.visit(rootNode);
            rootNode.rightChild && this.inOrderTraverse(rootNode.rightChild);
            }

            postOrderTraverse(rootNode) { // 后序遍历
            rootNode = rootNode || this.rootNode;
            rootNode.leftChild && this.postOrderTraverse(rootNode.leftChild);
            rootNode.rightChild && this.postOrderTraverse(rootNode.rightChild);
            this.visit(rootNode);
            }
        }
```

## 7、本节源码

[源码地址](https://github.com/wuyadream/Notes/tree/99017280861b5aadec350a852d5ba15dbde0d4ff/sourceCode/datastruct.js)

## 8、参考文档

[哈希表(hashtable)的javascript简单实现](https://www.cnblogs.com/hyl8218/archive/2010/01/18/1650589.html)

[JavaScript数据结构《队列》](https://segmentfault.com/a/1190000011374405)

[javascript实现数据结构： 树和二叉树,二叉树的遍历和基本操作](https://www.cnblogs.com/webFrontDev/p/3865719.html)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://fe-note.gitbook.io/notes/computer/datastruct.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.