1.为什么会有树？因为当有大量的输入数据时，链表的线性访问时间就显得略长了。而树结构，其大部分操作的运行时间平均为O(logN)。

2.树的实现并不难，几行代码就搞定了。

struct@H_404_7@ TreeNode
{
    Object@H_404_7@ element;
    TreeNode *firstChild;
    TreeNode *nextSibling;
}

3.遍历形式：

// 中序遍历二叉树@H_404_7@
void@H_404_7@ inorder(tree_pointer ptr)
{
    if@H_404_7@(ptr)
    {
        inorder(ptr->@H_404_7@left_child);
        printf("%d"@H_404_7@,ptr->@H_404_7@data@H_404_7@);
        inorder(ptr->@H_404_7@right_child);
    }
}

// 前序遍历二叉树@H_404_7@
void@H_404_7@ preorder(tree_pointer ptr)
{
    if@H_404_7@(ptr)
    {
        printf("%d"@H_404_7@,ptr->@H_404_7@data@H_404_7@);
        preorder(ptr->@H_404_7@left_child);
        preorder(ptr->@H_404_7@right_child);
    }
}

// 后序遍历二叉树@H_404_7@
void@H_404_7@ postorder(tree_pointer ptr)
{
    if@H_404_7@(ptr)
    {
        postorder(ptr->@H_404_7@left_child);
        postorder(ptr->@H_404_7@right_child);
        printf("%d"@H_404_7@,ptr->@H_404_7@data@H_404_7@);
    }
}

4.迭代的中序遍历

void@H_404_7@ iter_inorder(tree_pointer node)
{
    int@H_404_7@ top=-1@H_404_7@;
    tree_pointer stack@H_404_7@[MAX_STACK_SIZE];
    for@H_404_7@(;;)
    {
        for@H_404_7@(;node;node=node->left_child)
            add(&top,node);
        node=delete@H_404_7@(&top);
        if@H_404_7@(!node)
            break@H_404_7@;
        printf@H_404_7@("%d"@H_404_7@,node->data);
        node=node->right_child;
    }
}

5.二叉树的层序遍历

void level_order(tree_pointer ptr)
{
    int@H_404_7@ front=rear=0@H_404_7@;
    tree_pointer queue[MAX_QUEUE_SIZE];
    if@H_404_7@(!ptr)
        return@H_404_7@;
    addq(front,&rear,ptr)@H_404_7@;
    for@H_404_7@(;;)
    {
        ptr=delete@H_404_7@q(&front,rear)@H_404_7@;
        if@H_404_7@(ptr)
        {
            printf@H_404_7@("%d@H_404_7@"@H_404_7@,ptr->data);
            if@H_404_7@(ptr->left_child)
                addq(front,ptr->left_child)@H_404_7@;
            if@H_404_7@(ptr->right_child)
                addq(front,ptr->right_child)@H_404_7@;
        }
        else@H_404_7@
            break@H_404_7@;
    }
}

6.二叉树的复制

tree_pointer copy(tree_pointer original)
{
    tree_pointer temp;
    if@H_404_7@(original)
    {
        temp=@H_404_7@(tree_pointer) malloc(sizeof(node));
        if@H_404_7@(IS_FULL(temp))
        {
            fprintf(stderr,"The memory is full\n"@H_404_7@);
            exit(1@H_404_7@);
        }
        temp->@H_404_7@left_child=@H_404_7@copy(original->@H_404_7@left_child);
        tmep->@H_404_7@right_child=@H_404_7@copy(original->@H_404_7@right_child);
        temp->@H_404_7@data@H_404_7@=@H_404_7@original->@H_404_7@data@H_404_7@;
        return@H_404_7@ temp;
    }
    return@H_404_7@ NULL@H_404_7@;
}

7.判断二叉树的等价性

int equal@H_404_7@(tree_pointer first@H_404_7@,tree_pointer second@H_404_7@)
{
 return@H_404_7@ ((!first@H_404_7@&&!second@H_404_7@)||(first@H_404_7@ && second@H_404_7@ && (first@H_404_7@->data == second@H_404_7@->data) && 
            equal@H_404_7@(first@H_404_7@->left_child,second@H_404_7@->left_child) &&
            equal@H_404_7@(first@H_404_7@->right_child,second@H_404_7@->right_child));
}

8.寻找结点的中序后继

threaded_pointer insucc(threaded_pointer tree)
{
    threaded_pointer temp;
    temp=@H_404_7@tree->@H_404_7@right_child;
    if@H_404_7@(!@H_404_7@tree->@H_404_7@right_thread)
        while@H_404_7@(!@H_404_7@temp->@H_404_7@left_thread)
            temp=@H_404_7@temp->@H_404_7@left_child;
    return@H_404_7@ temp;
}

9.线索二叉树的中序遍历

void tinorder(threaded_pointer tree)
{
    threaded_pointer temp=tree;
    for@H_404_7@(;;)
    {
        temp=insucc(temp);
        if@H_404_7@(temp==tree)
            break@H_404_7@;
        printf@H_404_7@("%3c@H_404_7@"@H_404_7@,temp->data);
    }
}

10.线索二叉树的右插入操作

void@H_404_7@ insert_right(threaded_pointer parent@H_404_7@,threaded_pointer child)
{
     threaded_pointer temp;
     child->@H_404_7@right_child=@H_404_7@parent@H_404_7@->@H_404_7@right_child;
     child->@H_404_7@right_thread=@H_404_7@parent@H_404_7@->@H_404_7@right_thread;
     child->@H_404_7@left_child=@H_404_7@parent@H_404_7@;
     child->@H_404_7@left_thread=@H_404_7@TRUE@H_404_7@;
     parent@H_404_7@->@H_404_7@right_child=@H_404_7@child;
     parent@H_404_7@->@H_404_7@right_thread=@H_404_7@FALSE@H_404_7@;
     if@H_404_7@(!@H_404_7@child->@H_404_7@right_thread)
     {
         temp=@H_404_7@insucc(child);
         temp->@H_404_7@left_child=@H_404_7@child;
     }
}

感谢您的访问，希望对您有所帮助。

欢迎大家关注或收藏、评论或点赞。

为使本文得到斧正和提问，转载请注明出处：
http://blog.csdn.net/nomasp