6.二叉树——1.层次建树与遍历

本文主要是介绍6.二叉树——1.层次建树与遍历，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

层次建树的逻辑

1. 创建根节点 TreeNode * root=NULL
2. 创建一个队列，用于保存将要插入的位置（先进先出）
3. 读取字符：
   • 如果不是#，表明是非空结点，创建一个TreeNode对象，把该对象的左右孩子入队；然后判断root是否空
     • 若空，直接插入，让root指向新的TreeNode对象
     • 非空，访问队列找到本次插入的位置，插入
   • 若是#，访问队列，找到本次插入的位置，置为空指针，然后出队

代码

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;struct TreeNode{int data;TreeNode * leftChild;TreeNode * rightChild;
};
struct QueueNode{TreeNode *parent;bool isLeftIn;
};//插入操作会修改root（main函数中申请）的指向，所以需要使用引用
void insertTreeNode(TreeNode *&root,queue<QueueNode*> &myQueue,char data){if (data!='#'){//创建二叉树结点,在堆上创建，因为是在被调函数内创建TreeNode *newNode = new TreeNode;(*newNode).data = data;//*运算的优先级没有.高//或者：(*p).member等价于p->member//入队QueueNode* que = new QueueNode;que->parent = newNode;que->isLeftIn = false;myQueue.push(que);//插入操作if (root==NULL){//插入的第一个结点root = newNode;} else{//插入的不是根//parent用于定位插入结点的父亲位置QueueNode * Qparent = myQueue.front();if (Qparent->isLeftIn){Qparent->parent->leftChild = newNode;Qparent->isLeftIn= true;} else{Qparent->parent->rightChild = newNode;myQueue.pop();delete Qparent;//出队后，原来的队首元素没有用了}}} else{//是#，表明要插入一个空节点if (root!=NULL){//队列不为空QueueNode * Qparent = myQueue.front();if (Qparent->isLeftIn== false){Qparent->parent->leftChild=NULL;Qparent->isLeftIn= true;} else{Qparent->parent->rightChild = NULL;myQueue.pop();delete Qparent;//出队后，原来的队首元素没有用了}}}
}
int main() {TreeNode *root=NULL ;//根节点char list[] = "abc##de#g##f###";queue<QueueNode*> myQueue;//队列每个元素存储了新节点的父亲位置，以及是否插入过左孩子for (int i = 0; list[i]!='\0'; ++i) {insertTreeNode(root,);}return 0;
}

二叉树遍历

层次遍历：广度优先（使用队列）

• 访问起点，把起点的邻居（左右孩子）加入队列
• 按照队列出队顺序，把访问结点的邻居（左右孩子）加入队列

代码

void levelOrder(TreeNode *root){queue<TreeNode*> pos;//存储将要访问的结点地址pos.push(root);while(pos.empty()== false){TreeNode *pCur = pos.front();//找到队头pos.pop();//出队//访问队头printf("%c",pCur->data);//把队首的邻居加入队列if (pCur->leftChild!=NULL){pos.push(pCur->leftChild);}if (pCur->rightChild!=NULL){pos.push(pCur->rightChild);}}printf("\n");
}

递归遍历

先序遍历

void preOrder(TreeNode* root){if (root==NULL){return;}printf("%c",root->data);preOrder(root->leftChild);preOrder(root->rightChild);
}

中序遍历

void preOrder(TreeNode* root){if (root==NULL){return;}preOrder(root->leftChild);printf("%c",root->data);preOrder(root->rightChild);
}

后序遍历

void preOrder(TreeNode* root){if (root==NULL){return;}preOrder(root->leftChild);preOrder(root->rightChild);printf("%c",root->data);
}

本文代码全家福

#include <cstdio>
#include <string>
#include <map>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
using namespace std;struct TreeNode{char data;TreeNode * leftChild;TreeNode * rightChild;
};
struct QueueNode{TreeNode *parent;bool isLeftIn;
};//插入操作会修改root（main函数中申请）的指向，所以需要使用引用
void insertTreeNode(TreeNode *&root,queue<QueueNode*> &myQueue,char data){if (data!='#'){//创建二叉树结点,在堆上创建，因为是在被调函数内创建TreeNode *newNode = new TreeNode;(*newNode).data = data;//*运算的优先级没有.高//或者：(*p).member等价于p->member//入队QueueNode* que = new QueueNode;que->parent = newNode;que->isLeftIn = false;myQueue.push(que);//插入操作if (root==NULL){//插入的第一个结点root = newNode;} else{//插入的不是根//parent用于定位插入结点的父亲位置QueueNode * Qparent = myQueue.front();if (!Qparent->isLeftIn){Qparent->parent->leftChild = newNode;Qparent->isLeftIn= true;} else{Qparent->parent->rightChild = newNode;myQueue.pop();delete Qparent;//出队后，原来的队首元素没有用了}}} else{//是#，表明要插入一个空节点if (root!=NULL){//队列不为空QueueNode * Qparent = myQueue.front();if (Qparent->isLeftIn== false){Qparent->parent->leftChild=NULL;Qparent->isLeftIn= true;} else{Qparent->parent->rightChild = NULL;myQueue.pop();delete Qparent;//出队后，原来的队首元素没有用了}}}
}
void levelOrder(TreeNode *root){queue<TreeNode*> pos;//存储将要访问的结点地址pos.push(root);while(pos.empty()== false){TreeNode *pCur = pos.front();//找到队头pos.pop();//出队//访问队头printf("%c",pCur->data);//把队首的邻居加入队列if (pCur->leftChild!=NULL){pos.push(pCur->leftChild);}if (pCur->rightChild!=NULL){pos.push(pCur->rightChild);}}printf("\n");
}
void preOrder(TreeNode* root){if (root==NULL){return;}printf("%c",root->data);preOrder(root->leftChild);preOrder(root->rightChild);
}
void midOrder(TreeNode* root){if (root==NULL){return;}preOrder(root->leftChild);printf("%c",root->data);preOrder(root->rightChild);
}
void aftOrder(TreeNode* root){if (root==NULL){return;}preOrder(root->leftChild);preOrder(root->rightChild);printf("%c",root->data);
}
int main() {TreeNode *root=NULL ;//根节点char list[] = "abc##de#g##f###";queue<QueueNode*> myQueue;//队列每个元素存储了新节点的父亲位置，以及是否插入过左孩子for (int i = 0; list[i]!='\0'; ++i) {insertTreeNode(root,myQueue,list[i]);}levelOrder(root);preOrder(root);printf("\n");midOrder(root);printf("\n");aftOrder(root);return 0;
}

这篇关于6.二叉树——1.层次建树与遍历的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---