一、二叉树中的结点值指什么

在二叉树中，结点值（node value）通常是指每个节点上存储的数据值。在实际应用中，可以根据需要将结点值定义为任意类型，例如整数、浮点数、字符串等等。对于二叉搜索树（Binary Search Tree, BST），其结点值还需要满足一定的条件，即左子树上的所有结点的值均小于该结点的值，右子树上的所有结点的值均大于该结点的值。这样能够方便地使用二叉搜索树进行查找、插入和删除操作。

需要注意的是，在某些特殊情况下，结点值也可以表示其他含义，例如在霍夫曼树（Huffman Tree）中，结点值表示字符出现的次数；在红黑树（Red-Black Tree）中，结点值表示关键字的大小。因此，在实际应用中需要根据具体情况定义结点值的含义和类型。

二、二叉树概述

1、定义

二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

2、特点

每个结点非常多有两颗子树，所以二叉树中不存在度大于2的结点。左子树和右子树是有顺序的，次序不能任意颠倒。即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

3、性质

二叉树的第i层上至多有2^i-1（i≥1）个节点 。深度为h的二叉树中至多含有2^h-1个节点。若在任意一棵二叉树中，有n₀个叶子节点，有n₂个度为2的节点，则必有n₀=n₂+1。具有n个节点的满二叉树深为log2n+1。若对一棵有n个节点的完全二叉树进行顺序编号（1≤i≤n），那么，对于编号为i（i≥1）的节点：当i=1时，该节点为根，它无双亲节点；当i>1时，该节点的双亲节点的编号为i/2；若2i≤n，则有编号为2i的左节点，否则没有左节点；若2i+1≤n，则有编号为2i+1的右节点，否则没有右节点。

4、二叉树的建立

实现代码：

BiNode create()//先序建立二叉树 {BiNode T;char a;scanf("%c",&a);if(a=='.') return NULL;//当输入.时表示这个结点为空，而且没有左右子树。else{T=(BiNode)malloc(sizeof(BiTree));//动态分配内存T->data=a;T->lchild=create();//创建左子树 T->rchild=create();//创建右子树 }return T;}

三、二叉树、树、森林的相互转换

1、树转换为二叉树

由于二叉树是有序的，为了避免混淆，对于无序树，我们约定树中的每个结点的孩子结点按从左到右的顺序进行编号。

将树转换成二叉树的步骤是：

加线：就是在所有兄弟结点之间加一条连线；抹线：就是对树中的每个结点，只保留他与名列前茅个孩子结点之间的连线，删除它与其它孩子结点之间的连线；旋转：就是以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。

2、森林转换为二叉树

森林是由若干棵树组成，可以将森林中的每棵树的根结点看作是兄弟，由于每棵树都可以转换为二叉树，所以森林也可以转换为二叉树。

将森林转换为二叉树的步骤是：

先把每棵树转换为二叉树；名列前茅棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子结点，用线连接起来。当所有的二叉树连接起来后得到的二叉树就是由森林转换得到的二叉树。

3、二叉树转换为树

二叉树转换为树是树转换为二叉树的逆过程，其步骤是：

若某结点的左孩子结点存在，将左孩子结点的右孩子结点、右孩子结点的右孩子结点……都作为该结点的孩子结点，将该结点与这些右孩子结点用线连接起来；删除原二叉树中所有结点与其右孩子结点的连线；整理名列前茅步和第二步得到的树，使之结构层次分明。

4、二叉树转换为森林

二叉树转换为森林比较简单，其步骤是：

先把每个结点与右孩子结点的连线删除，得到分离的二叉树；把分离后的每棵二叉树转换为树；整理第二步得到的树，使之规范，这样得到森林。

延伸阅读1：二叉树遍历的概念

遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有节点，使每一个节点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个节点转换成为一个线性序列来表示。