树

节点数量 = 边数 + 1

深度/高度

最高

节点深度

从根节点（深度为0）开始，

节点高度

从该节点下面的叶子节点（高度为0）开始数

节点的度

子节点的数量

广度优先遍历 层序遍历

使用队列，初始时将根节点加入，头指针指向根节点，之后的每次都加入头指针所指节点的子节点，并且头指针后移

深度优先遍历

使用栈，先将根节点入栈，之后每次入栈栈顶节点没有入过栈的子节点，如果没有子节点，出栈

二叉树

• 每个节点度/子节点最多为2
• 节点数量 = 边数 + 1====>度为0的节点比度为2的节点多一个

左子树

右子树

完全二叉树

除了最后一层都是满的，最后一层缺少右子树

• 编号为i的子节点: 可以通过父节点的编号计算得到子节点的编号
  • 左子树编号: 2 * i
  • 右子树编号：2 * i + 1
• 可以用连续空间存储

满二叉树

没有度为1的节点，只有度为0和2的节点

完美二叉树

每一层都是满的

二叉树的实现

#include <bits/stdc++.h>
using namespace std;

struct TreeNode
{
    // 节点保存的值
    int val;
    // 节点地址
    TreeNode *Lnext;
    TreeNode *Rnext;
    // 节点构造函数
    TreeNode(int x) : val(x), Lnext(NULL), Rnext(NULL){};
};

struct BinaryTree
{

    TreeNode *RootNode;

public:
    BinaryTree(int rootV)
    {
        RootNode = new TreeNode(rootV);
    }
    void insert(int val)
    {
        TreeNode *node = RootNode;
        while (true)
        {
            if (node->Lnext==NULL||node->Rnext==NULL) break;
            if (rand()%2) node=node->Lnext;
            else node=node->Rnext;
        }

        if (node->Lnext==NULL)
        {
            node->Lnext = new TreeNode(val);
        } else {
            node->Rnext = new TreeNode(val);
        }
    }
};

void bfs(TreeNode *root)
{   
    TreeNode* arr[100];
    int head,tail=0;
    arr[tail++]= root;

    while (head < tail)
    {
        TreeNode *node = arr[head];
        cout<<node->val<<" ";
        if (node->Lnext) arr[tail++] = node->Lnext;
        if (node->Rnext) arr[tail++] = node->Rnext;
        head++;
    }
}

int tot = 0;
void dfs(TreeNode * root)
{
    if (root == NULL) return;
    int start , end;
    tot+=1;
    start = tot;
    if (root->Lnext) dfs(root->Lnext);
    if (root->Rnext) dfs(root->Rnext);

    tot+=1;
    end = tot;
    printf("%d : [%d-%d]\n",root->val,start,end);
    return;
}

void clear(TreeNode *node)
{
    if (node==NULL) return;
    clear(node->Lnext);
    clear(node->Rnext);
    free(node);
    return;
}

int main()
{
    srand(time(nullptr));

    BinaryTree * bi = new BinaryTree(1);

    for (int i = 2;i < 8;i++) {
        bi->insert(i);
    }

    bfs(bi->RootNode);
    cout<<endl;
    dfs(bi->RootNode);
    return 0;
}