当前位置:编程学习 > C/C++ >>

一步一步写算法(之排序二叉树)

 

【 声明:版权所有,欢迎转载,请勿用于商业用途。  联系信箱:feixiaoxing @163.com】

 

 

 

 

    前面我们讲过双向链表的数据结构。每一个循环节点有两个指针,一个指向前面一个节点,一个指向后继节点,这样所有的节点像一颗颗珍珠一样被一根线穿在了一起。然而今天我们讨论的数据结构却有一点不同,它有三个节点。它是这样定义的:

 

 

typedef struct _TREE_NODE 

    int data; 

    struct _TREE_NODE* parent; 

    struct _TREE_NODE* left_child; 

    struct _TREE_NODE* right_child; 

}TREE_NODE; 

typedef struct _TREE_NODE

{

       int data;

       struct _TREE_NODE* parent;

       struct _TREE_NODE* left_child;

       struct _TREE_NODE* right_child;

}TREE_NODE;    根据上面的数据结构,我们看到每一个数据节点都有三个指针,分别是:指向父母的指针,指向左孩子的指针,指向右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。那么排序二叉树又是什么意思呢?其实很简单,只要在二叉树的基本定义上增加两个基本条件就可以了:(1)所有左子树的节点数值都小于此节点的数值;(2)所有右节点的数值都大于此节点的数值。

 

    既然看到了节点的定义,那么我们并可以得到,只要按照一定的顺序遍历,可以把二叉树中的节点按照某一个顺序打印出来。那么,节点的创建、查找、遍历是怎么进行的呢,二叉树的高度应该怎么计算呢?我们一一道来。

 

    1)创建二叉树节点

 

 

TREE_NODE* create_tree_node(int data) 

    TREE_NODE* pTreeNode = NULL; 

    pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE)); 

    assert(NULL != pTreeNode); 

 

    memset(pTreeNode, 0, sizeof(TREE_NODE)); 

    pTreeNode->data = data; 

    return pTreeNode; 

TREE_NODE* create_tree_node(int data)

{

       TREE_NODE* pTreeNode = NULL;

       pTreeNode = (TREE_NODE*)malloc(sizeof(TREE_NODE));

       assert(NULL != pTreeNode);

 

       memset(pTreeNode, 0, sizeof(TREE_NODE));

       pTreeNode->data = data;

       return pTreeNode;

}    分析:我们看到,二叉树节点的创建和我们看到的链表节点、堆栈节点创建没有什么本质的区别。首先需要为节点创建内存,然后对内存进行初始化处理。最后将输入参数data输入到tree_node当中即可。

 

 

 

 

    2)数据的查找

 

 

TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data) 

    if(NULL == pTreeNode) 

        return NULL; 

 

    if(data == pTreeNode->data) 

        return (TREE_NODE*)pTreeNode; 

    else if(data < pTreeNode->data) 

        return find_data_in_tree_node(pTreeNode->left_child, data); 

    else 

        return find_data_in_tree_node(pTreeNode->right_child, data); 

TREE_NODE* find_data_in_tree_node(const TREE_NODE* pTreeNode, int data)

{

       if(NULL == pTreeNode)

              return NULL;

 

       if(data == pTreeNode->data)

              return (TREE_NODE*)pTreeNode;

       else if(data < pTreeNode->data)

              return find_data_in_tree_node(pTreeNode->left_child, data);

       else

              return find_data_in_tree_node(pTreeNode->right_child, data);

}    分析:我们的查找是按照递归迭代进行的。因为整个二叉树是一个排序二叉树,所以我们的数据只需要和每一个节点依次比较就可以了,如果数值比节点数据小,那么向左继续遍历;反之向右继续遍历。如果遍历下去遇到了NULL指针,只能说明当前的数据在二叉树中还不存在。

 

 

 

 

    3)数据统计

 

 

int count_node_number_in_tree(const TREE_NODE* pTreeNode) 

    if(NULL == pTreeNode) 

        return 0; 

 

    return 1 + count_node_number_in_tree(pTreeNode->left_child) 

        + count_node_number_in_tree(pTreeNode->right_child); 

int count_node_number_in_tree(const TREE_NODE* pTreeNode)

{

       if(NULL == pTreeNode)

              return 0;

 

       return 1 + count_node_number_in_tree(pTreeNode->left_child)

              + count_node_number_in_tree(pTreeNode->right_child);

}    分析:和上面查找数据一样,统计的工作也比较简单。如果是节点指针,那么直接返回0即可,否则就需要分别统计左节点树的节点个数、右节点树的节点个数,这样所有的节点总数加起来就可以了。

 

 

 

 

    4)按照从小到大的顺序打印节点的数据

 

 

void print_all_node_data(const TREE_NODE* pTreeNode) 

    if(pTreeNode){ 

        print_all_node_data(pTreeNode->left_child); 

        printf("%d\n", pTreeNode->data); 

        print_all_node_data(pTreeNode->right_child); 

    } 

void print_all_node_data(const TREE_NODE* pTreeNode)

{

       if(pTreeNode){

              print_all_node_data(pTreeNode->left_child);

              printf("%d\n", pTreeNode->data);

              print_all_node_data(pTreeNode->right_child);

       }

}    分析:因为二叉树本身的特殊性,按顺序打印二叉树的函数本身也比较简单。首先打印左子树的节点,然后打印本节点的数值,最后打印右子树节点的数值,这样所有节点的数值就都可以打印出来了。

 

 

 

补充:软件开发 , C语言 ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,