想想大学已经上了三年了，马上就要毕业，自己竟然还没有写过博客。写博客是我很早就想做的一件事情，但是一直因为其它事情（其实还是自己懒。。。）而没有把它付诸实践。

最近因为太无聊了（哈哈哈），也在复习数据结构，所以就想把它记录下来，以便日后复习可以用到，也希望对大家有点用吧。

以后会经常更新，希望可以养成一个好的习惯。

做一件事情最好的时刻是过去，其次是现在,想写博客的朋友也开始行动起来吧!

（不罗嗦了，进入正文）

 

 

二叉树的遍历是指通过一定顺序访问二叉树的所有结点。

遍历方法：先序遍历、中序遍历、后序遍历、层次遍历

访问顺序：

先序遍历：根结点--》左子树--》右子树

中序遍历：左子树--》根结点--》右子树

后序遍历：左子树--》右子树--》根结点

层次遍历：按层次顺序从根结点向下逐层进行遍历，且对同一层次的结点从左到右遍历

先序遍历

链表实现

void preorder(node *root){ if(root==NULL){ return; //到达空树，递归边界 } printf("%d\n",root->data); //访问左子树 preorder(root->lchild); //访问右子树 preorder(root->rchild); }

数组实现

void preorder(int root){ if(root==-1) return; printf("%d\n",Node[root].data); //访问左子树 preorder(Node[root].lchild); //访问右子树 preorder(Node[root].rchild); }

中序遍历

链表实现

void inorder(node *root){ if(root==NULL)} return; } //访问左子树 inorder(root->lchild) //访问根结点，例如将其数据输出 printf("%d\n",root->data); //访问右子树 inorder(root->rchild); }

数组实现

void inorder(int root){ if(root==-1) return; //访问左子树 inorder(Node[root].lchild); //访问根节点，例如将其数据输出 printf("%d\n",Node[root].data); //访问右子树 inorder(Node[root].rchild); }

后续遍历

链表实现

void postorder(node* root){ if(root==NULL){ return; } //访问左子树 postorder(root->lchild); //访问右子树 postorder(root->rchild); //访问根结点，例如将其数据输出 printf("%d\n",root->data); }

数组实现

void postorder(int root){ if(root==-1) return; //访问左子树 postorder(Node[root].lchild); //访问右子树 postorder(Node[root].rchild); //访问根节点，例如将其数据取出 printf("%d\n",Node[root].data); }

层次遍历

链表实现

void LayerOrder(node* root){ queue<node*> q; //注意队列里存放地址 q.push(root); //将根地址入队 while(!q.empty()){ node* now = q.front(); //取出队首元素 q.pop(); printf("%d\n",now->data); //访问队首元素 if(now->lchild!=NULL) q.push(now->lchild); //左子树非空 if(now->rchild!=NULL) q.push(now->rchild); //右子树非空 } }

数组实现

void LayerOrder(int root){ queue<int> q; //此处队列里存放结点下标 q.push(root); //将根结点地址入队 while(!q.empty()){ int now = q.front(); //取出队首元素 q.pop(); printf("%d\n",Node[now].data); //访问队首元素 if(Node[now].lchild !=-1) q.push(Node[now].lchild); //左子树非空 if(Node[now].rchild !=-1) q.push(Node[now].rchild); //右子树非空 } }