1 二叉树概念
1)树有很多种，每个节点最多只能有两个子节点的一种形式称为二叉树。
2)二叉树的子节点分为左节点和右节点。
3)如果该二叉树的所有叶子节点都在最后一层，并且结点总数=2^n-1 , n为层数，则我们称为满二叉树。
4)如果该二叉树的所有叶子节点都在最后一层或者倒数第二层，而且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续，我们称为完全二叉树。
2 二叉树的特点
1）树执行查找、删除、插入的时间复杂度都是O(logN)
2）遍历二叉树的方法包括前序、中序、后序
3）非平衡树指的是根的左右两边的子节点的数量不一致
4） 在非空二叉树中，第i层的结点总数不超过 , i>=1；
5）深度为h的二叉树最多有个结点(h>=1)，最少有h个结点；
6）对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1；
3 二叉树的Scala代码实现
定义节点以及前序、中序、后序遍历
class TreeNode(treeNo:Int){
val no = treeNo
var left:TreeNode = null
var right:TreeNode = null
//后序遍历
def postOrder():Unit={
//向左递归输出左子树
if(this.left != null){
this.left.postOrder
}
//向右递归输出右子树
if (this.right != null) {
this.right.postOrder
}
//输出当前节点值
printf("节点信息 no=%d \n",no)
}
//中序遍历
def infixOrder():Unit={
//向左递归输出左子树
if(this.left != null){
this.left.infixOrder()
}
//输出当前节点值
printf("节点信息 no=%d \n",no)
//向右递归输出右子树
if (this.right != null) {
this.right.infixOrder()
}
}
//前序遍历
def preOrder():Unit={
//输出当前节点值
printf("节点信息 no=%d \n",no)
//向左递归输出左子树
if(this.left != null){
this.left.postOrder()
}
//向右递归输出右子树
if (this.right != null) {
this.right.preOrder()
}
}
//后序遍历查找
def postOrderSearch(no:Int): TreeNode = {
//向左递归输出左子树
var resNode:TreeNode = null
if (this.left != null) {
resNode = this.left.postOrderSearch(no)
}
if (resNode != null) {
return resNode
}
if (this.right != null) {
resNode = this.right.postOrderSearch(no)
}
if (resNode != null) {
return resNode
}
println("ttt~~")
if (this.no == no) {
return this
}
resNode
}
//中序遍历查找
def infixOrderSearch(no:Int): TreeNode = {
var resNode : TreeNode = null
//先向左递归查找
if (this.left != null) {
resNode = this.left.infixOrderSearch(no)
}
if (resNode != null) {
return resNode
}
println("yyy~~")
if (no == this.no) {
return this
}
//向右递归查找
if (this.right != null) {
resNode = this.right.infixOrderSearch(no)
}
return resNode
}
//前序查找
def preOrderSearch(no:Int): TreeNode = {
if (no == this.no) {
return this
}
//向左递归查找
var resNode : TreeNode = null
if (this.left != null) {
resNode = this.left.preOrderSearch(no)
}
if (resNode != null){
return resNode
}
//向右边递归查找
if (this.right != null) {
resNode = this.right.preOrderSearch(no)
}
return resNode
}
//删除节点
//删除节点规则
//1如果删除的节点是叶子节点，则删除该节点
//2如果删除的节点是非叶子节点，则删除该子树
def delNode(no:Int): Unit = {
//首先比较当前节点的左子节点是否为要删除的节点
if (this.left != null && this.left.no == no) {
this.left = null
return
}
//比较当前节点的右子节点是否为要删除的节点
if (this.right != null && this.right.no == no) {
this.right = null
return
}
//向左递归删除
if (this.left != null) {
this.left.delNode(no)
}
//向右递归删除
if (this.right != null) {
this.right.delNode(no)
}
}
}
定义二叉树，前序、中序、后序遍历，前序、中序、后序查找，删除节点
class BinaryTree{
var root:TreeNode = null
//后序遍历
def postOrder(): Unit = {
if (root != null){
root.postOrder()
}else {
println("当前二叉树为空，不能遍历")
}
}
//中序遍历
def infixOrder(): Unit = {
if (root != null){
root.infixOrder()
}else {
println("当前二叉树为空，不能遍历")
}
}
//前序遍历
def preOrder(): Unit = {
if (root != null){
root.preOrder()
}else {
println("当前二叉树为空，不能遍历")
}
}
//后序遍历查找
def postOrderSearch(no:Int): TreeNode = {
if (root != null) {
root.postOrderSearch(no)
}else{
null
}
}
//中序遍历查找
def infixOrderSeacher(no:Int): TreeNode = {
if (root != null) {
return root.infixOrderSearch(no)
}else {
return null
}
}
//前序查找
def preOrderSearch(no:Int): TreeNode = {
if (root != null) {
return root.preOrderSearch(no)
}else{
//println("当前二叉树为空，不能查找")
return null
}
}
//删除节点
def delNode(no:Int): Unit = {
if (root != null) {
//先处理一下root是不是要删除的
if (root.no == no){
root = null
}else {
root.delNode(no)
}
}
}
往期精彩内容：