笔记·C++数据结构：二叉树

树结构

一棵树是由n(n > 0) 个元素组成的有限组合，其中

每一个元素被称为一个节点(node);
有一个特定的节点，被称为根节点或树根(root);
除根节点外，其余节点能分成m (m >= 0) 个互相不相交的有限集合。其中每个子集又都是一棵树，这些子集被称为子树;
树是递归定义的；
一棵树至少有一个节点，这个节点就是根节点；
一个节点的子树个数，称为这个根节点的度，度为0的节点称为叶节点，树中各节点的度的最大值称为这棵树的度（一棵树的子树的数目）；
一棵树中所有的节点的层次的最大值称为树的深度（树有几层）；

二叉树

定义：

树的每个节点最多有两个子节点，每个节点的子节点分别称为左孩子、右孩子，它的两颗子树分别称为左子树和右子树。

特点

在二叉树的第i层上最多有 $2^{i-1}(i \geqslant 1)$ 个节点
深度为k的二叉树最多有 $2^{k-1}(k \geqslant 1)$ 个节点
满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，在满二叉树中，每一层上的节点数都达到最大值；
完全二叉树：除最后一层外，每一层上的节点数都达到最大值，在最后一层只缺少右边的若干节点。

五种形态

空二叉树
仅有根节点的二叉树
右子树为空的二叉树
左右子树均非空的二叉树
左子树为空的二叉树

二叉树的遍历

先序遍历

执行过程:

访问根节点；
遍历左子树
遍历右子树

如上图，先序遍历的遍历过程是：
1-2-4-7-5-3-6-8-9

根左右

中序遍历

执行过程:

遍历左子树
访问根节点
遍历右子树

如上图，中序遍历的遍历过程是：
7-4-2-5-1-3-8-6-9

左根右

后序遍历

执行过程:

遍历左子树
遍历右子树
访问根节点

如上图，中序遍历的遍历过程是：
7-4-5-2-8-9-6-3-1

左右根

二叉树的建立

特点

节点间关系蕴含在其储存位置中
仅适用于存满二叉树和完全二叉树
浪费空间

建立

创建结构体，储存树的各个节点。

struct node{
    char value;
    int lchild, rchild;
    //lchild rchild 可以使用指针存储
}

两个例子

输入先序遍历序列建立二叉树，输出后序遍历结果

//输入先序遍历序列建立二叉树，输出后序遍历结果
//空节点用period间隔
#include <iostream>
#include <cstdio>
using namespace std;

struct node{
    char value;
    int lchild,rchild;
}data[101];



int root;//根节点
int cnt;//各节点序号
char ch;//输入字符
const char EMPTY = '.';

//建立二叉树
int buildTree(int bt){
    ch = getchar();
    if(ch == EMPTY){
        bt = 0;
        return bt;
    }
    else{
        bt = ++cnt;
        data[bt].value = ch;
        data[bt].lchild = data[bt].rchild = 0;
        data[bt].lchild = buildTree(bt);
        data[bt].rchild = buildTree(bt);
    }
    return bt;
}

//后序遍历
void postorder(int bt){
    if(bt){
        postorder(data[bt].lchild);
        postorder(data[bt].rchild);
        cout<<data[bt].value;
    }
}

int main(){
    root = 0;
    cnt = 0;
    root = buildTree(0);
    postorder(root);

    return 0;
}

输入一串二叉树，用先序遍历的格式输出，空节点用*表示

//输入一串二叉树，用先序遍历的格式输出，空节点用*表示
#include <iostream>
#include <cstdio>
using namespace std;

struct node{
    char parent;
    int lchild,rchild;
}data[101];
//此处使用结构体数组下标作为各个节点的值


int root;//根节点
int cnt;//各节点序号
char ch;//输入字符
const char EMPTY = '*';

//后序遍历
void preorder(int root){
    if(root!=0){
        cout<<(char)(root-1+'a');
        preorder(data[root].lchild);
        preorder(data[root].rchild);
    }
}

int main(){
    int n;
    cin>>n;
    for(int i = 1;i<=n;i++){
        char a,b,c;
        cin>>a>>b>>c;
        if(b!=EMPTY){
            data[b-'a'+1].parent=a-'a'+ 1;
            data[a-'a'+1].lchild=b-'a'+1;
        }
        if(c!=EMPTY){
            data[c-'a'+1].parent=a-'a'+1;
            data[a-'a'+1].rchild=c-'a'+1;
        }
    }

    int root;

    for(int i=1;i<=n;i++){
        if((data[i].parent==0)&&(data[i].lchild||data[i].rchild)){
            root=i;
            break;
        }
    }

    preorder(root);
    cout<<endl;

    return 0;
}

未完待续……

参考资料

二叉树的详细实现 (C++) - WindSun

C/C++ 二叉树 - Void_Caller