二叉树的定义

二叉树是n（n≥0）个结点的有限集合：
① 或者为空二叉树，即 n = 0。
② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。
特点：每个结点至多只有两棵子树 ，且左右子树不能颠倒（二叉树是有序树）

注意区别：度为2的有序树 【就是树和二叉树的区别】

二叉树的五种状态：

特殊二叉树

1. 满二叉树

一棵高度为 h，且含有 2^h - 1 个结点的二叉树。

特点：

1. 只有最后一层有叶子结点。
2. 不存在度为 1 的结点。
3. 若按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 ⌊i / 2⌋（如果有的话）

2. 完全二叉树

当且仅当其每个结点都与高度为 h 的满二叉树中编号为1～n的结点一一对应时，称为完全二叉树。

特点：

1. 只有最后两层可能有叶子结点。
2. 最多只有一个度为 1 的结点。
3. 若按层序从 1 开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父节点为 ⌊i / 2⌋
4. i ≤ ⌊ n / 2 ⌋ 为分支结点， i > ⌊ n / 2 ⌋ 为叶子结点。

3. 二叉排序树

① 是空二叉树
② 或者是具有如下性质的二叉树：
            左子树上所有结点的关键字均小于根结点的关键字；
            右子树上所有结点的关键字均大于根结点的关键字。

二叉树排序树建立及平衡处理

application/x-rar 4星 超过75%的资源 40KB

下载

4. 平衡二叉树

树上任一结点的左子树和右子树的深度之差不超过 1。

平衡二叉树能有更高的搜索效率

二叉树的性质

1. 设非空二叉树中度为 0、1 和 2 的结点个数分别为 n0​、 n1​ 和 n2​，则 n0 = n2 + 1

   

2. 二叉树第 i 层至多有 2ⁱ⁻¹ 个结点（i≥1）。

3. 高度为 h 的二叉树至多有 2^h − 1个结点（满二叉树）。

4. 具有 n 个（n>0）结点的完全二叉树的高度 h 为 ⌈log₂ ( n + 1 )⌉

   

5. 对于完全二叉树，设非空二叉树中度为 0、1 和 2 的结点个数分别为 n0​、 n1​ 和 n2
   则完全二叉树最多只有一个度为1的结点，即n₁=0 或 n₁=1

   
   .

二叉树的存储结构

二叉排序树与平衡二叉树的实现课程设计

doc 0星 超过10%的资源 204KB

下载

1. 二叉树的顺序存储

定义一个长度为 MaxSize 的数组 t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。让第一个位置空缺，保证数组中下标和结点编号一致。

#define MaxSize 100
struct TreeNode{  
    ElemType value; //结点中的数据元素  
    bool isEmpty;	//结点是否为空
}

//初始化树T
bool initTree(TreeNode T[]){  
    for(int i=0; i<MaxSize; i++){  
        T[i].isEmpty=true; 
    }  
    return true;
}

void test(){   
    struct TreeNode T[MaxSize];  
    initTree(T);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

这样可以使用二叉树的性质求一些问题：

• 结点 i 的左孩子： 2i
• 结点 i 的右孩子： 2i+1
• 结点 i 的父节点： ⌊ i / 2 ⌋
• 结点 i 的层次： ⌈ log₂ ( i + 1 ) ⌉

但是如果不是完全二叉树，依然按层序将各节点顺序存储，那么将无法从结点编号反映出结点间的逻辑关系。可以将二叉树中的结点编号与完全二叉树对应起来存储，不过这样会浪费很多内存空间。因此，。二叉树的顺序存储结构，只适合存储完全二叉树

2. 二叉树的链式存储

typedef struct BiTNode{  
    ElemType data;	
    struct BiTNode *lchild, *rchild;	
}BiTNode, *BiTree;

//初始化
bool initTree(BiTree &root){
    root = (BiTree)malloc(sizeof(BiTNode));   
    if(root == NULL)     
        return false;
    root->lchild = NULL; 
    root->rchild = NULL;
    return true;
}

void test{  
    BiTree root = NULL; 	
    initTree(root);
    ...
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二叉树的链式存储可以非常方便的找到指定结点的左右孩子，但是找到指定结点的父结点却非常困难，只能从根节点开始遍历寻找。
因此，如果寻找父结点的需求比较多，也可以加上父结点指针形成三叉链表。