Question

数据结构，图中画波浪线的的地方，这个外部结点指的是什么呢？

Answer 1

在一棵n个结点的二叉树中，除了根结点，每个结点都与一条边相对应，所以边数为n-1
在这n个结点中，有2个孩子的结点，称为2度结点，设其个数为x；有1个孩子的结点，称为1度结点，设其个数为y；还有没有孩子的结点，即叶子结点，设其个数为z
那么显然有x+y+z=n。又由于2度结点对应两条边，1度结点对应一条边，因此可得
2x+y=n-1，两式相减，得z-x=1，由此得到二叉树中的一条重要结论：
叶子结点的个数比2度结点的个数多1。
回到你的问题，这里的内部结点就是指二叉排序树中本来的结点，外部结点应该指为其增加的虚拟结点，即为原来树中每个结点补全其孩子，原来的1度结点补上1个孩子变为2度结点，原来的0度结点补上2个孩子也变为2度结点。
这样在新树中，所有的2度结点即为原二叉排序树中的结点，从位置上来说也可以叫内部结点；所有的叶子结点即为新加的外部结点，因为都补全为2度结点故没有1度结点。
所以根据上面的结论，有n个内部结点即n个2度结点的二叉排序树，其外部结点也就是叶子个数比2度结点个数多1，也即有n+1个。