前言

  • 学习了一段时间的数据结构,但是树这一块这是理解了一些理论知识,本篇将记录树的结构和应用。

树的定义

  • 自由树:
  • 有根树:一颗有根树T,简称为树,可定义为n(n≥0)个节点的有限集合,当n=0时,T称为空树;否则,T是非空树。
  • 每棵子树的根节点有且仅有一个直接前驱,但可以有0个或多个直接后继

树的基本术语

  • 结点(node): 它包含数据元素及指向其他结点的分支指针
  • 结点的度(degree): 它是结点所拥有的子树棵数
  • 叶结点(leaf): 度为0的结点,又称为终端结点
  • 子女结点(child): 若结点X的子树非空,则子树的根结点即为结点x的子女
  • 父结点(parent): 又称为双亲结点,若结点x有子女,它即为子女的父结点
  • 兄弟结点(sibling): 同一父结点的子女称为兄弟
  • 祖先结点(ancestor): 从根结点到该结点所经历的所有结点
  • 子孙结点(descendant): 某一结点的子女,以及这些子女的子女都是改结点的子孙
  • 结点间的路径(path): 树中任一结点vi经过一系列的结点v1,v2,……vk到vj,其中(vi, v1),(v1, v2)……(vk, vj)是树的分支,则称vi, v1, v2……,vk,vj是vi与vj间的路径
  • 结点的深度(depth): 结点所处层次,简称结点的层次,即从根到改结点的路径上的分支数加1
  • 结点的高度(height): 空树的高度为0, 叶结点的高度为1, 非叶结点的高度等于它的两个子女结点的高度向比, 取最大值加1
  • 树的深度(depth): 树中距离根结点最远的结点所处层次即为树的深度
  • 树的高度(height): 树的高度等于根结点的高度,树的高度与树的深度的值相等,但高度与深度计算的方向不同
  • 树的宽度(breadth): 统计每一层结点个数,取最大者作为树的宽度
  • 树的度(degree):树中结点的度的最大值
  • 有序树(ordered tree):树中结点的各棵子树T0,T1……是有次序的,即为有序树。其中,T1叫做根的第一颗子树……
  • 无序树:树中结点的各棵子树之间的次序是不重要的,可以互相交换位置
  • forest:森林是m棵树的集合

二叉树

二叉树的定义

  • 二叉树是结点的一个有限集合,该集合或者为空,或者是由一个根节点加上两棵分别称为左子树和右子树、互不相交的二叉树组成
  • 二叉树的任意形状都是基于五种形态组成或嵌套而成的

       [ ∅(n=0)
    T={
       [r,T1,T2} (n >0)


二叉树的性质


二叉树的存储表示

  • 二叉树的存储表示有两种:顺序存储表示和链接存储表示

二叉链表的结构定义

1
2
3
4
5
6
7
#include <iostream>
#include <stdlib.h>
typedef struct node{
TElemType data;
struct node* lchild;
struct node* rchild;
}BitNode, *BinTree;

二叉树的遍历

  1. VLR前序遍历

    1
    2
    3
    4
    5
    6
    7
    void PreOrder(BitNode *T){
    if(T != NULL){
    cout << T->data;
    Inorder(T->lchild);
    Inorder(T->rchild);
    }
    }
  2. LVR中序遍历

    1
    2
    3
    4
    5
    6
    7
    void InOrder(BitNode *T){
    if(T != NULL){
    Inorder(T->lchild);
    cout << T->data;
    Inorder(T->rchild);
    }
    }
  3. LRV后序遍历

    1
    2
    3
    4
    5
    6
    7
    void PostOrder(BitNode *T){
    if(T != NULL){
    Inorder(T->lchild);
    Inorder(T->rchild);
    cout << T->data;
    }
    }

使用前序遍历建立二叉树

  • 所有节点值为’#’的结点位于原二叉树的空子树结点的位置,读入’;’则停止建立二叉树。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    void createBinTree(BinTree &T){
    TElemType item;
    cin >> item;
    if(item == ';') return;
    if(item != '#'){

    T = new BitNode;
    if(T == NULL) cerr << "存储分配失败" << endl;
    T -> data = item;
    createBinTree(T->lchild);
    createBinTree(T->rchild);
    }else{
    T = NULL;
    }
    }
  • 前序遍历按照广义表输出二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void PreOrder(BitNode *T){
if(T != NULL){
cout << T->data;
if(T->lchild != NULL || T -> rchild != NULL ){
cout << '(';
if(T->lchild != NULL)
PreOrder(T->lchild);
cout << ',';
if(T->rchild != NULL)
PreOrder(T->rchild);
cout << ')';
}
}
}

二叉树的销毁

  • 算法首先销毁掉根的左子树和右子树,然后再释放根结点。

参考链接

留言

⬆︎TOP