数据结构-树与二叉树

一、树的定义与性质

<1>定义

1. 结点（node）:树枝分叉处、树叶、树根
2. 根结点（root）：树根
3. 叶子结点（leaf）:叶子结点
4. 边（edge）：茎干和树枝
5. 子结点（child）
6. 子树（subtree）

<2>性质

1. 树可以没有结点，把这种情况下称为空树(empty tree)
2. 树的层次（layer），从根结点开始算起来，即根结点为第一层
3. 把结点的子树棵树称为结点的度（degree），而树的中结点的最大的度称为树的度（也称为树的宽度）
4. 对于有n个结点的树的边一定是n-1
5. 叶子结点被定义为0的结点，因此当树只有一个结点时，根结点也算作叶子结点
6. 结点的深度（depth）是指从根结点（深度为1），开始自顶向下逐层累加至该结点时的深度值；而高度（height）是指从最底层叶子结点开始自底向上逐层累加，而对于树而言，是选择最大的那个数，同时，深度和高度应该是一样的。
7. 多棵树结合在一起就是森林（forest）

<3>二叉树的递归定义

1. 要么二叉树没有根结点，是一棵空树。
2. 要么二叉树由根结点、左子树、右子树组成，且左子树和有子树都是二叉树。

• 区分二叉树和度为2的树
• 满二叉树：每一层结点个数都达到当层能够达到的最大结点数。
• 完全二叉树：除了最下面一层之外，其余层的结点个数都达到当层的最大结点数，且最下面一层只从左到右连续存在若干结点，而这些连续结点右边的结点全部不存在。
• 自己即是自己的祖先结点，也是自己的子孙结点。

<4>二叉树的存储结构

//二叉链表
struct node{
    typename data;
    node* lchild;
    node* rchild;
};

//如果二叉树在建树前根结点不存在，因此其地址一般设为NULL
node* root = NULL;

//如果想要新建结点，可以使用一下函数
node* newNode(int v){
    node* Node = new node;
    Node->data = v;//结点权值
    Node->lchild = Node->rchild = NULL;//初始状态下没有左右孩子
    return Node;//返回新建结点的地址
}

<5>二叉树结点的查找、修改

• 查找是指在给定数据域的条件下，在二叉树中找到所有数据域为给定数据域的结点，并将它们的数据域修改为给定的数据域。

void search(node* root, int x, int newdata){
    if(root == NULL){
        return;//递归边界
    }
    if(root->data == x){
        root->data = newdata;
    }
    search(root->lchild, x, newdata);
    search(root->rchild, x, newdata);
}

<6>二叉树结点的插入

• insert函数将在二叉树中插入一个数据域为x的新结点
• 如何判断是否需要加引用？如果函数中需要新建结点，即对二叉树的结构做出修改，就需要加引用；如果只是修改当前已有结点的内容，或仅仅是遍历树，就不需要加引用。
• 新建结点之后，务必令新结点的左右指针域为NULL。

void insert(node* &root, int x){
    if(root == NULL){//递归边界
        root = newNode(x);
        return;
    }
    if(由二叉树的性质，x应该插在左子树){
        insert(root->lchild, x);
    }else{
        insert(root->rchild, x);
    }
}

<7>二叉树的创建

node* Create(int data[], int n){
    node* root = NULL;
    for(int i = 0; i < n; i++){
        insert(root, data[i]);
    }
    return root;
}

<8>完全二叉树的存储结构

1. 对于完全二叉树当中的任何一个结点，其左孩子的编号一定是2x，而右孩子编号一定是2x+1
2. 1号位存放的必须是根结点
3. 该数组中元素存放的顺序恰好为该完全二叉树的层序遍历序列
4. 判断某个结点是否为叶结点的标志为，该结点（记结点下标为root）的左子结点编号root*2大于结点总个数n
5. 某个结点是否为空结点的标志为该结点下标root大于结点总个数n