什么是单支树?_广州千锋IT培训

什么是单支树?

来源：千锋教育

发布人：xqq

时间： 2023-10-15 21:35:57

一、什么是单支树

单支树是非叶子节点只有一个孩子节点，且方向一致的特殊二叉树。单支树指的是只有一个孩子并且方向一致，就是每个结点非常多只有一个孩子结点，其实就是链表。

二叉树是另一种树形结构，其特点是每个结点至多只有两棵子树( 即二叉树中不存在度大于2的结点)，并且二叉树的子树有左右之分，其次序不能任意颠倒。

与树相似，二叉树也以递归的形式定义。二叉树是n (n≥0) 个结点的有限集合:

或者为空二叉树，即n=0。

或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

二叉树是有序树，若将其左、右子树颠倒，则成为另一棵不同的二叉树。即使树中结点只有一棵子树，也要区分它是左子树还是右子树。

延伸阅读：

二、几个特殊的二叉树

（1）斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

（2）满二叉树棵高度为h，且含有2 h − 1 2^h-12h−1个结点的二叉树称为满二叉树，即树中的每层都含有非常多的结点。满二叉树的叶子结点都集中在二叉树的最下一层，并且除叶子结点之外的每个结点度数均为2 22。可以对满二叉树按层序编号:约定编号从根结点(根结点编号为1 11)起，自上而下，自左向右。这样，每个结点对应一个编号,对于编号为i的结点，若有双亲，则其双亲为i / 2 i/2i/2,若有左孩子，则左孩子为2 i 2i2i;若有右孩子，则右孩子为2 i + 1 2i+12i+1。

声明：本站稿件版权均属千锋教育所有，未经许可不得擅自转载。