import java.util.Queue;
import java.util.Stack;
/**
* @ClassName tree
* @Description
* * 遍歷二叉樹
* * 分別以遞歸和非遞歸實現(xiàn)前序惕澎、中序蚀之、后序遍歷二叉樹靴跛、與層級遍歷
* @Version V1.0
**/
public class tree {
//遞歸
//前序遍歷
public void preOrder(Node node){
if(node==null){
return;
}
System.out.println("前序"+node.getValue());
preOrder(node.getLeft());
preOrder(node.getRight());
}
//中序遍歷
public void inOrder(Node node){
if(node == null){
return;
}
inOrder(node.getLeft());
System.out.println("中序"+node.getValue());
inOrder(node.getRight());
}
//后序遍歷
public void postOrder(Node node){
if(node == null){
return;
}
postOrder(node.getLeft());
postOrder(node.getRight());
System.out.println("后序"+node.getValue());
}
//非遞歸
//前序遍歷-- 使用棧
public void preOrderTraversal(Node node){
if(node == null){
return;
}
Stack<Node> nodeStack = new Stack<>();
nodeStack.push(node);
while (!nodeStack.isEmpty()){
Node cur_node = nodeStack.lastElement();
nodeStack.pop();
if(!nodeStack.isEmpty() && nodeStack.lastElement()==null){
nodeStack.pop();
System.out.println("前序"+cur_node.getValue());
continue;
}
if(cur_node.getRight()!=null){
nodeStack.push(cur_node.getRight());
}
if(cur_node.getLeft()!=null){
nodeStack.push(cur_node.getLeft());
}
//前序 nullptr 標(biāo)記當(dāng)前節(jié)點的左右子樹已經(jīng)遍歷
nodeStack.push(null);
nodeStack.push(cur_node);
}
}
//中序遍歷
public void inOrderTraversal(Node node){
if(node == null){
return;
}
Stack<Node> nodeStack = new Stack<>();
nodeStack.push(node);
while (!nodeStack.isEmpty()){
Node cur_node = nodeStack.lastElement();
nodeStack.pop();
if(!nodeStack.isEmpty() && nodeStack.lastElement()==null){
nodeStack.pop();
System.out.println("中序"+cur_node.getValue());
continue;
}
if(cur_node.getRight()!=null){
nodeStack.push(cur_node.getRight());
}
//中序 nullptr 標(biāo)記當(dāng)前節(jié)點的左右子樹已經(jīng)遍歷
nodeStack.push(null);
nodeStack.push(cur_node);
if(cur_node.getLeft()!=null){
nodeStack.push(cur_node.getLeft());
}
}
}
//后序遍歷
public void postOrderTraversal(Node node){
if(node == null){
return;
}
Stack<Node> nodeStack = new Stack<>();
nodeStack.push(node);
while (!nodeStack.isEmpty()){
Node cur_node = nodeStack.lastElement();
nodeStack.pop();
if(!nodeStack.isEmpty() && nodeStack.lastElement()==null){
nodeStack.pop();
System.out.println("后序"+cur_node.getValue());
continue;
}
//后序 nullptr 標(biāo)記當(dāng)前節(jié)點的左右子樹已經(jīng)遍歷
nodeStack.push(null);
nodeStack.push(cur_node);
if(cur_node.getRight()!=null){
nodeStack.push(cur_node.getRight());
}
if(cur_node.getLeft()!=null){
nodeStack.push(cur_node.getLeft());
}
}
}
//層級遍歷
//實現(xiàn)過程
//1、首先將二叉樹的根節(jié)點push到隊列中糟趾,判斷隊列不為NULL,就輸出隊頭的元素黎烈,
//2唠粥、判斷節(jié)點如果有孩子,就將孩子push到隊列中蛉艾,
//3钳踊、遍歷過的節(jié)點出隊列,
//4勿侯、循環(huán)以上操作拓瞪,直到Tree == NULL。
public void levelOrder(Node node){
if(node ==null){
return;
}
Queue<Node> queue = null;
if(node!=null){
queue.add(node);
}
while (!queue.isEmpty()){
System.out.println(queue.peek().getValue());
if(queue.peek().getLeft()!=null){
queue.add(queue.peek().getLeft());
}
if(queue.peek().getRight()!=null){
queue.add(queue.peek().getRight());
}
queue.poll();
}
}
}
class Node {
private int value;
private Node left;
private Node right;
public Node(int value){
this.value=value;
this.left=null;
this.right=null;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
劍指offer-樹
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
- 文/潘曉璐 我一進店門屁药,熙熙樓的掌柜王于貴愁眉苦臉地迎上來粥血,“玉大人,你說我怎么就攤上這事「纯鳎” “怎么了趾娃?”我有些...
- 文/不壞的土叔 我叫張陵,是天一觀的道長缔御。 經(jīng)常有香客問我抬闷,道長,這世上最難降的妖魔是什么耕突? 我笑而不...
- 正文 為了忘掉前任笤成,我火速辦了婚禮,結(jié)果婚禮上眷茁,老公的妹妹穿的比我還像新娘炕泳。我一直安慰自己,他們只是感情好上祈,可當(dāng)我...
- 文/花漫 我一把揭開白布培遵。 她就那樣靜靜地躺著,像睡著了一般登刺。 火紅的嫁衣襯著肌膚如雪荤懂。 梳的紋絲不亂的頭發(fā)上,一...
- 文/蒼蘭香墨 我猛地睜開眼箭启,長吁一口氣:“原來是場噩夢啊……” “哼!你這毒婦竟也來了蛉迹?” 一聲冷哼從身側(cè)響起傅寡,我...
- 正文 年R本政府宣布,位于F島的核電站多矮,受9級特大地震影響灶搜,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜工窍,卻給世界環(huán)境...
- 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望前酿。 院中可真熱鬧患雏,春花似錦、人聲如沸罢维。這莊子的主人今日做“春日...
- 文/蒼蘭香墨 我抬頭看了看天上的太陽肺孵。三九已至匀借,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間平窘,已是汗流浹背吓肋。 一陣腳步聲響...
推薦閱讀更多精彩內(nèi)容
- 1、題目描述 輸入兩棵二叉樹A偶芍,B充择,判斷B是不是A的子結(jié)構(gòu)。 我們規(guī)定空樹不是任何樹的子結(jié)構(gòu)匪蟀。 樣例樹A8/ \...
- 1萄窜、題目描述 給出一個二叉樹铃剔,輸入兩個樹節(jié)點撒桨,求它們的最低公共祖先。 一個樹節(jié)點的祖先節(jié)點包括它本身键兜。 注意: 輸...
- 題目:輸入兩棵二叉樹A凤类,B,判斷B是不是A的子結(jié)構(gòu)普气。(ps:我們約定空樹不是任意一個樹的子結(jié)構(gòu)) 代碼: isSu...
- 原創(chuàng)分享第636天 周三 今天下午進行了一場約練谜疤。有緣千里來相會,杭州现诀、四川夷磕、義烏、鄭州仔沿,千里之外的學(xué)友因焦點...
- 之前我?guī)屯伦鲑Y料坐桩,然后想著后面她應(yīng)該會給我錢,不過上周因為她太忙了封锉, 提起過后來又忘記了绵跷,今天本來我就想著要和她...