二叉樹
概念
二叉樹是一種非常重要的資料結構，非常多其他資料結構都是基于二叉樹的基礎演變而來的。對于二叉樹，有深度周遊和廣度周遊，深度周遊有前序、中序以及後序三種周遊方法，廣度周遊即我們尋常所說的層次周遊。由于樹的定義本身就是遞歸定義，是以採用遞歸的方法去實作樹的三種周遊不僅easy了解并且代碼非常簡潔，而對于廣度周遊來說，須要其他資料結構的支撐。比方堆了。是以。對于一段代碼來說，可讀性有時候要比代碼本身的效率要重要的多。
四種基本的周遊思想
前序周遊：根結點 ---> 左子樹 ---> 右子樹
中序周遊：左子樹---> 根結點 ---> 右子樹
後序周遊：左子樹 ---> 右子樹 ---> 根結點
層次周遊：僅僅需按層次周遊就可以
比如。求以下二叉樹的各種周遊
前序周遊：1 2 4 5 7 8 3 6
中序周遊：4 2 7 5 8 1 3 6
後序周遊：4 7 8 5 2 6 3 1
層次周遊：1 2 3 4 5 6 7 8
一、前序周遊
1）依據上文提到的周遊思路：根結點 ---> 左子樹 ---> 右子樹，非常easy寫出遞歸版本号：
public void preOrderTraverse1(TreeNode root) {
if (root != null) {
System.out.print(root.val+" ");
preOrderTraverse1(root.left);
preOrderTraverse1(root.right);
}
} 
2）如今讨論非遞歸的版本号：
依據前序周遊的順序，優先訪問根結點。然後在訪問左子樹和右子樹。是以。對于随意結點node。第一部分即直接訪問之，之後在推斷左子樹是否為空，不為空時即反複上面的步驟，直到其為空。若為空。則須要訪問右子樹。注意。在訪問過左孩子之後。須要反過來訪問其右孩子。是以，須要棧這樣的資料結構的支援。對于随意一個結點node，詳細過程例如以下：
a)訪問之，并把結點node入棧。目前結點置為左孩子；
b)推斷結點node是否為空，若為空。則取出棧頂結點并出棧，将右孩子置為目前結點；否則反複a)步直到目前結點為空或者棧為空（能夠發現棧中的結點就是為了訪問右孩子才存儲的）
代碼例如以下：
public void preOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
System.out.print(pNode.val+" ");
stack.push(pNode);
pNode = pNode.left;
} else { //pNode == null && !stack.isEmpty()
TreeNode node = stack.pop();
pNode = node.right;
}
}
} 二、中序周遊
1)依據上文提到的周遊思路：左子樹 ---> 根結點 ---> 右子樹，非常easy寫出遞歸版本号：
public void inOrderTraverse1(TreeNode root) {
if (root != null) {
inOrderTraverse1(root.left);
System.out.print(root.val+" ");
inOrderTraverse1(root.right);
}
} 2）非遞歸實作，有了上面前序的解釋，中序也就比較簡單了。同樣的道理。僅僅隻是訪問的順序移到出棧時。代碼例如以下：
public void inOrderTraverse2(TreeNode root) {
Stack<TreeNode> stack = new Stack<>();
TreeNode pNode = root;
while (pNode != null || !stack.isEmpty()) {
if (pNode != null) {
stack.push(pNode);
pNode = pNode.left;
} else { //pNode == null && !stack.isEmpty()
TreeNode node = stack.pop();
System.out.print(node.val+" ");
pNode = node.right;
}
}
} 三、後序周遊
1）依據上文提到的周遊思路：左子樹 ---> 右子樹 ---> 根結點。非常easy寫出遞歸版本号：
public void postOrderTraverse1(TreeNode root) {
if (root != null) {
postOrderTraverse1(root.left);
postOrderTraverse1(root.right);
System.out.print(root.val+" ");
}
} 2）
後序周遊的非遞歸實作是三種周遊方式中最難的一種。由于在後序周遊中，要保證左孩子和右孩子都已被訪問而且左孩子在右孩子前訪問才幹訪問根結點，這就為流程的控制帶來了難題。以下介紹兩種思路。
第一種思路：對于任一結點P，将其入棧，然後沿其左子樹一直往下搜尋。直到搜尋到沒有左孩子的結點，此時該結點出如今棧頂，可是此時不能将其出棧并訪問，是以其右孩子還為被訪問。
是以接下來依照同樣的規則對其右子樹進行同樣的處理，當訪問完其右孩子時。該結點又出如今棧頂，此時能夠将其出棧并訪問。這樣就保證了正确的訪問順序。能夠看出，在這個過程中，每一個結點都兩次出如今棧頂，僅僅有在第二次出如今棧頂時，才幹訪問它。是以須要多設定一個變量辨別該結點是否是第一次出如今棧頂。
void postOrder2(BinTree *root) //非遞歸後序周遊
{
stack<BTNode*> s;
BinTree *p=root;
BTNode *temp;
while(p!=NULL||!s.empty())
{
while(p!=NULL) //沿左子樹一直往下搜尋。直至出現沒有左子樹的結點
{
BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
btn->btnode=p;
btn->isFirst=true;
s.push(btn);
p=p->lchild;
}
if(!s.empty())
{
temp=s.top();
s.pop();
if(temp->isFirst==true) //表示是第一次出如今棧頂
{
temp->isFirst=false;
s.push(temp);
p=temp->btnode->rchild;
}
else //第二次出如今棧頂
{
cout<<temp->btnode->data<<" ";
p=NULL;
}
}
}
} 另外一種思路：要保證根結點在左孩子和右孩子訪問之後才幹訪問，是以對于任一結點P。先将其入棧。假設P不存在左孩子和右孩子。則能夠直接訪問它；或者P存在左孩子或者右孩子。可是其左孩子和右孩子都已被訪問過了。則相同能夠直接訪問該結點。若非上述兩種情況。則将P的右孩子和左孩子依次入棧。這樣就保證了每次取棧頂元素的時候，左孩子在右孩子前面被訪問。左孩子和右孩子都在根結點前面被訪問。
void postOrder3(BinTree *root) //非遞歸後序周遊
{
stack<BinTree*> s;
BinTree *cur; //目前結點
BinTree *pre=NULL; //前一次訪問的結點
s.push(root);
while(!s.empty())
{
cur=s.top();
if((cur->lchild==NULL&&cur->rchild==NULL)||
(pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
{
cout<<cur->data<<" "; //假設目前結點沒有孩子結點或者孩子節點都已被訪問過
s.pop();
pre=cur;
}
else
{
if(cur->rchild!=NULL)
s.push(cur->rchild);
if(cur->lchild!=NULL)
s.push(cur->lchild);
}
}
} 四、廣度優先周遊
也叫層次周遊的代碼比較簡單。僅僅須要一個隊列就可以。先在隊列中增加根結點。之後對于随意一個結點來說。在其出隊列的時候，訪問之。同一時候假設左孩子和右孩子有不為空的。入隊列。代碼例如以下：
public void levelTraverse(TreeNode root) {
if (root == null) {
return;
}
LinkedList<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
TreeNode node = queue.poll();
System.out.print(node.val+" ");
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
} 五、深度優先周遊
事實上深度周遊就是上面的前序、中序和後序。可是為了保證與廣度優先周遊相照顧，也寫在這。代碼也比較好了解，事實上就是前序周遊，代碼例如以下：
public void depthOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()) {
TreeNode node = stack.pop();
System.out.print(node.val+" ");
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
} 六、後序周遊的簡單思路
前序周遊的非遞歸版本，通路順序依次是根節點->左子樹->右子樹，如果将壓棧順序改動一下，可以很容易得到根節點->右子樹->左子樹，觀察這個順序和後序周遊左子樹->右子樹->根節點正好反序。是以，可以考慮使用盞來實作。
vector<int> postorderTraversal(TreeNode* root) {
vector<int> ret;
if(root==NULL) return ret;
stack<TreeNode*> st;
st.push(root);
while(!st.empty())
{
TreeNode* tmp = st.top();
ret.push_back(tmp->val);//先通路根節點
st.pop();
if(tmp->left!=NULL) st.push(tmp->left);//再通路左子樹
if(tmp->right!=NULL) st.push(tmp->right);//最後通路右子樹
}
reverse(ret.begin(),ret.end());//将結果反序輸出
return ret;
} public void postOrderTraverse(Node node) {
if (node == null) {
return;
}
Node temp = node;
Stack<Node> stack = new Stack<>();
List<Node> nodes = new ArrayList<>();
while (temp != null || !stack.isEmpty()) {
if (temp != null) {
nodes.add(temp);
stack.push(temp);
temp = temp.rightChild;
} else {
Node popNode = stack.pop();
temp = popNode.leftChild;
}
}
for (int i = nodes.size() - 1; i >= 0; i--) {
System.out.print(nodes.get(i).data + " ");
}
}