37.2° Blog

时间：2021.01.18 14:03

1、二叉树的性质

1.1 $n0 = n2 + 1$

非空二叉树的叶子结点数等于度为2的结点数加1。

证明：

设度为0，1，2的结点个数分别为n0，n1，n2，则结点总数 n = n0 + n1 + n2。

再看分支数，除根节点外，其余结点都有一个分支进入，设B为分支总数，则n=B+11。由于这些分支是由度为1或2的结点射出的，所以又有 B = n1 + 2n2。

联立，得 n0 = n2 + 1。

2、一些基本概念

2.1 根节点代表一棵树所有的信息

• 知道树的根结点，树中任意一个结点都能访问到；
• 如果指针为空，代表整个树不存在

2.2 树是由众多子树构成的

• 空不是代表结点不存在，是对应的子树不存在

2.3 树的遍历

先序遍历

void preOrder(BiTree T)
{
    if(T == NULL)
        return;
    print_tree_value(T);
    preOrder(T->lchild);
    preOrder(T->rchild);
}

中序遍历

void InOrder(BiTree T)
{
    if(T == NULL)
        return;
    InOrder(T->lchild);
    print_tree_value(T);
    InOrder(T->rchild);
}

后序遍历

void PostOrder(BiTree T)
{
    if(T == NULL)
        return;
    PostOrder(T->lchild);
    PostOrder(T->rchild);
    print_tree_value(T);
}

3、先序遍历方式建树

算法思想：

• 先读入根结点数据，并且创建根节点；
• 再读入左子树数据并创建左子树，
• 之后再读入右子树数据并创建右子树，
• 在根结点左右子函数创建好之后，最终将根节点返回

// 先序遍历创建树，创建一棵树
BiTNode* preCreateBiTree()
{
    BiTNode* T = NULL;
    ElemType enter;
    enter = getchar();  // 可能读入空格

    if ('@' != enter)
    {
        T = (BiTNode*)malloc(sizeof(BiTNode));
        T->data = enter;

        // 创建左右子树
        T->lchild = preCreateBiTree();
        T->rchild = preCreateBiTree();
    }
    return T;
}

输出先序、中序遍历结果：

4、先序、中序创建二叉树

先序序列

A	B	D	E	C	F	G
0	1	2	3	4	5	6
	preStartIndex+1		preStartIndex+length	preStartIndex+length+1		preEndIndex

中序序列

D	B	E	A	F	C	G
0	1	2	3	4	5	6
inStartIndex		rootIndex-1	rootIndex	rootIndex+1		inEndIndex

int length = rootIndex - inStartIndex;

一颗树的先序序列和中序序列能确定这棵树。

• 先序序列：根，左，右
• 中序序列：左，根，右
• 后序序列：左，右，根

表示子树不存在：

• 序列长度为零，代表子树不存在
• 给定起始位置索引和终止位置索引。起始位置和终止位置不合法，也就是终止位置大于起始位置来代表序列不存在，即代表字数不存在

BiTNode* PreInOrderCreateTre(ElemType preOrderList[], int preStartIndex, int preEndIndex,
    ElemType inOrderList[], int inStartIndex, int inEndIndex)
{
    if (preStartIndex > preEndIndex)
        return NULL;
    BiTNode* t = (BiTNode*)malloc(sizeof(BiTNode)); // 分配空间
    t->data = preOrderList[preStartIndex];  // 每颗子树根节点为先序序列第一个
    int rootIndex = inStartIndex;
    for (; rootIndex <= inEndIndex; rootIndex++) // 寻找根结点在中序序列中位置
        if (t->data == inOrderList[rootIndex])
            break;
    int length = rootIndex - inStartIndex;
    // 创建左子树
    t->lchild = PreInOrderCreateTre(preOrderList, preStartIndex + 1,
        preStartIndex + length, inOrderList, inStartIndex, rootIndex - 1);
    // 创建右子树
    t->rchild = PreInOrderCreateTre(preOrderList, preStartIndex + length + 1,
        preEndIndex, inOrderList, rootIndex + 1, inEndIndex);
    return t;
}

ElemType preOrderList[] = { 'A','B','D','E','C','F','G' };
  int preOrderListLength = 7;
  ElemType inOrderList[] = { 'D','B','E','A','F','C','G' };
  int inOrderListLength = 7;
  BiTree T = PreInOrderCreateTre(preOrderList, 0, preOrderListLength - 1,
      inOrderList, 0, inOrderListLength - 1);

输出先序、中序遍历结果：

5、层序、中序创建二叉树

层序序列

A	B	C	D	E	F	G
0	1	2	3	4	5	6
			preStartIndex+length	preStartIndex+length+1		preEndIndex

中序序列

D	B	E	A	F	C	G
0	1	2	3	4	5	6
		rootIndex-1	rootIndex	rootIndex+1		inEndIndex

算法思想：

• 先从层次序列中确定根节点（子树根节点），
• 再到中序序列中确定根结点位置，此时会将中序序列分成左子树和右子树
• 在层次遍历中，依次取出每个结点到左（右）子树中序序列中匹配
• 确定左右子树序列，后构建二叉树

// 层序，中序遍历构建树
BiTNode* LevelInOrderCreateTree(ElemType levelOrderList[], int levelStartIndex, int levelEndIndex,
    ElemType inOrderList[], int inStartIndex, int inEndIndex)
{
    if (levelStartIndex > levelEndIndex)
        return NULL;
    BiTNode* t = (BiTNode*)malloc(sizeof(BiTNode)); // 分配空间
    t->data = levelOrderList[levelStartIndex];
    // 寻找根结点在中序序列中位置
    int rootIndex = inStartIndex;
    for (; rootIndex <= inEndIndex; rootIndex++) 
        if (t->data == inOrderList[rootIndex])
            break;
    // 左子树
    ElemType leftLevelOrderList[100];
    int leftLevelOrderListLength = 0;
    // 依次取每个结点到左子树中序序列中匹配
    for (int i = levelStartIndex + 1; i <= levelEndIndex; i++)
    {
        // 左子树在中序序列中寻找
        for (int j = inStartIndex; j <= rootIndex - 1; j++)
        {
            if (levelOrderList[i] == inOrderList[j])
                leftLevelOrderList[leftLevelOrderListLength++] = levelOrderList[i];
        }  
    }
    // 右子树
    ElemType rightLevelOrderList[100];
    int rightLevelOrderListLength = 0;
    // 依次取每个结点到右子树中序序列中匹配
    for (int i = levelStartIndex + 1; i <= levelEndIndex; i++)
    {
        // 右子子树在中序序列中寻找
        for (int j = rootIndex + 1; j <= inEndIndex; j++)
        {
            if (levelOrderList[i] == inOrderList[j])
                rightLevelOrderList[rightLevelOrderListLength++] = levelOrderList[i];
        }
    }
    // 创建左子树
    t->lchild = LevelInOrderCreateTree(leftLevelOrderList, 0, leftLevelOrderListLength - 1,
        inOrderList, inStartIndex, rootIndex - 1);
    // 创建右子树
    t->rchild = LevelInOrderCreateTree(rightLevelOrderList, 0, rightLevelOrderListLength - 1,
        inOrderList, rootIndex + 1, inEndIndex);
    return t;
}

  ElemType levelOrderList[] = { 'A','B','C','D','E','F','G' };
  int levelOrderListLength = 7;
  ElemType inOrderList[] = { 'D','B','E','A','F','C','G' };
  int inOrderListLength = 7;
  BiTree T = LevelInOrderCreateTree(levelOrderList, 0, levelOrderListLength - 1,
      inOrderList, 0, inOrderListLength - 1);

输出先序、中序遍历结果：