【数据结构】二叉树

每一个格子都有一个数和一个指针

缺点：

要一个一个找数，比如上图，最多要找5次才能找到数

复杂度是O(n)

这一个二叉树最多只用找三次就能找到数

复杂度是O(log n)

左子结点和右子结点：一个结点的左右两个字结点

父结点：一个结点把它的子结点称为父结点

兄弟结点：一个结点的两个子结点互称为兄弟结点

叶结点就是没有延伸的结点，因为叶子不能再分叉，所以叫叶结点

这里的4,6,7三个结点就是叶子结点

其余的非叶子结点被叫做分支结点

树的深度是所有节点中最大层数被称为树的深度

如图，从一个结点到根结点的所有数都是这个数的祖先结点；反过来，一个节点到子树中所有节点都叫后代节点

1.前序遍历

void Preorder(node *p){

if(!p) return;

visit(p);

Preorder(p->left_son);

Preorder(p->right_son);

}

2.中序遍历

void Inorder(node *p){

if(!p) return;

Inorder(p->left_son);

visit(p);

norder(p->right_son);

}

3.后序遍历

void Postorder(node *p){

if(!p) return;

Postorder(p->left_son);

Postorder(p->right_son);

visit(p);

}

最后点个赞吧，谢谢