009——二叉树

二叉树的五种基本形态：

1.二叉树可以是空树

2.只有一个根节点的树

3.斜树：只有左子树或右子树的树

4.左右孩子都有的树

二叉树的性质：

1.假设根节点是第一层，在二叉树的第i层上最多有2^(n-1)个结点

2.深度为k的二叉树，最多有（2^k）-1个结点

3.任意一个非空二叉树，度为0的结点数比度为2的结点数多一个

4.在完全二叉树中有无度为1的判断

5.具有N个结点的完全二叉树的深度为log2（N+1）（向下取整）或者（log2N）+1（向上取整）

6. 如果有一棵n个结点的完全二叉树，其结点编号按照层次序（从上到下，从左到右），则除根结点外，满足[i/2 , i, 2i, 2i+1]的规则

二叉树的存储方式

1.直接采用数组存储二叉树，将任意一个二叉树补成完全二叉树，不过这样容易造成空间上的浪费

2.二叉链表存储

二叉树是树中最常用的一种，即度为2的树（每个结点最多有两个孩子），在二叉树中，结点的度只有0、1、2这三种可能

二叉树的五种基本形态：

1.二叉树可以是空树

2.只有一个根节点的树

3.斜树：只有左子树或右子树的树

4.左右孩子都有的树

二叉树的性质：

1.假设根节点是第一层，在二叉树的第i层上最多有2^(n-1)个结点

解释：若想要结点数最多，则要求除叶子结点外，每个结点的度都为2

层数该层结点数

一层：根节点 1

二层： 1*2 2

三层 2*2 4

四层 4*2 8

n层 2*2*...*2 2^(n-1)

2.深度为k的二叉树，最多有（2^k）-1个结点

将所有层次的结点数相加，再根据等比数列求和公式可得

满二叉树

而有（2^k）-1个结点的树有被称作满二叉树，满二叉树没有度为1的结点

完全二叉树

对满二叉树的结点编号（从上到下再从左到右）从后面删除若干个连续的编号最大的结点，剩下的部分就是完全二叉树

如下图删除15.14.13

同时，对于完全二叉树来说，度为1的结点要么没有，要么只有一个

满二叉树也是完全二叉树

3.任意一个非空二叉树，度为0的结点数比度为2的结点数多一个

解释：

按照度来分，我们可以将其分成度分别为0，1，2的结点：

n = n0 + n1 + n2

按照有无父亲，或者说是是否可以当作孩子结点，我们可以分成根节点和其他结点：

n = 1 + （n-1）

而在这（n-1）个孩子结点里，我们可以再将每个结点看作父亲，

度为0的父亲没有孩子 0 * n0

度为1的父亲一个孩子 1 * n1

度为2的父亲两个孩子 2 * n1

所以可以推出

n = 1 + 0 * n0 + n1 + 2n1

n0 + n1 + n2 = 1 + n1 + 2n1

n0 = n2 + 1

或者从连线个数的角度理解：

n个结点的树有n-1条连线

度为0的树向下有0条

度为1的树向下有n1条

度为2的树向下有2n2条

n1+n2+n0-1 =n1+2n2

n0-1=n2

4.在完全二叉树中有无度为1的判断

没有度为1的结点，n=n0+n2=n2+1+n2=2n2+1

有度为1的结点，n=n0+n1+n2=2n2+2

所以在完全二叉树中，结点数为奇数,没有度为1的结点；结点数为偶数，有度为1的结点且只有1个

5.具有N个结点的完全二叉树的深度为log2（N+1）（向下取整）或者（log2N）+1（向上取整）

6. 如果有一棵n个结点的完全二叉树，其结点编号按照层次序（从上到下，从左到右），则除根结点外，满足[i/2 , i, 2i, 2i+1]的规则

二叉树的存储方式

1.直接采用数组存储二叉树，将任意一个二叉树补成完全二叉树，不过这样容易造成空间上的浪费

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
char data[1005];
int flag;//=0 左  =1右孩子 
int find(char fx)
{for (int i = 1; i < 1005; i++){if (data[i] == fx){return i;}}
}
int main()
{int n;char root;printf("读入数据个数：\n");scanf("%d", &n);for (int i = 0; i < 1005; i++){data[i] = ' ';}getchar();printf("读入根结点：\n");scanf("%c", &root);data[1] = root;char x, fx;//数据为x,fx为x的父亲  int fxi, xi;for (int i = 1; i <= n - 1; i++){getchar();printf("读入剩下的结点（x fx flag）：\n");scanf("%c %c %d", &x, &fx, &flag);fxi = find(fx);//寻找父亲结点的下标 if (flag == 0){xi = 2 * fxi;}else {xi = 2 * fxi + 1;}data[xi] = x;}getchar();printf("查找某个结点的孩子父亲结点：\n");scanf("%c", &x);xi = find(x);if (xi == 1){printf("根节点，无父亲节点\n");}else {printf("父亲结点：%c\n", data[xi / 2]);}printf("孩子节点是：%c %c\n", data[2 * xi], data[2 * xi + 1]);return 0;
}

2.二叉链表存储

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
//二叉链表节点结构
typedef struct BTNode {char data;struct BTNode* left;//保存左孩子地址struct BTNode* right;//保存右孩子地址//struct BTNode* fa;//保存父亲的地址 
}BTNode, * BTree;
BTree initBTree(char root)
{BTNode* r = (BTNode*)malloc(sizeof(BTNode));if (r == NULL){printf("空间分配失败\n");return NULL;}r->data = root;r->left = r->right = NULL;//r->fa=NULL; return r;
}
BTNode* find(BTree r, char fx)
{if (r == NULL || r->data == fx){return r;}if (r->left != NULL){BTNode* ans = find(r->left, fx);if (ans != NULL && ans->data == fx){return ans;}}if (r->right != NULL){BTNode* ans = find(r->right, fx);if (ans != NULL && ans->data == fx){return ans;}}return NULL;
}BTree insert(BTree r, char x, char fx, int flag)
{BTNode* f = find(r, fx);if (f == NULL){printf("父亲节点不存在，不能插入\n");}else{BTNode* s = (BTNode*)malloc(sizeof(BTNode));//判断s==NULLs->data = x;s->left = s->right = NULL;//s->fa=f;if (flag == 0){f->left = s;}else {f->right = s;}}return r;
}
int main()
{int n;int flag;//=0 左  =1右孩子 BTree r = NULL;char root;printf("输入结点的总个数：\n");scanf("%d", &n);getchar();printf("输入根节点：\n");scanf("%c", &root);r = initBTree(root);char x, fx;for (int i = 1; i <= n - 1; i++){getchar();printf("输入结点信息（x, fx, flag）：\n");scanf("%c %c %d", &x, &fx, &flag);r = insert(r, x, fx, flag);}getchar();printf("输入要查找的结点：\n");scanf("%c", &x);BTNode* p = find(r, x);if (p != NULL && p->left != NULL){printf("左孩子%c\n", p->left->data);}if (p != NULL && p->right != NULL){printf("右孩子%c\n", p->right->data);}return 0;
}