相关概念：
左高树(leftist tree)将树中的节点分为两类：
外部节点：用于代替树中的空子树；其余节点均叫做内部节点．内部节点就是我们所能看到的树中的每个真实节点，如果某个节点的左子树为空，那它的这个左子树就是外部节点．外部节点的引入，其实主要是为了下面s(x)这个概念的计算，并不具备其它实际意义．
s(x)为节点x至它的子树的外部节点的所有路径中最短的那一条．比如根节点30，左子树为20(内部节点)，右子树为空(外部节点)，则根节点到左子树的路径为：30 -> 20 -> 外部节点，路径为２；根节点到右子树的路径为：30->外部节点，路径为１．因此，根节点30的s(x)＝１.
根据上面s(x)的定义可知，若x是外部节点，则s(x)=0；若x为内部节点，则s(x)=min{s(left_child), s(right_child)} + 1．
高度优先左高树(Height-Biased Leftist Tree, HBLT)：当且仅当一棵二叉树的任何一个内部，其左孩子的s(x)值大于等于右孩子的s(x)值．
最大HBLT，即同时又是最大树(每个节点的值都大于或等于其子节点值的树)的HBLT．
MaxHBLT_Main.c即是一个最大HBLT的实现，核心函数就是hblt_merge()，即将两个最大HBLT合并成一个HBLT，其中就用到了s(x)这个概念．
运行结果：
$ ./MaxHBLT_Main **********HBLT*********data=11,s=2 left=9 right=2 data=9,s=1 left=7 data=7,s=1 left=1 data=1,s=1 data=2,s=1
#include <stdio.h>#include <stdlib.h>#include <string.h>/** 描述高度优先左高树节点的数据结构*/struct hblt_node {int data; /* 节点存储的是int值 */int s;/* s(x)为从节点x到它的子树的外部节点的所有路径中最短的值 */struct hblt_node *left;struct hblt_node *right;};/** malloc and init for struct hblt_node **/static struct hblt_node * hblt_node_create(int data){struct hblt_node *node;node = malloc(sizeof(struct hblt_node));if(NULL == node)return NULL;memset(node, 0, sizeof(struct hblt_node));node->data = data;node->s= 1;node->left = NULL;node->right = NULL;}/** 销毁给定节点及其所有子树*/static void hblt_destroy(struct hblt_node **tree){struct hblt_node *root = *tree; if(NULL == root)return;if(NULL == root->left && NULL == root->right) {free(root);root = NULL;return;}if(root->left) hblt_destroy(&root->left);if(root->right)hblt_destroy(&root->right);}/** 计算给定HBLT的s(x)值：从节点x到它的子树的外部节点的所有路径中最短的值*/static int get_s_of_hblt(struct hblt_node *n){struct hblt_node *left, *right;int s_left, s_right, result;if(NULL == n)return 0;left = n->left;right = n->right;if(NULL == left || NULL == right)return 1;s_left = get_s_of_hblt(left);s_right = get_s_of_hblt(right);result = (s_left < s_right)?s_left:s_right;return (result+1);}static struct hblt_node * hblt_merge(struct hblt_node *n1, struct hblt_node *n2){struct hblt_node *parent, *old_right, *new_right, *temp;int s_left, s_right, s_smaller;if(!n1 && !n2)return NULL;if(n1 && !n2)return n1;if(!n1 && n2)return n2;/* 选择值大的节点作为根节点 */if(n1->data > n2->data) {parent = n1;old_right = n1->right;new_right = n2;} else {parent = n2;old_right = n2->right;new_right = n1;}/* 将根节点的右子树和待插入的树进行合并 */parent->right = hblt_merge(new_right, old_right);/* 判断左右子数的s(x)，如果右边比左边大，则交换左右子树 */s_left = get_s_of_hblt(parent->left);s_right = get_s_of_hblt(parent->right);if( s_right > s_left ) {temp= parent->left;parent->left = parent->right;parent->right = temp;s_smaller= s_left;} else {s_smaller= s_right;}parent->s = s_smaller + 1;return parent;}static void print_hblt(struct hblt_node *n){if(NULL == n)return;printf("data=%d,s=%d ", n->data, n->s);if(n->left)printf("left=%d ", n->left->data);if(n->right)printf("right=%d ", n->right->data);printf("\n");print_hblt(n->left);print_hblt(n->right);}int main(){struct hblt_node *n1, *n2, *n3, *n4, *n5, *temp;n1 = hblt_node_create(7);n2 = hblt_node_create(1);n3 = hblt_node_create(9);n4 = hblt_node_create(11);n5 = hblt_node_create(2);temp = hblt_merge(n1, n2);temp = hblt_merge(temp, n3);temp = hblt_merge(temp, n4);temp = hblt_merge(temp, n5);printf("**********HBLT*********\n");print_hblt(temp);hblt_destroy(&temp);return 0;}
