文章目录
一、建立一个排序二叉树二、四种遍历前言
这里先给出建立一颗普通的排序二叉树，平衡二叉树的建立以及操作，等复习到再写吧。
一、排序二叉树
排序二叉树，即当前节点左子树 < 当前节点 < 当前节点的右子树 的特殊的二叉树，便于查找。
排序二叉树的构造很简单，使用三个树节点指针。currentNode(指向当前遍历节点地址的指针) parentNode(保存当前遍历节点的父节点地址的指针) ，和一个新节点指针newNode
每插入一个新节点，移动这三个指针，即在树上找到合适的位置插入新节点
代码如下：
currentNode = root;while(currentNode!=NULL){parentNode = currentNode; //当cur 是空的时候 结束循环 此时par 就是 cur的父节点if(currentNode->date > newNode->date){currentNode = currentNode->lchild;}else{currentNode = currentNode->rchild;}}if(parentNode->date > newNode->date) //找到位置了，新节点要插在这个par下面parentNode->lchild = newNode; //再判断一下elseparentNode->rchild = newNode;
二、四种遍历
模板一样的东西，记下来就行了。挺简单的。
void PreOrder(BiTree root){if(root!=NULL){cout<<root->date<<" ";PreOrder(root->lchild);PreOrder(root->rchild);}}void InOrder(BiTree root){if(root!=NULL){InOrder(root->lchild);cout<<root->date<<" ";InOrder(root->rchild);}}void PostOrder(BiTree root){if(root!=NULL){PostOrder(root->lchild);PostOrder(root->rchild);cout<<root->date<<" ";}}void LevelOrder(BiTree root){if(root==NULL){cout<<"当前树为空"<<endl;}q.push(root);BiTNode *cur=NULL;while(!q.empty()) {cur= q.front(); //遍历当前节点 q.pop();cout<<cur->date<<" ";if(cur->lchild) q.push(cur->lchild); //左孩子有孩子入队列 if(cur->rchild) q.push(cur->rchild); }}
一个完整的实例
树结构如下：
先序遍历结果：5 4 2 1 3 8 7 6 9
中序遍历结果：1 2 3 4 5 6 7 8 9
后序遍历结果：1 3 2 4 6 7 9 8 5
层次遍历结果：5 4 8 2 7 9 1 3 6
#include<iostream>#include<queue>using namespace std;//排序二叉树 typedef int ElemType;typedef struct BiTNode{ElemType date;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree; queue<BiTNode*> q; //层次遍历用 BiTree add(BiTree root,int e){BiTNode *newNode=NULL; //新结点指针 BiTNode *currentNode=NULL; //当前遍历到的节点指针 BiTNode *parentNode=NULL; //父节点指针 newNode = (BiTNode*)malloc(sizeof(BiTNode));newNode->date=e;newNode->lchild=NULL;newNode->rchild=NULL;if(root==NULL) //第一个节点建立 {return newNode;}else //往下找 {currentNode = root;while(currentNode!=NULL){parentNode = currentNode;if(currentNode->date > newNode->date){currentNode = currentNode->lchild;}else{currentNode = currentNode->rchild;}}if(parentNode->date > newNode->date)parentNode->lchild = newNode;elseparentNode->rchild = newNode;} return root;}BiTree CreateBtree(int e[],int len){BiTree root = NULL;//根节点指针初始为空 for(int i=1;i<=len;i++){root = add(root,e[i]);}return root;} void PreOrder(BiTree root){if(root!=NULL){cout<<root->date<<" ";PreOrder(root->lchild);PreOrder(root->rchild);}}void InOrder(BiTree root){if(root!=NULL){InOrder(root->lchild);cout<<root->date<<" ";InOrder(root->rchild);}}void PostOrder(BiTree root){if(root!=NULL){PostOrder(root->lchild);PostOrder(root->rchild);cout<<root->date<<" ";}}void LevelOrder(BiTree root){if(root==NULL){cout<<"当前树为空"<<endl;}q.push(root);BiTNode *cur=NULL;while(!q.empty()) {cur= q.front(); //遍历当前节点 q.pop();cout<<cur->date<<" ";if(cur->lchild) q.push(cur->lchild); //左孩子有孩子入队列 if(cur->rchild) q.push(cur->rchild); }}int main(){int len;BiTree root = NULL;cin>>len;int e[len+1]; for(int i=1;i<=len;i++){cin>>e[i];}root=CreateBtree(e,len);cout<<"先序结果：";PreOrder(root);cout<<endl;cout<<"中序结果："; InOrder(root);cout<<endl;cout<<"后序结果：";PostOrder(root);cout<<endl;cout<<"层次结果："; LevelOrder(root);return 0;}
<iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width=330 height=86 src="///outchain/player?type=2&id=1362193347&auto=0&height=66"></iframe>
