數(shù)據(jù)結(jié)構(gòu)與算法之判斷一棵樹是否為搜索二叉樹、判斷一棵樹是否是完全二叉樹

---

目錄

判斷一棵樹是否為搜索二叉樹

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

---

1. 判斷一棵樹是否為搜索二叉樹

概念：搜索樹就是中序遍歷的結(jié)果是升序，就是搜索二叉樹。如下圖

我們可以改中序遍歷非遞歸版，在打印時機換成比較。即如代碼為中序遍歷非遞歸版

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è)置一個變量記錄當前值，和后一個需要打印的值比較，如果前一個值大于后一個值，即不是搜索二叉樹，則返回false。改后的搜索二叉樹代碼為：

public static boolean isBST1(Node head) {if (head != null) {Stack<Node> stack = new Stack<>();int pre = 0;while (!stack.isEmpty() || head != null) {if (head != null) {stack.push(head);head = head.left;} else {head = stack.pop();if (pre<=head.value){pre = head.value;}else {return false;}head = head.right;}}}return true;}

另外一種搜索二叉樹的代碼

public static boolean isBST2(Node head) {if (head == null) {return true;}boolean res = true;Node pre = null;Node cur1 = head;Node cur2 = null;while (cur1 != null) {cur2 = cur1.left;if (cur2 != null) {while (cur2.right != null && cur2.right != cur1) {cur2 = cur2.right;}if (cur2.right == null) {cur2.right = cur1;cur1 = cur1.left;continue;} else {cur2.right = null;}}if (pre != null && pre.value > cur1.value) {res = false;}pre = cur1;cur1 = cur1.right;}return res;}

---

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

思路

如果有右孩子，沒有左孩子，那肯定不是完全二叉樹

當?shù)谝淮伟l(fā)現(xiàn)左右兩個孩子不是雙全的時候，后面遍歷到的節(jié)點全部都是葉節(jié)點，否則返回false

流程

判斷head是否為null，如果為null返回true，否則創(chuàng)建一個隊列和創(chuàng)建一個布爾值leaf，表示判斷是否開啟葉子階段

當隊列不為null時，從隊列彈出一個數(shù)，然后獲取左右節(jié)點。

判斷：如果左孩子為null，右孩子不為null，或者開啟葉子判斷并且左孩子節(jié)點或者右孩子節(jié)點不為null，則返回false。

如果左節(jié)點不為null，加入隊列。如果右節(jié)點不為null，加入隊列。

如果左節(jié)點為null或者右節(jié)點為null，則開啟葉子判斷。

代碼實現(xiàn)

public static boolean isCBT(Node head) {if (head == null) {return true;}Queue<Node> queue = new LinkedList<Node>();boolean leaf = false;Node l = null;Node r = null;queue.offer(head);while (!queue.isEmpty()) {head = queue.poll();l = head.left;r = head.right;if ((leaf && (l != null || r != null)) || (l == null && r != null)) {return false;}if (l != null) {queue.offer(l);}if (r != null) {queue.offer(r);}if (l == null || r == null) {leaf = true;}}return true;}

總結(jié)

以上是生活随笔為你收集整理的数据结构与算法之判断一棵树是否为搜索二叉树、判断一棵树是否是完全二叉树的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。