数据结构(12)-树结构初探

定义

树(Tree)是n(n >= 0)个结点的有限集合。n = 0时称为空树。在任意一棵非空树中：

有且仅有一个特定的结点称为根结点。

当n > 1时，其余结点可分为m(m > 0)个互不相交的有限集合，其中每一个集合本身又是一棵树，称之为根的子树(SubTree)。

树是一种一对多的数据结构。

树的相关概念

树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。度为0的结点称为叶结点(leaf)或终端结点。度不为0的结点称为分支结点或者非终端结点。分支结点也称为内部结点。树的度是树内各结点的度的最大值。

结点的子树的根为该结点的子节点(child)，相应的，即为双亲(parent)。结点的层次(level)是从根结点开始，根为第1层，根的子结点为第2层，以此类推。树中结点的最大层次称之为高度或深度(Depth)，深度从上往下，高度从下往上。层次是从1开始；高度、深度也都是从1开始的。

线性结构和树结构的区别：

线性结构中，第一个元素无前驱；最后一个元素无后继；中间元素有一个前驱、一个后继。
树结构中，根结点无parent、唯一存在；叶结点无child、可以存在多个；中间结点一个parent多个child。

二叉树

二叉树(Binary Tree)是n(n >= 0)个结点的有限集合。该集合或者为空集，或者由一个根结点和两棵不相交的、分别称为根结点的左子树和右子树的二叉树组成。

通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。

二叉树的特点如下：

每个结点最多有两棵子树，即二叉树中不存在度大于2的结点。
左子树和右子树是有顺序的。
即便是某结点只有一颗子树，也需要区分左右子树。

二叉树的五种形态：

空树
只有一个根结点
根结点只有左子树
根结点只有右子树
根结点既有左子树又有右子树

斜树：所有结点都只有一种子树，即都为左子树，或者都为右子树。

完全二叉树：若设二叉树的高度为h，除第h层外，其它各层(1～h-1)的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，不存在中间有空结点的情况。

满二叉树：除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树，通俗的说parent结点都有2个child结点。

平衡二叉树：它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

二叉树的性质：

在二叉树的第i层上最多有 $2^{i-1}$ 个结点
深度为k的二叉树最多有 $2^k - 1$ 个结点(k >= 1)
对于任何一颗二叉树T，如果其终端结点数(叶子节点数)为 $n_0$ ，度为2的结点数为 $n_2$ ，则 $n_0 = n_2 + 1$
具有n个结点的完全二叉树深度为( $log_2n$ )+1。
对一个具有n个结点的完全二叉树的结点按层序编号，对于任一结点i(1 <= i <= n)有
- 如果i = 1，则结点i是二叉树的根结点，如果i > 1，其双亲结点是i / 2
- 如果2i > n，则结点i无左孩子，即结点i为叶子结点；否则左孩子是结点2i
- 如果2i + 1 > n，则结点i无右孩子，否则其右孩子是结点2i + 1

二叉树的存储结构

树的存储结构可分为线性存储结构和链式存储结构。

二叉树的顺序存储结构

二叉树的顺序存储结构就是用一堆一位数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标要能提现结点之间的逻辑关系，比如双亲与孩子的关系等。

二叉树顺序结构.png

将上述二叉树存入数组中：

下标：1 2 3 4 5 6 7 8 9 10
结点：A B C D E F G H I J

如果不是完全二叉树，也可以按照完全二叉树编号，只不过需要把不存在的结点设置为空。

代码如下：

#define T_MAX_SIZE 100
#define T_ERROR -1
#define T_OK 1
typedef int TStatus;
typedef int ElementType;
typedef ElementType BinaryTree[T_MAX_SIZE];
ElementType NULL_NODE = 0; // 空结点
typedef struct {
    int level; //结点层
    int order; //本层的序号(按照满二叉树给定序号规则)
} Position;


void initBinaryTree(BinaryTree bt) {
    for (int i = 0; i < T_MAX_SIZE; i++) {
        bt[i] = NULL_NODE;
    }
}

void initBinaryTreeWithData(BinaryTree bt, int *data, int len) {
    for (int i = 0; i < T_MAX_SIZE; i++) {
        if (i < len) {
            bt[i] = data[i];
        } else {
            bt[i] = NULL_NODE;
        }
    }
}

bool isEmptyBinaryTree(BinaryTree bt) {
    return bt[0] == NULL_NODE;
}

// 获取二叉树的深度
int getBinaryTreeDepth(BinaryTree bt) {
    int i = 0;
    for (i = T_MAX_SIZE - 1; i >= 0; i--) {
        if (bt[i] != NULL_NODE) {
            break;
        }
    }
    return log2(i) + 1;
}

// 返回处于位置pos的结点值
ElementType getBinaryTreeValue(BinaryTree bt, Position pos) {
    int level = pow(2, pos.level - 1);
    int index = level + pos.order - 2;
    return bt[index];
}

// 给处于位置pos的结点赋值
TStatus assignValue(BinaryTree bt, Position pos, ElementType e) {
    int index = (int)pow(2, pos.level - 1) + pos.order - 2;
    
    // parent结点不存在
    if (bt[(index+1)/2-1] == NULL_NODE) {
        return T_ERROR;
    }
        
    // 将parent置空 但是有子节点
    if (e == NULL_NODE && (bt[index*2+1] != NULL_NODE || bt[index*2+2] != NULL_NODE)) {
        return T_ERROR;
    }
    
    bt[index] = e;
    return T_OK;
}

// 获取pos位置的parent
ElementType getParentValue(BinaryTree bt, Position pos) {
    if (bt[0] == NULL_NODE) {
        return NULL_NODE;
    }
    int level = pow(2, pos.level - 1);
    int index = level + pos.order - 2;
    return bt[(index - 1) / 2];
}

// 获取某个结点的左孩子 e是结点内容
ElementType getLeftChildValue(BinaryTree bt, ElementType e) {
    if (bt[0] == NULL_NODE) {
        return NULL_NODE;
    }
    
    for (int i = 0; i < T_MAX_SIZE; i++) {
        if (bt[i] == e) {
            return bt[i*2+1];
        }
    }
    
    return NULL_NODE;
}

// 获取某个结点的右孩子 e是结点内容
ElementType getRightChildValue(BinaryTree bt, ElementType e) {
    if (bt[0] == NULL_NODE) {
        return NULL_NODE;
    }
    
    for (int i = 0; i < T_MAX_SIZE; i++) {
        if (bt[i] == e) {
            return bt[i*2+2];
        }
    }
    
    return NULL_NODE;
}

// 获取某个结点的左兄弟 e是结点内容
ElementType getLeftSiblingValue(BinaryTree bt, ElementType e) {
    if (bt[0] == NULL_NODE) {
        return NULL_NODE;
    }
    
    for (int i = 0; i < T_MAX_SIZE; i++) {
        if (bt[i] == e && i % 2 == 0) {
            // 获取和当前值相等、且还是右结点
            return bt[i-1];
        }
    }
    
    return NULL_NODE;
}

// 获取某个结点的右兄弟 e是结点内容
ElementType getRightSiblingValue(BinaryTree bt, ElementType e) {
    if (bt[0] == NULL_NODE) {
        return NULL_NODE;
    }
    
    for (int i = 0; i < T_MAX_SIZE; i++) {
        if (bt[i] == e && i % 2 == 1) {
            // 获取和当前值相等、且还是左结点
            return bt[i+1];
        }
    }
    
    return NULL_NODE;
}

二叉树的链式存储结构

由于为了方便查找与存储，二叉树的顺序存储结构都是按照完全二叉树来实现的，这样内存空间的利用率比较低。所以我们就需要考虑链式存储。二叉树的每个结点最多有两个孩子，所以设计成一个数据域和两个指针域是比较合适的。

二叉树链式结构.png

#define T_MAX_SIZE 100
#define T_ERROR -1
#define T_OK 1
typedef int TStatus;
typedef char ElementType;


typedef struct BinaryNode {
    ElementType data;
    struct BinaryNode *leftChild, *rightChild;
} BinaryNode, *BinaryTree;


// 用以初始化或者创建二叉树
// 空位置的用#字符代替
int indexs = 1;
// 第一个位置存放字符串的长度
typedef char String[26];
String treeStr;
TStatus StrAssign(String T, char *data) {
    if (strlen(data) > T_MAX_SIZE) {
        return T_ERROR;
    }
    
    T[0] = strlen(data);
    for(int i=1;i<=T[0];i++) {
        T[i] = *(data+i-1);
    }
    
    return T_OK;
}


void initBinaryTree(BinaryTree *bt) {
    *bt = NULL;
}

// 创建二叉树 按前序输入二叉树中的结点值(字符), #表示空树
void createBinaryTree(BinaryTree *bt) {
    ElementType e = treeStr[indexs++];
    
    if (e == '#') {
        *bt = NULL;
    } else {
        *bt = (BinaryTree)malloc(sizeof(BinaryNode));
        (*bt)->data = e;
        createBinaryTree(&((*bt)->leftChild));
        createBinaryTree(&((*bt)->rightChild));
    }
}

bool isEmptyBinaryTree(BinaryTree bt) {
    return bt;
}

// 销毁二叉树 释放结点
void destoryBinaryTree(BinaryTree *bt) {
    if (*bt) {
        if ((*bt)->leftChild) {
            destoryBinaryTree(&(*bt)->leftChild);
        }
        if ((*bt)->rightChild) {
            destoryBinaryTree(&(*bt)->rightChild);
        }
        free(*bt);
        *bt = NULL;
    }
}

// 获取二叉树的深度
int getBinaryTreeDepth(BinaryTree bt) {
    if (!bt) {
        return 0;
    }
    
    int leftDepth, rightDepth;
    if (bt->leftChild) {
        leftDepth = getBinaryTreeDepth(bt->leftChild);
    } else {
        leftDepth = 0;
    }
    if (bt->rightChild) {
        rightDepth = getBinaryTreeDepth(bt->rightChild);
    } else {
        rightDepth = 0;
    }
    
    return leftDepth > rightDepth ? (leftDepth + 1): (rightDepth + 1);
}

二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

前序遍历：先访问根结点，然后前序遍历左子树，再前序遍历右子树。如图：ABDGHCEIF。

前序遍历.png

代码实现如下：

顺序存储结构前序遍历：

// 前序遍历
void preOrderTraverse(BinaryTree bt, int leftIndex) {
    // 传入leftIndex
    printf(" %d ", bt[leftIndex]);
    
    // 先遍历左子树
    if (bt[2*leftIndex+1] != NULL_NODE) {
        preOrderTraverse(bt, 2*leftIndex+1);
    }
    
    // 最后遍历右子树
    if (bt[2*leftIndex+2] != NULL_NODE) {
        preOrderTraverse(bt, 2*leftIndex+2);
    }
}

链式存储结构前序遍历

// 前序遍历
void PreOrderTraverse(BinaryTree bt) {
    if (bt == NULL) {
        return;
    }
    printf("%c",bt->data);
    
    // 再先序遍历左子树
    PreOrderTraverse(bt->leftChild);
    
    // 后先序遍历右子树
    PreOrderTraverse(bt->rightChild);
}

中序遍历：从根节点开始，但是先不访问根结点，中序遍历根结点的左子树，然后访问根结点，最后遍历右子树。如图：GDHBAEICF。

中序比那里.png

顺序存储结构中序遍历

// 中序遍历 先不访问根结点，中序遍历根结点的左子树，然后访问根结点，最后遍历右子树
void inOrderTraverse(BinaryTree bt, int inIndex) {
    // 先遍历左子树
    if (bt[2*inIndex+1] != NULL_NODE) {
        inOrderTraverse(bt, 2*inIndex+1);
    }
    
    // 打印输出
    printf(" %d ", bt[inIndex]);
    
    // 最后遍历右子树
    if (bt[2*inIndex+2] != NULL_NODE) {
        inOrderTraverse(bt, 2*inIndex+2);
    }
}

链式存储结构中序遍历

// 中序遍历
void inOrderTraverse(BinaryTree bt) {
    if (bt == NULL) {
        return;
    }
    
    // 再先序遍历左子树
    inOrderTraverse(bt->leftChild);
    
    printf("%c",bt->data);

    // 后先序遍历右子树
    inOrderTraverse(bt->rightChild);
}

后序遍历：从左到右先叶子后结点，先左后右，最后访问根结点。如图：GHDBIEFCA。

后序遍历.png

顺序存储结构后序遍历

// 后序遍历 从左到右先叶子后结点，先左后右，最后访问根结点
void sufOrderTraverse(BinaryTree bt, int inIndex) {
    // 先遍历左子树
    if (bt[2*inIndex+1] != NULL_NODE) {
        sufOrderTraverse(bt, 2*inIndex+1);
    }
    
    // 后遍历右子树
    if (bt[2*inIndex+2] != NULL_NODE) {
        sufOrderTraverse(bt, 2*inIndex+2);
    }
    
    // 打印输出
    printf(" %d ", bt[inIndex]);
}

链式存储结构后序遍历

// 后序遍历 
void sufOrderTraverse(BinaryTree bt) {
    if (bt == NULL) {
        return;
    }
    
    sufOrderTraverse(bt->leftChild);
    sufOrderTraverse(bt->rightChild);
    
    printf("%c",bt->data);
}

层序遍历：从根结点开始，从上而下逐层遍历，在同一层中，按照从左到右的顺序对结点逐个访问。如图：ABCDEFGHI。

层序遍历.png

顺序存储结构层序遍历

void levelOrderTraverse(BinaryTree bt, int inIndex) {
    int lastIndex = T_MAX_SIZE;
    // 找到最后一个非空结点
    while (bt[lastIndex] == NULL_NODE) {
        lastIndex -= 1;
    }
    
    for (int i = 0; i < lastIndex; i++) {
        if (bt[i] != NULL_NODE) {
            printf(" %d ", bt[i]);
        }
    }
}

通过二叉树的遍历特点可知：

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树
已知前序和后序是不能确定的，是因为我们只能确定根结点，而无法确定左子树和右子树

参考文献

大话数据结构