[科普中国]-空二叉树

二叉树是n（n≥0）个结点的有限集合。n=0的树称为空二叉树。n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。1

概念二叉树是n（n≥0）个结点的有限集合。n=0的树称为空二叉树。n>0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。1

二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有五种基本形态：1

(1)空二叉树2

(2)只有一个根结点的二叉树2

(3)只有左子树2

(4)只有右子树2

(5)完全二叉树1

二叉树的基本运算1）创建二叉树 CreatBTNode(*b,*str)1

2）查找结点 FindNode(*b,x)3

采用递归算法在二叉树b中查找值为x的结点，找到后返回其指针，否则返回NULL。2

在查找前，通常先判断二叉树是否为空，若为空，则返回查找失败。2

3）找孩子结点1

4）求树的高度3

5）输出二叉树1

通常也需判断二叉树是否为空。2

二叉树定义//二叉树节点定义struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};构造空树//清空或销毁二叉树void ClearTree(PTree *T){ T->n = NULL;}如何判断TreeEmpty(PTree *T){ /* 初始条件：树T存在。操作结果：若T为空树，则返回TRUE，否则返回FALSE */ return T->n==NULL;} 二叉树拓展（1）线索二叉树

在节点空指针域存放前驱和后继节点的指针，加上线索标志域区分是线索指针还是child指针；建立线索二叉树，实质上就是遍历一颗二叉树，在相应的指针域进行操作。2

（2）二叉排序树

（3）最优二叉树（哈夫曼树）2

对于一组有确定权值的叶子节点，构造的具有最小带权路径长度的二叉树（典型应用：哈夫曼编码）3

（3）平衡树

它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。（防止退化为链表，提高搜索效率）3

（4）红黑树

红黑树是平衡二叉树的一种；它有很好的性质，树中的结点都是有序的，而且因为它本身就是平衡的，所以查找也不会出现非常恶劣的情况，基于二叉树的操作的时间复杂度是O(log(N))。Linux内核在管理vm_area_struct时就是采用了红黑树来维护内存块的。2

本词条内容贡献者为:

尚轶伦 - 副教授 - 同济大学数学科学学院