二叉樹的遞歸與非遞歸

二叉樹的遞歸與非遞歸

二叉樹節點結構

class Node<V>
{
	V value;//一個節點有自己的值
	Node left;//指向左孩子的指針
	Node right;//指向右孩子的指針
}
           

遞歸實作方法

• 先序：先處理頭，再處理左，最後處理右

  即按照遞歸順序取第一次出現的數組成的序列

• 中序：先處理左，再處理頭，最後處理右

  即按照遞歸順序取第二次出現的數組成的序列

• 後序：先處理左，再處理右，最後處理頭

  即按照遞歸順序取第三次出現的數組成的序列

非遞歸實作方法

任何遞歸函數都可以改成非遞歸函數

• 先序：

每次：

1. 從棧中彈出一個節點cur
2. 列印（處理）cur
3. 先右節點再左節點（如果有）
4. 周而複始

public static void preOrderUnRecur(Node head)
{
	if(head != null)
	{
		Stack<Node> stack = new Stack<Node>();
		stack.add(head);
		while(!stack.isEmpty())
		{
			head = stack.pop();
			cout<<head.value<<" ";
			if(head.right != null)
				stack.push(head.right);
			if(head.left != null)
				stack,push(head.left)
		}
	}
}
           

• 中序

每棵子樹，整個樹左邊界進棧，在依次彈出節點的過程中列印，并且對彈出節點的右數重複此操作

public static void inOrderUnRecur(Node head)
{
	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往左走的時候，若走到空位置上，開始彈出節點，然後移動到它的右孩子上
			{
                head = stack.pop();
                cout<<head.value<<" ";
                head = head.right;
			}
		}
	}
}
           

• 後序

​ 準備兩個棧

2. 将cur放入收集棧後
3. 先壓左節點再壓右節點（如果有）

因為為頭右左，進一次新棧再出棧後順序颠倒，為右左頭

public static void posOrderUnRecur1(Node head)
{
	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())
		cout<<s2.pop().value<<" ";
}
           

完成二叉樹的橫向優先搜尋（求一棵二叉樹的寬度）

思路：寬度周遊用隊列，先進先出

1. 先把頭節點放入隊列
2. 彈出就列印
3. 先放左再放右

public static void width(Node head)
{
	if(head == null)
		return ;
	Queue<Node> queue = new LinkedList<>();
	queue.add(head);
	//若還希望每一層的節點個數，周遊到某個節點能知道它是第幾層
	HAshMap<Node, Integer> levelMap = new HashMap<>();
	levelMap.put(head,1);
	int curLevel = 1;//目前在第幾層
	int curLevelNodes = 0;//目前層數的節點個數
	int max = Integer.MIN_VALUE;//等于系統最小
	while(!queue.isEmpty())
	{
		Node cur = queue.poll();
		int curNodeLevel = levelMap,get(cur);
		if(curNodeLevel == curLevel)//如果目前來到的這個層數正是正在統計節點的這個層數，則該層數的nodes就++
		{
			curLevelNodes++;
		}
		else//來到的節點已經來到下一層的節點了，說明上一層的節點已經++結束了，應結算
		{
			max = Math.max(max,curLevelNodes);
			curLevel++;
			curLevelNodes = 1;
		}
//		cout<<cur.value<<" ";
		if(cur.left != null)
		{
			levelMAp.put(cur.left, curNodeLevel+1);
			queue.add(cur.left);
		}
		if(cur.right != null)
		{
			levelMAp.put(cur.right, curNodeLevel+1);
			queue.add(cur.right);
		}
	}
}
           

若不用哈希表但希望能知道它的層數

設定幾個變量

Node Cur_end 目前彈出的節點所在層中的最後一個節點

1. Cur_end是最新彈出隊列的節點
2. Next_end是最新進隊的節點
3. 在一層結束後，Cur_end的值修改為Next_end的值，max與目前的Cur_levelNode做大小比較，Next_end标空