算法學(xué)習(xí)(七): 二叉樹和二叉樹搜索

樹的定義

  • 樹(Tree): 是一種無向圖(undirected graph), 其中任意兩個頂點(diǎn)間存在唯一一條路徑?；蛘哒f, 只要沒有回路的連通圖就是樹。
  • 一個(可能是非線性的)數(shù)據(jù)結(jié)構(gòu), 由結(jié)點(diǎn), 頂點(diǎn)和邊組成, 沒有任何環(huán)

下面的就是典型的樹:

下面這兩種就不是樹：

  • 第一個兩個頂點(diǎn)之間存在多條路
  • 第二個形成了環(huán)路


二叉樹

二叉樹
上面的鏈接是關(guān)于二叉樹的介紹, 大家可以先通過鏈接學(xué)習(xí)二叉樹的相關(guān)概念


二叉樹的屬性

  • 二叉樹第i層最多有2i個節(jié)點(diǎn)(這里的層數(shù)是從0開始)
  • 一個深度為k的二叉樹樹最多有2(k+1)-1個節(jié)點(diǎn)(深度從0開始)
  • 一個完全二叉樹有n個節(jié)點(diǎn), 樹的深度則是log(n+1)-1 (深度從0開始)
  • 在完全二叉樹中, 如果從根節(jié)點(diǎn)開始為節(jié)點(diǎn)編號, 對于節(jié)點(diǎn)編號為k的節(jié)點(diǎn), 其左孩子的編號為2k+1, 右孩子為2k+2, 其中跟節(jié)點(diǎn)編號為0


二叉樹的遍歷

  • 前序遍歷: 父節(jié)點(diǎn), 左孩子, 右孩子
  • 中序遍歷: 左孩子, 父節(jié)點(diǎn), 右孩子
  • 后序遍歷: 左孩子, 右孩子， 父節(jié)點(diǎn)


二叉樹遍歷的框架

  • 創(chuàng)建一個Node類用來保存二叉樹結(jié)構(gòu)
  • preOrderUnRecur方法實(shí)現(xiàn)非遞歸的二叉樹前序遍歷
  • inOrderUnRecur方法實(shí)現(xiàn)非遞歸的二叉樹中序遍歷
  • posOrderUnRecur方法實(shí)現(xiàn)非遞歸的二叉樹后序遍歷
import java.util.Stack;

public class PreInPosTraversal {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int data) {
            this.value = data;
        }
    }

    public static void preOrderUnRecur(Node head) {}

    public static void inOrderUnRecur(Node head) {}

    public static void posOrderUnRecur(Node head) {}


    public static void main(String[] args) {
        Node head = new Node(5);
        head.left = new Node(3);
        head.right = new Node(8);
        head.left.left = new Node(2);
        head.left.right = new Node(4);
        head.left.left.left = new Node(1);
        head.right.left = new Node(7);
        head.right.left.left = new Node(6);
        head.right.right = new Node(10);
        head.right.right.left = new Node(9);
        head.right.right.right = new Node(11);

    
        // unrecursive
        System.out.println("============unrecursive=============");
        preOrderUnRecur(head);
        inOrderUnRecur(head);
        posOrderUnRecur(head);
    }
}


非遞歸實(shí)現(xiàn)前序遍歷

public static void preOrderUnRecur(Node head) {
  System.out.print("pre-order: ");
  if (head != null) {
    Stack<Node> stack = new Stack<Node>();
    stack.add(head);
    while (!stack.isEmpty()) {
      head = stack.pop();
      System.out.print(head.value + " ");
      if (head.right != null) {
        stack.push(head.right);
      }
      if (head.left != null) {
        stack.push(head.left);
      }
    }
  }
  System.out.println();
}


非遞歸實(shí)現(xiàn)中序遍歷

  • 首先對左子樹進(jìn)行迭代, 將非空節(jié)點(diǎn)入棧, 直到節(jié)點(diǎn)為空

  • 當(dāng)前節(jié)點(diǎn)為空時進(jìn)行出棧操作, 并訪問棧頂節(jié)點(diǎn), 將當(dāng)前節(jié)點(diǎn)用右子節(jié)點(diǎn)代替


public static void inOrderUnRecur(Node head) {
  System.out.print("in-order: ");
  if (head != null) {
    Stack<Node> stack = new Stack<Node>();
    while (!stack.isEmpty() || head != null) {
      if (head != null) {
        stack.push(head);
        head = head.left;
      } else {
        head = stack.pop();
        System.out.print(head.value + " ");
        head = head.right;
      }
    }
  }
  System.out.println();
}


非遞歸實(shí)現(xiàn)后序遍歷

用兩個棧實(shí)現(xiàn)后序遍歷：


public static void posOrderUnRecur(Node head) {
  System.out.print("pos-order: ");
  if (head != null) {
    Stack<Node> s1 = new Stack<Node>();
    Stack<Node> s2 = new Stack<Node>();
    s1.push(head);
    while (!s1.isEmpty()) {
      head = s1.pop();
      s2.push(head);
      if (head.left != null) {
        s1.push(head.left);
      }
      if (head.right != null) {
        s1.push(head.right);
      }
    }
    while (!s2.isEmpty()) {
      System.out.print(s2.pop().value + " ");
    }
  }
  System.out.println();
}



用一個棧實(shí)現(xiàn)后序遍歷:
這個有興趣的可以了解下, 平時不太能用的到, 因?yàn)橛脙蓚€棧的空間復(fù)雜度跟一個一樣, 并且代碼簡單, 所以通常用兩個棧來實(shí)現(xiàn)后序遍歷就可以了



def postOrderTraversalOneStack(self):
      nodeStack = stack.Stack()
      curNode = self.root
      newNode = None
      while not nodeStack.isEmpty() or curNode != None:
        while curNode != None:
          newNode = NodeWithFlag(curNode, False)
          nodeStack.push(newNode)
          curNode = curNode.left

        newNode = nodeStack.pop()
        curNode = newNode.node
        if not newNode.flag:
          newNode.flag = True
          nodeStack.push(newNode)
          curNode = curNode.right
        else:
          print(curNode.key)
          curNode = None


二叉樹相關(guān)算法

得到一個二叉樹節(jié)點(diǎn)的后繼節(jié)點(diǎn)

有一個二叉樹, 給定一個節(jié)點(diǎn), 找出他的后繼節(jié)點(diǎn),
這個二叉樹的節(jié)點(diǎn)有個特殊的地方, 每個節(jié)點(diǎn)不但有指向左孩子的left和右孩子的right, 還有一個指向父節(jié)點(diǎn)的parent，在二叉樹的中序遍歷的序列中, node的下一個節(jié)點(diǎn)叫做node的后繼節(jié)點(diǎn)

分析：
這里先要給出、幾個概念：

  • 中序前驅(qū)：
    中序遍歷時, 某個節(jié)點(diǎn)的前一個遍歷的節(jié)點(diǎn)叫前驅(qū)

  • 中序后繼:
    中序遍歷時, 某個節(jié)點(diǎn)的后一個遍歷的節(jié)點(diǎn)叫做后繼


  • 二叉搜索樹
    對于二叉樹中任意一個元素, 若其左子樹中所有元素的值都小于該元素的值, 并且其右子樹中所有元素的值都大于該元素的值, 這個二叉樹就叫做搜索二叉樹
    二叉搜索樹中序遍歷后的結(jié)果是從小到大依次排列的, 這也是我們判斷一個二叉樹是不是二叉搜索樹的依據(jù)


算法流程:

  • 當(dāng)節(jié)點(diǎn)有右孩子時, 節(jié)點(diǎn)的后繼就是以右孩子為根的二叉樹的最后一個左孩子
  • 當(dāng)節(jié)點(diǎn)沒有右孩子時, 一直沿著父節(jié)點(diǎn)往上找, 直到找到某個節(jié)點(diǎn)是其父節(jié)點(diǎn)的第一個左孩子, 則某個節(jié)點(diǎn)的父節(jié)點(diǎn)就是目標(biāo)節(jié)點(diǎn)的后繼
public SuccessorNode {

    public static class Node {
        public int value;
        public Node left;
        public Node right;
        public Node parent;

        public Node(int data) {
            this.value = data;
        }
    }

    public static Node getSuccessorNode(Node node) {
        if (node == null) {
            return node;
        }
        if (node.right != null) {
            return getLeftMost(node.right);
        } else {
            Node parent = node.parent;
            while (parent != null && parent.left != node) {
                node = parent;
                parent = node.parent;
            }
            return parent;
        }
    }

    public static Node getLeftMost(Node node) {
        if (node == null) {
            return node;
        }
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}


二叉樹的序列化和反序列化

  • 二叉樹的序列化：把一棵二叉樹按照某種遍歷方式的結(jié)果以某種格式保存為字符串，從而使得內(nèi)存中建立起來的二叉樹可以持久保存。
  • 二叉樹的反序列化: 把字符串格式保存的二叉樹文本轉(zhuǎn)換成內(nèi)存中的二叉樹, 應(yīng)按照序列化時的遍歷方式來反序列化, 如序列化時用的是前序遍歷, 則反序列化也必須用前序遍歷的方式來反序列化



二叉樹序列化的方法如下:

  1. 先規(guī)定按某個方式遍歷, 遇到元素時,保存元素的值, 并用下滑下_隔開, 如:
    我們遍歷第一個元素為1, 第二個為23, 則記錄方式為1_23_
  2. 遍歷某個元素的左節(jié)點(diǎn)時, 如果其左節(jié)點(diǎn)為空, 用#符號記錄, 同樣的遍歷到右節(jié)點(diǎn)時, 若右節(jié)點(diǎn)為空, 也用#記錄

  3. 整個二叉樹遍歷完后記錄的字符串結(jié)構(gòu)即為序列化結(jié)果




我們還可以利用按層遍歷二叉樹來序列化:

  1. 準(zhǔn)備一個隊(duì)列, 在把head加入隊(duì)列前先打印head的值,比如head的值為1, 我們記錄為1_
  2. 從隊(duì)列彈出一個數(shù), 打印head的左孩子和右孩子的值, 然后把左孩子和右孩子存入隊(duì)列中, 如果某個孩子不存在, 僅打印#_, 無需存入隊(duì)列
  3. 繼續(xù)從隊(duì)列中彈出一個數(shù), 然后繼續(xù)打印head左孩子的左孩子和右孩子的值,并存入隊(duì)列, 跟上面一樣如果沒有就僅打印#_
  4. 繼續(xù)從隊(duì)列彈出一個數(shù), 打印head右孩子的左孩子和右孩子的值,并存入隊(duì)列,如果沒有就打印#_

  5. 重復(fù)彈出一個數(shù), 然后打印下一個元素的左右孩子, 存入隊(duì)列, 沒有就打印#_, 直到隊(duì)列中所有元素都彈出為止




按層遍歷的反序列化:

序列化和反序列化的代碼比較簡單, 請大家自己試著寫出來吧


判斷一棵二叉樹是否是平衡二叉樹

  • 平衡二叉樹:
    對于二叉樹中任意節(jié)點(diǎn), 其左子樹的高度和右子樹的高度差不超過1

此類問題的套路:
適用情況為考察每一個節(jié)點(diǎn)為頭的整棵子樹
利用遞歸來解決問題

  1. 先寫主函數(shù)框架
public static boolean isBalance() {
  ...
}
  1. 分析我們需要得到的數(shù)據(jù)
    判斷一棵樹是否是平衡二叉樹需要滿足兩點(diǎn): 左子樹和右子樹都是平衡二叉樹, 左子樹和右子樹的高度差不大于1。 為了判斷是否平衡二叉樹, 我們需要得到以下數(shù)據(jù):
    • 左子樹是否平衡二叉樹
    • 右子樹是否平衡二叉樹
    • 左子樹的高度
    • 右子樹的高度
  2. 整合信息,定義抽象數(shù)據(jù)類型(ADT)
    進(jìn)一步抽象數(shù)據(jù), 把所有數(shù)據(jù)整合, 設(shè)計(jì)返回整合后數(shù)據(jù)的抽象數(shù)據(jù)類型
    我們發(fā)現(xiàn)如果不考慮左子樹和右子樹, 對于每一個節(jié)點(diǎn),我們都需要兩個數(shù)據(jù): 以該節(jié)點(diǎn)為根的二叉樹是否為平衡二叉樹, 節(jié)點(diǎn)的高度。我們可以用一個抽象數(shù)據(jù)類型來獲得這兩個數(shù)據(jù), 這道題的情況是左右剛好需要的數(shù)據(jù)是一樣的, 如果左右子樹需要的數(shù)據(jù)不一樣, 我們把所有需要的數(shù)據(jù)都整合成一個ADT, 在遞歸時對左右子樹返回其各自需要的數(shù)據(jù)即可
    • isBalance 布爾類型
    • height 整型
public static class ReturnData {
  public boolean isBalance;
  public int height;
  public ReturnData(boolean, isBalance, int height) {
    this.isBalance = isBalance;
    this.height = height;
  }
}


  1. 設(shè)計(jì)遞歸函數(shù)
    先確定簡單情況
    設(shè)計(jì)遞歸時, 默認(rèn)左樹返回所需的信息, 默認(rèn)右樹也返回所需的信息, 然后自身也同樣返回相同的所需信息

通過遞歸先得到所有節(jié)點(diǎn)的左子樹和右子樹是否為平衡二叉樹以及他們的高度, 并根據(jù)這些數(shù)據(jù)判斷以該節(jié)點(diǎn)為根的二叉樹是否為平衡二叉樹, 層層往上, 最終就能得到整個二叉樹是否為平衡二叉樹

public static ReturnData process(Node node) {
  //簡單情況
  if (node == null) {
    return new ReturnData(true, 0);
  }
  //默認(rèn)左子樹返回isBalance和height
  ReturnData leftData = process(node.left);

  //默認(rèn)右子樹返回isBalance和height
  ReturnData rightData = process(node.right);

  //自身判斷并返回相同的所需信息
  int height = 0;
  boolean isBalance = true;
  if (!leftData.isBalance || !rightData.isBalance ) {
    isBalance = false;
  }
  if (Math.abs(leftData.height - rightData.height) > 1) {
    isBalance = false;
  }
  height = Math.max(leftData.height, rightData.height) + 1
  return new ReturnData(isBalance, height)
}
  1. 在主函數(shù)中調(diào)用遞歸函數(shù)
public static boolean isBalance() {
  return process(head).isBalance;
}


判斷一棵樹是否是完全二叉樹

思路:
按層遍歷

  1. 如果某個節(jié)點(diǎn)有右孩子沒有左孩子, 則不是完全二叉樹
  2. 如果某個節(jié)點(diǎn)k左右孩子不全, 則他之后的節(jié)點(diǎn)必須都是葉節(jié)點(diǎn)
  public static boolean isCBT(Node head) {
    if (head == null) {
      return true;
    }
    Queue<Node> queue = new LinkedList<Node>();
    boolean leaf = false; // 觸發(fā)檢測k之后節(jié)點(diǎn)全是葉節(jié)點(diǎn)的開關(guān)
    Node left = null;
    Node right = null;
    queue.offer(head);
    while (!queue.isEmpty()) {
      head = queue.poll();
      left = head.left;
      right = head.right;
      if ((left == null && right != null) || (leaf && (left !=null || right != null))) {
        return false;
      }
      if (left == null && right == null) {
        leaf = true;
      }
      if (left !=null) {
        queue.offer(left);
      }
      if (right != null) {
        queue.offer(right);
      }
    }
    return true;
  }


已知一棵完全二叉樹, 求其節(jié)點(diǎn)的個數(shù)

要求: 時間復(fù)雜度低于O(n)， N為這棵樹的節(jié)點(diǎn)個數(shù)

// 保證head是一棵完全二叉樹
public static int nodeNum(Node node) {
  if (node == null) {
    return 0;
  }
  return bs(head, 0, mostLeftLevel(head, 0));
}

public static int bs(Node node, int i, int allLevel) {
  if (i == allLevel) {
    return 1;
  }
  if (mostLeftLevel(node.right, i + 1) == allLevel) {
    return (1<<(allLevel - i)) + bs(node.right, i + 1, allLevel);
  }else {
    return (1<<(allLevel - i - 1)) + bs(node.left, i + 1, allLevel);
  }
}

public static int mostLeftLevel(Node node, int i) {
   while (node != null) {
    i++;
    node = node.left;
  }
  return i - 1;
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容