时间:2021.01.18 14:03
1、二叉树的性质
1.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);
输出先序、中序遍历结果:
