数据结构-树与二叉树

一、树的定义与性质

<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

相关推荐