返回顶部

收藏

C++算法之排序二叉树

更多

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

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;  
}  

                                    分析:我们看到,二叉树节点的创建和我们看到的链表节点、堆栈节点创建没有什么本质的区别。首先需要为节点创建内存,然后对内存进行初始化处理。最后将输入参数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);  
}  

                                    分析:我们的查找是按照递归迭代进行的。因为整个二叉树是一个排序二叉树,所以我们的数据只需要和每一个节点依次比较就可以了,如果数值比节点数据小,那么向左继续遍历;反之向右继续遍历。如果遍历下去遇到了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);  
}  

                                    分析:和上面查找数据一样,统计的工作也比较简单。如果是节点指针,那么直接返回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);  
    }  
}  

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

5)统计树的高度
int calculate_height_of_tree(const TREE_NODE* pTreeNode)  
{  
    int left, right;  
    if(NULL == pTreeNode)  
        return 0;  

    left = calculate_height_of_tree(pTreeNode->left_child);  
    right = calculate_height_of_tree(pTreeNode->right_child);  
    return (left > right) ? (left + 1) : (right + 1);  
}  

                                    分析:树的高度其实是指所有叶子节点中,从根节点到叶子节点的最大高度可以达到多少。当然,程序中表示得已经很明白了,如果节点为空,那么很遗憾,节点的高度为0;反之如果左子树的高度大于右子树的高度,那么整个二叉树的节点高度就是左子树的高度加上1;如果右子树的高度大于左子树的高度,那么整个二叉树的高度就是右子树的高度加上1。计算树的高度在我们设计平衡二叉树的时候非常有用,特别是测试的时候,希望大家多多理解,熟练掌握。

总结: 1)二叉树是所有树的基础,后续的平衡二叉树、线性二叉树、红黑树、复合二叉树、b树、b+树都以此为基础,希望大家好好学习; 2)二叉树很多的操作是和堆栈紧密联系在一起的,如果大家暂时理解不了递归,可以用循环或者堆栈代替; 3)实践出真知,大家可以自己对排序二叉树的代码多多练习。不瞒大家说,我个人写平衡二叉树不下20多遍,即使这样也不能保证每次都正确;即使这样,我每次写代码的都有不同的感觉。

标签:排序二叉树,链表,C++

收藏

0人收藏

支持

0

反对

0

相关聚客文章
  1. mouse 发表 2015-07-31 10:16:54 c++ 链表翻转
  2. coder4 发表 2013-02-02 15:15:20 c++ tr1和Boost中,tuple、tie的用法。
  3. Dave Abrahams 发表 2011-11-04 08:16:16 Having it all: Pythy syntax for C++
  4. Herb Sutter 发表 2012-04-30 23:19:59 C++ Libraries: Casablanca
  5. Herb Sutter 发表 2012-09-18 20:53:01 C&B 2012 panel posted: Ask Us Anything!
  6. Herb Sutter 发表 2013-01-16 00:20:29 Videos: Panel, and C++ Concurrency
  7. Eric Battalio 发表 2013-03-11 18:34:00 Advanced Developers Conference 2013: C++
  8. alex 发表 2013-04-13 08:23:26 Dynamic C++ in a nutshell
  9. 博主 发表 2009-12-30 16:00:00 C++如何判断声明为基类的对象,是否某子类型的实例?
  10. maipianshuo 发表 2013-06-11 04:14:53 [C++技巧篇1]enable_if,lambda
  11. admin 发表 2012-09-28 07:50:16 基于XMPP协议IM技术选型
  12. mortoray 发表 2013-08-13 04:09:26 We don’t need a string type

发表评论