二叉树

2023-12-29 14:51:58

性质：

1.i > 1的结点，其父结点是i/2

2.如果结点i有孩子，则左孩子是2i，右孩子是2i+1

二叉树的存储结构

struct node{
　　int value;　　  //结点的值
　　node *l, *r;　　//指向左、右子结点　　
};

二叉树的遍历

1.宽度优先遍历

　　队列

2.深度优先遍历

（先中后序的意思是指父结点的遍历顺序）

　　1>先序遍历中左右

　　　　伪代码：

void preorder(node *root){
    cout<<root->value;
    preorder(root->l);
    preorder(root->r);
}

　　2>中序遍历左中右

　　　　伪代码：

void inorder(node *root){
    inorder(root->l);
    cout<<root->value;
    inorder(root->r);
}

　　3>后序遍历左右中

　　　　伪代码：

void postorder(node *root){
    postorder(root->l);
    postorder(root->r);
    cout<<root->value;
}

题目推荐

hdu1710

码农公寓