数据结构——树

树结构

树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。
** 在任意一个非空树中,有如下特点。**

有且仅有一个特定的称为根的节点。
当n＞1时，其余节点可分为m（m＞0）个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树。

树结构图

根节点： 树的最顶端的节点。
叶子节点： 不再连接的节点（即末端），称为叶子节点（又称为终端结点）。
子节点： 除根节点之外，并且本身下面还连接有节点的节点。
高度： 从叶子节点开始从0计数，越靠近根节点，高度越高。上图中节点7高度为0，节点1高度为3。
深度：从根节点开始从0计数，离根节点越远，深度越深。上图中节点1深度为0，节点7深度为3。

二叉树

概念

二叉树的每个节点的最多两个子节点，且有子树具有左右之分。此外，二叉树还有两种特殊形式，完全二叉树和满二叉树。

完全二叉树：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树。

`特性:`

1.完全二叉树被称为真二叉树，其中所有叶子都具有相同的深度。
2.在完全二叉树中，深度d处的节点数为 2 d。
3.在具有n个节点的完全二叉树中，树的高度为log(n+1)。
4.除最后一个级别外所有级别均已满。

完全二叉树

满二叉树： 一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。

满二叉树

二叉搜索树（BST）：是二叉树的一种，但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值”

二叉树存储

二叉树存储结构分两类：顺序结构存储、链式结构存储。

1.链式存储结构

链式存储结构

C语言二叉树节点存储，代码如下：

typedef struct BiTNode
{
    char   data;               // 存放结点的数据元素。
    struct BiTNode *lchild;    // 指向左子结点地址的指针。
    struct BiTNode *rchild;    // 指向右子结点地址的指针。
}BiTNode,*BiTree;

BiTNode* BuyBTNode(BTDataType x)
{
    BTNode* newnode = (BTNode*)malloc(sizeof(BTNode));
    if (newnode == NULL)//这里是为了判空，若malloc失败，则直接退出
    {
        perror("malloc failed");//perror输出错误信息
        exit(-1);
    }
    newnode->left = newnode->right = NULL;
    newnode->data = x;
    return newnode;
}

BiTNode* CreatBinaryTree()
{
 BiTNode* node1 = BuyNode(1);
 BiTNode* node2 = BuyNode(2);
 BiTNode* node3 = BuyNode(3);
 BiTNode* node4 = BuyNode(4);
 BiTNode* node5 = BuyNode(5);
 BiTNode* node6 = BuyNode(6);
 
 node1->_left = node2;
 node1->_right = node4;
 node2->_left = node3;
 node4->_left = node5;
 node4->_right = node6;
 return node1;
}

JavaScript二叉树节点存储，代码如下：

class Node {
    constructor(key) {
     this.key = key; // {1} 节点值
     this.left = null; // 左侧子节点引用
     this.right = null; // 右侧子节点引用
    }
}

/***
  二叉搜索树存值
***/

const Compare = {
    LESS_THAN: -1,//小于
    BIGGER_THAN: 1,//大于
    EQUALS: 0//等于
}
class BinarySearchTree {
    constructor() {
        this.root = null; // Node类型的根节点
    }
    // 比较节点的值大小
    compareFn(a, b) {
        if (a === b) {return Compare.EQUALS;}
        return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
    }
    // 插入值
    insert(key) {
        if (this.root == null) {
            this.root = new Node(key); 
        } else {
            this.insertNode(this.root, key);
        }
      }
    insertNode(node, key) {
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) { 
          if (node.left == null) {
              node.left = new Node(key); 
          } else {
              this.insertNode(node.left, key);
          }
      } else {
          if (node.right == null) {
              node.right = new Node(key);
          } else {
              this.insertNode(node.right, key);
          }
      }
  }
}

2.数组（数组是典型的顺序存储结构）

顺序存储结构

二叉树遍历

在计算机程序中，遍历本身是一个线性操作。遍历同样具有线性结构的数组或链表，是一件轻而易举的事情。而二叉树是典型的非线性数据结构，在遍历时需要把非线性关联的节点转化成一个线性的序列。

二叉树遍历，从节点之间位置关系角度看，二叉树遍历可分为前序遍历、中序遍历、后序遍历、层序遍历。从更宏观的角度来看，二叉树的遍历归结为两大类深度优先遍历（前序遍历、中序遍历、后序遍历）、广度优先遍历（层序遍历）。

先序遍历
二叉树的前序遍历，输出顺序是根节点、左子树、右子树。
C语言代码示例：

void PrevOrder(BTNode* root)
{
    if (root == NULL)//递归终止条件，若遍历到空，则返回
    {
        printf("NULL");
        return;
    }
    printf("%d", root->data);//先序遍历，先输出根节点的值
    PrevOrder(root->left);//递归进入左子树
    PrevOrder(root->right);//递归进入右子树
}

JavaScript代码示例：

preOrderTraverse(callback) {
  this.preOrderTraverseNode(this.root, callback);
}
preOrderTraverseNode(node, callback) {
  if (node != null) {
    callback(node.key);
    this.preOrderTraverseNode(node.left, callback);
    this.preOrderTraverseNode(node.right, callback);
  }
}

中序遍历
二叉树的中序遍历，输出顺序是左子树、根节点、右子树。中序遍历应用于二叉搜索树(BST)，将从最小到最大的顺序遍历所有节点。

C语言代码示例：

void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL");
        return;
    }
    InOrder(root->left);
    printf("%d", root->data);
    InOrder(root->right);
}

JavaScript代码示例：

  inOrderTraverse(callback) {
    this.inOrderTraverseNode(this.root, callback);
  }
  inOrderTraverseNode(node, callback) {
    if (node != null) {
      this.inOrderTraverseNode(node.left, callback);
      callback(node.key);
      this.inOrderTraverseNode(node.right, callback);
    }
  }

后序遍历
二叉树的后序遍历，输出顺序是左子树、右子树、根节点。

C语言代码示例：

void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d", root->data);
}

JavaScript代码示例：

  postOrderTraverse(callback) {
    this.postOrderTraverseNode(this.root, callback);
  }
  postOrderTraverseNode(node, callback) {
    if (node != null) {
      this.postOrderTraverseNode(node.left, callback);
      this.postOrderTraverseNode(node.right, callback);
      callback(node.key);
    }
  }

参考资料：
https://blog.csdn.net/m0_68621863/article/details/130417158
https://github.com/PacktPublishing/Learning-JavaScript-Data-Structures-and-Algorithms-Third-Edition”

数据结构——树

树结构

二叉树

概念

特性:

二叉树存储

二叉树遍历

推荐阅读更多精彩内容

`特性:`