C/C++教程

关于二叉树遍历的反思(C++)

本文主要是介绍关于二叉树遍历的反思(C++),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 二叉树函数
  • 递归序
  • 递归遍历
  • 非递归遍历

全文基于左程云老师的教学,感谢左程云老师!

二叉树函数

struct treenode {
     node* left;
     node* right;
     int val;
     node(int x){val=x;}
}*Node;

递归序

递归序是指在递归过程中实际访问的节点顺序

例如树{1,2,3,4,5,6,7}

根据递归行为可知其递归序为:1,2,4,4,4,2,5,5,5,2,1,3,6,6,6,3,7,7,7,3,1

递归遍历

先序遍历(头左右):打印第一次出现的节点:1,2,4,5,3,6,7

void preorder(Node head) {
     if(head==NULL)return;
     
     cout << head->val;
     preorder(head->left);
     preorder(head->right);
}

中序遍历(左头右):打印第二次出现的节点:4,2,5,1,6,3,7

void inorder(Node head) {
     if(head==NULL)return;
    
     inorder(head->left);
     cout << head->val;
     inorder(head->right);
}

后序遍历(右头左):打印第三次出现的节点:4,5,2,6,7,3,1

void postorder(Node head) {
     if(head==NULL)return;
     
     postorder(head->left);
     postorder(head->right);
     cout << head->val;
}

非递归遍历

先序遍历(头左右):1,2,4,5,3,6,7

先放右再放左,因为栈先进后出

void preorder(Node head) {
     if(head!=NULL) {
        stack<Node>stack;
        stack.push(head);
        while(!stack.empty()) {
          head = stack.top();
          stack.pop();
          cout << head->val << " ";
          if(head->right) {
            stack.push(head->right);
          }
          if(head->left) {
            stack.push(head->left);
          }
       }
     }
}

后序遍历(右头左):4,5,2,6,7,3,1

准备一个辅助栈进行打印(可以直接用队列)

void postorder(Node head) {
     if(head!=NULL) {
        stack<Node>stack1;
        stack<Node>stack2;
        stack1.push(head);
        while(!stack1.empty()) {
          head = stack1.top();
          stack1.pop();
          stack2.pop();
          cout << head->val << " ";
          if(head->left) {
            stack1.push(head->left);
          }
          if(head->right) {
            stack1.push(head->right);
          }
       }
       while(!s2.empty()) {
       	cout << s2.top() << " ";
       	s2.pop();
	   }
     }
}

中序遍历(左头右):4,2,5,1,6,3,7

整棵树左边界进栈,依次弹出节点的过程中,打印,对弹出节点的右树重复

 void postorder(Node head) {
     if(head!=NULL) {
     	stack<Node>stack;
     	while(!stack.empty() || head!=NULL) {
     		if(head!=NULL) {
     			stack.push(head);
     			head=head->left;
			 } else {
			 	head=stack.top();
			 	stack.pop();
			 	cout << head->val << " ";
			 	head=head->right;
			 }
		 }
	 }
}

层序遍历(一层一层):1,2,3,4,5,6,7

递归要压两次栈,比较复杂。

所以采取BFS(宽度优先遍历)进行遍历

void floororder(Node head)
{
    queue<Node>q;
    if (head != NULL)
    {
        q.push(head); 
    }

    while (!q.empty())
    {
        cout << q.front()->val << " "; 
        if (q.front()->left)   
        {
            q.push(q.front()->left);   
        }

        if (q.front()->right)   
        {
            q.push(q.front()->right);
        }
        q.pop();
    }
}
这篇关于关于二叉树遍历的反思(C++)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!