構(gòu)造
//節(jié)點
public class Node {
public int value;//數(shù)據(jù)
public Node left;//左節(jié)點
public Node right;//右節(jié)點
//構(gòu)造函數(shù)
Node(int i){
value = i;
left=null;
right=null;
}
}
二叉樹的構(gòu)造绷杜。
先要有一棵樹直秆，才能遍歷一棵樹。
static void preSet(Node node,Node[] nodes,int i){
if(i*2+1 < nodes.length) {
node.left = nodes[i * 2+1];
}
if(i*2+2 < nodes.length){
node.right = nodes[i*2+2];
}
}
Node[] nodes = new Node[13];
for(int i =0 ;i<13;i++) {
Node node = new Node(i);
nodes[i] = node;
}
for(int i=0;i<13;i++){
preSet(nodes[i],nodes,i);
}
首先構(gòu)造一顆簡單的完全二叉樹
Paste_Image.png
刪去一些節(jié)點：
nodes[2].right=null;
nodes[3].left=null;
nodes[4].right=null;
nodes[5].left=null;
Paste_Image.png
生成了一棵樹鞭盟，開始遍歷吧圾结。
遍歷
Paste_Image.png
遞歸實現(xiàn)
- 前序遍歷 =>
ABC
static void preTravel(Node node){
if(node==null ){
return;
}
System.out.print(node.value + ",");
preTravel(node.left);
preTravel(node.right);
}
- 中序遍歷 =>
BAC
static void preTravel(Node node){
if(node==null ){
return;
}
preTravel(node.left);
System.out.print(node.value + ",");
preTravel(node.right);
}
- 后續(xù)遍歷 =>
BCA
static void preTravel(Node node){
if(node==null ){
return;
}
preTravel(node.left);
preTravel(node.right);
System.out.print(node.value + ",");
}
非遞歸實現(xiàn)
非遞歸實現(xiàn)，這里我根據(jù)網(wǎng)上的思路齿诉，用到了棧. (廢話連篇) 其實不用棧也可以筝野，畢竟看到了這個棧我是用ArrayList寫的，所以只要用到棧的這種思路就行了粤剧，不一定一定要寫一個棧歇竟。但是確實棧很方便...
一個簡單的棧：
public class Stack {
int current=0;
private ArrayList<Node> nodes = new ArrayList<Node>();
boolean isEmpty(){
if(0==current){
return true;
}
return false;
}
void push(Node node){
if(node==null){
return;
}
nodes.add(node);
current++;
}
Node pop() throws Exception{
if(isEmpty()){
throw new Exception();
}
current--;
return nodes.remove(current);
}
}
| 前序遍歷 |
|---|
實現(xiàn)1：
static void preTraverse(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
s.push(node);
while (!s.isEmpty()){
Node item = s.pop();
System.out.print(item.value + ",");
s.push(item.right);
s.push(item.left);
}
System.out.println();
}
這個實現(xiàn)方法不夠好吧。
缺點分析：每次都要先push再pop抵恋』酪椋可不可以必須push才push呢？
實現(xiàn)2：
直接將node=node.left ,而不是每次先push再pop 出來馋记。
static void preTraverse2(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while (node !=null ||!s.isEmpty()){
if(node!=null) {
System.out.print(node.value + ",");
s.push(node.right);
node = node.left;
}else {
node = s.pop();
}
}
System.out.println();
}
進一步優(yōu)化：
實現(xiàn)3：
優(yōu)化的地方是号坡，檢查條件懊烤，內(nèi)嵌了一個while( node != null ),使得不必每次只需檢查node != null的時候還檢查了！s.isEmpty()
但是多了個異常捕獲宽堆。因為這樣可能腌紧，棧為空的時候還向棧中取元素。
static void preTraverse3(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
try {
while (node != null || !s.isEmpty()) {
while (node != null) {
System.out.print(node.value + ",");
s.push(node.right);
node = node.left;
}
node = s.pop();
}
}catch (Exception e){
;
}
System.out.println();
}
進一步優(yōu)化：
發(fā)現(xiàn)畜隶，
1.只有在pop時候壁肋，在需要檢查棧是否空
2.初始化的時候棧為空，
3.內(nèi)嵌了一個while(node籽慢！=null)浸遗，只有在node為空的時候，才會去棧中獲取元素箱亿，如果獲取不到元素跛锌，那么外圍的while(node！=null)檢查條件依然有效.
實現(xiàn)4：
static void preTraverse4(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while (node != null ) {
while (node != null) {
System.out.print(node.value + ",");
s.push(node.right);
node = node.left;
}
if( !s.isEmpty()) {
node = s.pop();
}
}
System.out.println();
}
進一步優(yōu)化：
實現(xiàn)5：
額届惋，好吧髓帽，節(jié)省了一個的node！=null的檢查而已...
static void preTraverse5(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while (node != null ) {
System.out.print(node.value + ",");
s.push(node.right);
node = node.left;
while (node != null) {
System.out.print(node.value + ",");
s.push(node.right);
node = node.left;
}
if( !s.isEmpty()) {
node = s.pop();
}
}
System.out.println();
}
好了脑豹，我是到此結(jié)束了郑藏。
其他的書寫思路一樣，快速看瘩欺，就直接溜到結(jié)尾的實現(xiàn)中必盖。（多么貼心的boy！）
| 中序遍歷 |
|---|
實現(xiàn)1：
static void InOrderTraverse(Node node)throws Exception{
if(node==null){ return; }
Stack s=new Stack();
s.push(node);
while(!s.isEmpty()){
node = s.pop();
//如果左節(jié)點不存在
if(node.left!=null){
s.push(node);
s.push(node.left);
}else if(node.right!=null){//如果右節(jié)點不存在
System.out.print(node.value+",");
s.push(node.right);
}else{//其他的情況俱饿，那就是沒有節(jié)點嘛
System.out.print(node.value+",");
node = s.pop();
while(node.right==null){
System.out.print(node.value+",");
if(!s.isEmpty()) {
node = s.pop();//獲取父親節(jié)點
}else{
return;
}
}
System.out.print(node.value+",");
s.push(node.right);
}
}
}
這個代碼看起來就很頭大歌粥，本人寫的，自己都看不下去..也是調(diào)試后寫出來的稍途。不管了阁吝。優(yōu)化。
實現(xiàn)2：
主要是不要非得將節(jié)點放入棧械拍，再拿出這種浪費效率的工作突勇。而是直接node=node.left;node=node.right;
//BACstatic void InOrderTraverse3(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
if(node.left!=null){//如果左節(jié)點不為空
s.push(node);
node = node.left;
}else if(node.right!=null){//如果右節(jié)點不為空
System.out.print(node.value + ",");
node =node.right;
}else {//否則就是都是空
System.out.print(node.value + ",");
node = s.pop();//獲取父親節(jié)點
while(node.right==null){
System.out.print(node.value + ",");
if(!s.isEmpty()) {
node = s.pop();
}else{
return;
}
}
System.out.print(node.value + ",");
node=node.right;
}
}
}
實現(xiàn)3：
這里其實并沒有優(yōu)化，而是合并了下代碼坷虑。
static void InOrderTraverse4(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
if(node.left!=null){
s.push(node);
node = node.left;
}else if(node.right!=null){
System.out.print(node.value + ",");
node =node.right;
}else {
while (node.right == null) {
System.out.print(node.value + ",");
if(!s.isEmpty()) {
node = s.pop();
}else{
return;
}
}
System.out.print(node.value + ",");
node=node.right;
}
}
}
實現(xiàn)4：
發(fā)現(xiàn)其實第二個else if 中的操作了甲馋，else中的操作其實是一致的，可以合并：
static void InOrderTraverse6(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
while(node.left!=null){
s.push(node);
node = node.left;
}
while(node.right == null){
System.out.print(node.value + ",");
if(!s.isEmpty()) {
node = s.pop();
}else{
return;
}
}
System.out.print(node.value + ",");
node = node.right;
}
}
實現(xiàn)5：
其實是把后半部分的代碼移動了一下而已...
static void InOrderTraverse7(Node node)throws Exception{
if(node==null){ return; }
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
while(node.left!=null){
s.push(node);
node = node.left;
}
System.out.print(node.value + ",");
node=node.right;
while(node ==null){
if(!s.isEmpty()) {
node = s.pop();
System.out.print(node.value + ",");
node=node.right;
}else{return;}
}
}
}
實現(xiàn)6：
又是換了下代碼的位置而已迄损，其實是想少一個while定躏，想利用外面的while，本來就要檢查!s.isEmpty。
static void InOrderTraverse8(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
if(node==null){
node=s.pop();
System.out.print(node.value + ",");
node=node.right;
}else {
while (node.left != null) {
s.push(node);
node = node.left;
}
System.out.print(node.value + ",");
node = node.right;
}
}
}
實現(xiàn)7：
這個優(yōu)化痊远，有點明顯的垮抗，額。
1.上面步驟中碧聪，else部分冒版，的下半部分，其實操作和if的下半部分一樣
2.else中上面是push逞姿。if中有個pop
static void InOrderTraverse10(Node node)throws Exception{
if(node==null){ return; }
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
if(node==null){
node=s.pop();
System.out.print(node.value + ",");
node=node.right;
}else{
while (node.left != null) {
s.push(node);
node = node.left;
}
s.push(node);
}
}
}
實現(xiàn)8：
無論如何s.push(node)這個操作都會被執(zhí)行辞嗡。所以：
static void InOrderTraverse9(Node node)throws Exception{
if(node==null){
return;
}
Stack s=new Stack();
while(node!=null || !s.isEmpty()){
if(node==null){
node=s.pop();
System.out.print(node.value + ",");
node=node.right;
}else{
s.push(node);
node = node.left;
}
}
}
實現(xiàn)9：
網(wǎng)友的實現(xiàn)，我就是因為網(wǎng)友這個刺激的呀滞造，所以一步步實現(xiàn)優(yōu)化续室。
這里又把檢測條件縮小了一下。
static void InOrderTraverse2(Node node)throws Exception{
if(node==null){ return; }
Stack s=new Stack();
while( node!=null || !s.isEmpty()){
while(node!=null){
s.push(node);
node = node.left;
}
node = s.pop();
System.out.print(node.value+",");
node=node.right;
}
}
| 后序遍歷 |
|---|
實現(xiàn)1：
static void postTraverse(Node node)throws Exception{
if(node==null){ return; }
Stack s = new Stack();
s.push(node);
while (!s.isEmpty()){
node = s.pop();
if(node.left==null && node.right==null){
System.out.print(node.value + ",");
Node node1 =s.pop();
while(node1.left == node || node1.right == node){
System.out.print(node1.value+",");
node = node1;
try{
node1=s.pop();
}catch (Exception e){
return;
}
}
s.push(node1);
}else {
s.push(node);
s.push(node.right);
s.push(node.left);
}
}
}
實現(xiàn)2：
主要是
1.簡化了pop和push操作谒养，將操作變簡單
static void postTraverse2(Node node)throws Exception{
if(node==null){ return; }
Stack s = new Stack();
try {
while (node != null || !s.isEmpty()) {
if(node==null){
node =s.pop();
}
if (node.left == null && node.right == null) {
System.out.print(node.value + ",");
Node node1 = s.pop();//獲取父節(jié)點
while (node1.left == node || node1.right == node) {//檢查是不是父節(jié)點
System.out.print(node1.value + ",");
node = node1;
node1 = s.pop();
}
node=node1;
} else {
s.push(node);
s.push(node.right);
node = node.left;
}
}
}catch (Exception e){
return;
}
System.out.println();
}
實現(xiàn)3：
并沒有實質(zhì)性的優(yōu)化...
static void postTraverse3(Node node)throws Exception{
if(node==null){ return; }
Stack s = new Stack();
try {
while (node != null || !s.isEmpty()) {
if(node==null){
node =s.pop();
}
if (node.left == null && node.right == null) {
System.out.print(node.value + ",");
Node tmp=node;
node = s.pop();//獲取父節(jié)點
while (node.left == tmp || node.right == tmp) {//檢查是不是父節(jié)點
System.out.print(node.value + ",");
tmp = node;
node = s.pop();
}
} else {
s.push(node);
s.push(node.right);
node = node.left;
}
}
}catch (Exception e){
return;
}
}
實現(xiàn)4：
static void postTraverse4(Node node)throws Exception{
if(node==null){
return; }
Stack s = new Stack();
try {
while (node != null || !s.isEmpty()) {
if (node.left == null && node.right == null) {
Node tmp;
do {
System.out.print(node.value + ",");
tmp = node;
node = s.pop();//獲取父節(jié)點
}while (node.left == tmp || node.right == tmp);//檢查是不是父節(jié)點
}else {
s.push(node);
s.push(node.right);
node = node.left;
if(node==null){
node =s.pop();
}
}
}
}catch (Exception e){
return;
}
}
實現(xiàn)5：
網(wǎng)友的思路是：
設(shè)置標志位挺狰，如果讀取過一次就置1.不然，就設(shè)置0.
就是Stack中他添加了一個tag數(shù)組买窟，用于設(shè)置其標志位她渴。
void postorder_dev(bintree t){
seqstack s;
s.top = -1;
if(!t){
printf("the tree is empty!\n");
}else{
while(t || s.top != -1){ //棧空了的同時t也為空蔑祟。
while(t){
push(&s,t);
s.tag[s.top] = 0; //設(shè)置訪問標記，0為第一次訪問沉唠，1為第二次訪問
t= t->lchild;
}
if(s.tag[s.top] == 0){ //第一次訪問時疆虚，轉(zhuǎn)向同層右結(jié)點
t= s.data[s.top]; //左走到底時t是為空的，必須有這步满葛！
s.tag[s.top]=1;
t=t->rchild;
}else {
while (s.tag[s.top] == 1){ //找到棧中下一個第一次訪問的結(jié)點径簿，退出循環(huán)時并沒有pop所以為其左子結(jié)點
t = pop(&s);
printf("%c ",t->data);
}
t = NULL; //必須將t置空。跳過向左走嘀韧，直接向右走
}
}
}
}
| 層級遍歷 |
|---|
static void levelTravel(Node node){
if(node==null){
return;
}
ArrayList<Node> nodes= new ArrayList<Node>();
nodes.add(node);
while(!nodes.isEmpty()){
Node item = nodes.remove(0);
if(item==null){
continue;
}
System.out.println(item.value);
nodes.add(item.left);
nodes.add(item.right);
}
}
