创建二叉树 2.先序遍历二叉树(递归) 3.中序遍历二叉树(非递归1) 4.中序遍历二叉树(非递归2) 5.后序遍历二叉树(递归) 6.层序遍历二叉树 7.求二叉树的深度 8.求二叉树中非叶子结点的个数
时间: 2024-12-22 22:11:02 浏览: 51
创建二叉树通常涉及构建节点结构,每个节点包含一个值、左子树引用和右子树引用。以下是基本步骤:
1. **创建二叉树**:创建一个Node类,包含字段value,left(左孩子),right(右孩子)。然后通过插入操作,按照给定的元素序列构建二叉树。
2. **先序遍历(递归)**:也称为前序遍历,顺序是根-左-右。对于当前节点,首先访问它,然后递归地访问左子树,最后右子树。递归形式为`visit(root)`,其中`visit(node) = {print(node.value); visit(node.left); visit(node.right)}`。
3. **中序遍历(非递归1)**:顺序是左-根-右。非递归版本可以使用栈辅助,将所有左子节点压入栈,然后弹出并访问根节点,再遍历其右子树。
4. **中序遍历(非递归2)**:同样采用栈,但操作稍微复杂一些。开始时将根节点压栈,然后循环:如果当前节点不为空,将其左子节点压栈;当遇到空节点时,从栈顶取出节点访问,并移动到其右子节点,直到栈为空。
5. **后序遍历(递归)**:顺序是左-右-根。在访问完左右子树后再访问根节点,即`visit(node) = {visit(node.left); visit(node.right); print(node.value)}`。
6. **层序遍历**:又称广度优先搜索,逐层遍历节点。用队列辅助,每次放入一层的所有节点,然后依次访问它们,再将下一层的节点放入队列。
7. **求二叉树的深度**:从根节点开始,递归计算最深的分支的长度加一,或者用层次遍历,记录每一层的最大深度。
8. **求二叉树中非叶子结点的个数**:非叶子结点即内部结点,统计除叶子结点外的所有节点。可以用递归方式,在访问每个结点时减去1(如果是叶子结点则不变)。
阅读全文
相关推荐















