【数据结构】树和二叉树

【1】树的概念

树（Tree）是n（n≥0）个节点的有限集合T，它满足两个条件 ：
有且仅有一个特定的称为根（Root）的节点；
其余的节点可以分为m（m≥0）个互不相交的有限集合T1、T2、……、Tm，
其中每一个集合又是一棵树，并称为其根的子树（Subtree）。

【3】度数

一个节点的子树的个数称为该节点的度数，一棵树的度数是指该树中节点的最大度数。

【4】路径

一个节点系列k1,k2,……,ki,ki+1,kj,并满足ki是ki+1的父节点，就称为一条从k1
到kj的路径，路径的长度为j-1,即路径中的边数。

【5】层数以及树的高度或深度

节点的层数等于父节点的层数加一，根节点的层数定义为一。
树中节点层数的最大值称为该树的高度或深度。

【6】树的逻辑结构

树中任何节点都可以有零个或多个直接后继节点（子节点），但至多只有一个直接前趋
节点（父节点），根节点没有前趋节点，叶节点没有后继节点。

【7】二叉树的定义

二叉树（Binary Tree）是n（n≥0）个节点的有限集合，它或者是空集（n＝0），或者是
由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。
二叉树与普通有序树不同，二叉树严格区分左孩子和右孩子，即使只有一个子节点也要区分左右。

【8】二叉树的性质

二叉树第i（i≥1）层上的节点最多为2~（i-1）个。
深度为k（k≥1）的二叉树最多有2~k－1个节点。
在任意一棵二叉树中，树叶的数目比度数为2的节点的数目多一。
    总节点数为各类节点之和：n = n0 + n1 + n2  
    总节点数为所有子节点数加一：n = n1 + 2*n2 + 1
    故得：n0 = n2 + 1 ;
满二叉树 ：深度为k（k≥1）时有2~k－1个节点的二叉树
完全二叉树 ：只有最下面两层有度数小于2的节点，且最下面一层的叶节点集中在最左边的若干位置上。

【9】二叉树的存储

完全二叉树节点的编号方法是从上到下，从左到右，根节点为1号节点。
设完全二叉树的节点数为n，某节点编号为i
当2*i≤n时，有左孩子，其编号为2*i,否则没有左孩子，本身是叶节点;
当2*i＋1≤n时，有右孩子，其编号为2*i+1,否则没有右孩子；

注意：如果根节点编号为0，则判断左右子树时使用2*i+1和2*i+2

【10】二叉树的遍历

先序遍历：先访问树根，再访问左子树，最后访问右子树  根 左 右
中序遍历：先访问左子树，再访问树根，最后访问右子树  左 根 右
后序遍历：先访问左子树，再访问右子树，最后访问树根   左 右 根

代码

/* binary_tree.h */
#ifndef BINARY_TREE_H
#define BINARY_TREE_H

#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"
typedef int datatype;
struct bt_node
{
    datatype data;
    struct bt_node *lchild;
    struct bt_node *rchild;
};

extern struct bt_node *binary_tree_create(int node_num,int root);
extern void binary_tree_preorder(struct bt_node *root);
extern void binary_tree_inorder(struct bt_node *root);
extern void binary_tree_postorder(struct bt_node *root);
extern void binary_tree_level(struct bt_node *root);

#endif // BINARY_TREE_H

/* binary_tree.c */
#include "binary_tree.h"

struct bt_node *binary_tree_create(int node_num,int root)
{
    struct bt_node *node=(struct bt_node *)malloc(sizeof(struct bt_node));
    node->data=root;
    if(root*2<=node_num)
        node->lchild=binary_tree_create(node_num,root*2);
    else
        node->lchild=NULL;

    if(root*2+1<=node_num)
        node->rchild=binary_tree_create(node_num,root*2+1);
    else
        node->rchild=NULL;
    return node;

}

void binary_tree_preorder(struct bt_node *root)
{
    if(root==NULL)
        return;
    printf("%d ",root->data);
    binary_tree_preorder(root->lchild);
    binary_tree_preorder(root->rchild);
}

void binary_tree_inorder(struct bt_node *root)
{
    if(root==NULL)
        return;
    binary_tree_inorder(root->lchild);
    printf("%d ",root->data);
    binary_tree_inorder(root->rchild);
}


void binary_tree_postorder(struct bt_node *root)
{
    if(root==NULL)
        return;
    binary_tree_postorder(root->lchild);
    binary_tree_postorder(root->rchild);
    printf("%d ",root->data);
}


void binary_tree_level(struct bt_node *root)
{
    struct bt_node *tmp;
    struct linkqueue *q=linkqueue_create();
    linkqueue_push(q,root);
    while(!linkqueue_empty(q))
    {
        tmp=linkqueue_pop(q);
        printf("%d ",tmp->data);
        if(tmp->lchild!=NULL)
            linkqueue_push(q,tmp->lchild);
        if(tmp->rchild!=NULL)
            linkqueue_push(q,tmp->rchild);
    }
}