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

《一步一步写算法(之排序二叉树)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、软件英才网软件行业驰名招聘网站一步一步写算法（之排序二叉树）前面我们讲过双向链表的数据结构。每一个循环节点有两个指针，一个指向前面一个节点，一个指向后继节点，这样所有的节点像一颗颗珍珠一样被一根线穿在了一起。然而今天我们讨论的数据结构却有一点不同，它有三个节点。它是这样定义的：[cpp]viewplaincopy1typedefstruct_TREE_NODE2{3intdata;4struct_TREE_NODE*parent;5struct_TREE_NODE*left_child;6struct_TREE_NODE*right

2、_child;7}TREE_NODE;根据上面的数据结构，我们看到每一个数据节点都有三个指针，分别是：指向父母的指针，指向左孩子的指针，指向右孩子的指针。每一个节点都是通过指针相互连接的。相连指针的关系都是父子关系。那么排序二叉树又是什么意思呢？其实很简单，只要在二叉树的基本定义上增加两个基本条件就可以了：（1）所有左子树的节点数值都小于此节点的数值；（2）所有右节点的数值都大于此节点的数值。既然看到了节点的定义，那么我们并可以得到，只要按照一定的顺序遍历，可以把二叉树中的节点按照某一个顺序打印出来。那么，节点的创建、查找、遍历是怎

3、么进行的呢，二叉树的高度应该怎么计算呢？我们一一道来。1）创建二叉树节点[cpp]viewplaincopy8TREE_NODE*create_tree_node(intdata)9{10TREE_NODE*pTreeNode=NULL;11pTreeNode=(TREE_NODE*)malloc(sizeof(TREE_NODE));12assert(NULL!=pTreeNode);1314memset(pTreeNode,0,sizeof(TREE_NODE));15pTreeNode->data=data;16returnp

4、TreeNode;17}分析：我们看到，二叉树节点的创建和我们看到的链表节点、堆栈节点创建没有什么本质的区别。首先需要为节点创建内存，然后对内存进行初始化处理。最后将输入参数data输入到tree_node当中即可。有需要请联系我们软件英才网软件行业驰名招聘网站2）数据的查找[cpp]viewplaincopy1TREE_NODE*find_data_in_tree_node(constTREE_NODE*pTreeNode,intdata)2{3if(NULL==pTreeNode)4returnNULL;56if(data==p

5、TreeNode->data)7return(TREE_NODE*)pTreeNode;8elseif(datadata)9returnfind_data_in_tree_node(pTreeNode->left_child,data);10else11returnfind_data_in_tree_node(pTreeNode->right_child,data);12}分析：我们的查找是按照递归迭代进行的。因为整个二叉树是一个排序二叉树，所以我们的数据只需要和每一个节点依次比较就可以了，如果数值比节点数据

6、小，那么向左继续遍历；反之向右继续遍历。如果遍历下去遇到了NULL指针，只能说明当前的数据在二叉树中还不存在。3）数据统计[cpp]viewplaincopy13intcount_node_number_in_tree(constTREE_NODE*pTreeNode)14{15if(NULL==pTreeNode)16return0;1718return1+count_node_number_in_tree(pTreeNode->left_child)19+count_node_number_in_tree(pTreeNode->

7、right_child);20}分析：和上面查找数据一样，统计的工作也比较简单。如果是节点指针，那么直接返回0即可，否则就需要分别统计左节点树的节点个数、右节点树的节点个数，这样所有的节点总数加起来就可以了。4）按照从小到大的顺序打印节点的数据[cpp]viewplaincopy21voidprint_all_node_data(constTREE_NODE*pTreeNode)22{23if(pTreeNode){有需要请联系我们软件英才网软件行业驰名招聘网站1print_all_node_data(pTreeNode->left

8、_child);2printf("%d",pTreeNode->data);3print_all_node_data(pTreeNode->right_child);4}5}分析：因为二叉树本身的特殊性，按顺序打印二叉树的函数本身