信用网站建设原则,网站维护正常要多久,wordpress网站安全,应用公园下载二叉树的种类#xff1a;
满二叉树#xff1a;树的所有节点都是满#xff0c;即都有左右孩子。 这棵二叉树为满二叉树#xff0c;也可以说深度为k#xff0c;有2^k-1个节点的二叉树。
完全二叉树#xff1a;完全二叉树的定义如下#xff1a;在完全二叉树中#xff0c…二叉树的种类
满二叉树树的所有节点都是满即都有左右孩子。 这棵二叉树为满二叉树也可以说深度为k有2^k-1个节点的二叉树。
完全二叉树完全二叉树的定义如下在完全二叉树中除了最底层节点可能没填满外其余每层节点数都达到最大值并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层则该层包含 1~ 2^(h-1) 个节点。 二叉搜索树二叉搜索树是一颗排序树。
若它的左子树不空则左子树上所有结点的值均小于它的根结点的值若它的右子树不空则右子树上所有结点的值均大于它的根结点的值它的左、右子树也分别为二叉排序树平衡二叉搜索树又被称为AVLAdelson-Velsky and Landis树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。 二叉树的存储方式
二叉树可以链式存储也可以顺序存储。
那么链式存储方式就用指针 顺序存储的方式就是用数组。
链式存储使用链表 顺序存储使用数组的方式 查找节点如果父节点的数组下标是 i那么它的左孩子就是 i * 2 1右孩子就是 i * 2 2。
但是用链式表示的二叉树更有利于我们理解所以一般我们都是用链式存储二叉树。
二叉树的遍历方式
二叉树主要有两种遍历方式
深度优先遍历先往深走遇到叶子节点再往回走。广度优先遍历一层一层的去遍历。
那么从深度优先遍历和广度优先遍历进一步拓展才有如下遍历方式
深度优先遍历 前序遍历递归法迭代法中序遍历递归法迭代法后序遍历递归法迭代法广度优先遍历 层次遍历迭代法
前中后遍历其实就是看根节点的位置。在中间就是中序在前面就前序在后面就是后序遍历。
前序遍历中左右中序遍历左中右后序遍历左右中
二叉树的定义
java的定义
public class TreeNode {int value;TreeNode left;TreeNode right;//无参数构造器TreeNode(){}TreeNode(int value){this.valuevalue;}//有参数构造器public TreeNode(int value, TreeNode left, TreeNode right) {this.value value;this.left left;this.right right;}
}
python的定义
class TreeNode: def __init__(self, value):self.value valueself.left Noneself.right None
C的定义
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
