宁德城乡建设部网站网站域名查询ip
一、二叉树
在计算机科学中，树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构。二叉树是每个节点最多有两个子树的有序树。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。值得注意的是，二叉树不是树的特殊情形。在图论中，二叉树是一个连通的无环图，并且每一个顶点的度不大于3。有根二叉树还要满足根结点的度不大于2。有了根结点后，每个顶点定义了唯一的根结点，和最多2个子结点。然而，没有足够的信息来区分左结点和右结点。二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。二叉树的第i层至多有2的 i -1次方个结点；深度为k的二叉树至多有2^(k) -1个结点；对任何一棵二叉树T，如果其终端结点数(即叶子结点数)为n0，度为2的结点数为n2，则n0 = n2 + 1。
二、二叉树的遍历
前序遍历（DLR）
前序遍历也叫做先根遍历，可记做根左右。
前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问根结点，然后遍历左子树，最后遍历右子树。
若二叉树为空则结束返回，否则：
（1）访问根结点
（2）前序遍历左子树
（3）前序遍历右子树
注意的是：遍历左右子树时仍然采用前序遍历方法。
中序遍历（LDR）
中序遍历也叫做中根遍历，可记做左根右。
中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：
若二叉树为空则结束返回，否则：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树。
注意的是：遍历左右子树时仍然采用中序遍历方法。
后序遍历（LRD）
后序遍历也叫做后根遍历，可记做左右根。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点。在遍历左、右子树时，仍然先遍历左子树，再遍历右子树，最后访问根结点。即：
若二叉树为空则结束返回，否则：
（1）后序遍历左子树。
（2）后序遍历右子树。
（3）访问根结点。
注意的是：遍历左右子树时仍然采用后序遍历方法。
1，二叉树的链式存储
typedef struct bitnode{char data;struct bitnode *lchild,*rchild;
}bitnode,*bitree;2，以先序建立二叉树
利用递归函数进行创建，建立字符型，当遇到‘#’的时候结束
int creatbitree(bitree &t){char ch;if(cin>>ch&&ch=='#'){t=NULL;return false;
}else{t=(bitree)malloc(sizeof(bitnode));t->data=ch;creatbitree(t->lchild);creatbitree(t->rchild);}return ok;
}3，对二叉树进行递归遍历，先展示先序递归遍历
int prebitree(bitree &t){if(t){visit(t->data);prebitree(t->lchild);prebitree(t->rchild);}return ok;
}//先序递归遍历4，中序递归遍历（这三个遍历比较简单，主要是电脑进行操作，这里不进行说明）
int midbitree(bitree &t){if(t){midbitree(t->lchild);visit(t->data);midbitree(t->rchild);}return ok;
}//中序递归遍历5，后序递归遍历
int houbitree(bitree &t){if(t){houbitree(t->lchild);houbitree(t->rchild);visit(t->data);}return ok;
}//后序递归遍历现在开始介绍二叉树的三种非递归遍历，非递归遍历主要是借助栈的思想进行进栈和出栈操作，从而达到三种非递归遍历，前序和中序相对后序能简单一点，希望大家好好理解后序的代码。
6，先序的非递归代码
int pre_bitree(bitree t){stack<bitree>stack;bitree p=t;while(p||!stack.empty()){if(p!=NULL){cout<<p->data<<" ";//先输出根结点stack.push(p);//p=p->lchild;}else{p=stack.top();stack.pop();p=p->rchild;}
}
return ok;
}7，中序的非递归代码
int mid_bitree(bitree t){stack<bitree>stack;bitree p=t;while(p||!stack.empty()){if(p!=NULL){stack.push(p);//先让根结点进栈。p=p->lchild;//然后让左子树进栈}else{p=stack.top();//获得栈顶元素stack.pop();//删除栈顶元素cout<<p->data<<" ";//输出栈顶元素p=p->rchild;//让右子树进栈}}return ok;//这一部分看图就可以理解
}8，后序的非递归代码
int hou_bitree(bitree t){stack<bitree>stack;bitree e,previsit;//e表示可移动的结点，pre表示已将访问过的上一个结点e=t;while(e){stack.push(e);//根节点进栈e=e->lchild;//左子树进栈}while(e||!stack.empty()){e=stack.top();stack.pop();if(e->rchild==NULL||e->rchild==previsit){cout<<e->data<<" ";previsit=e;//这个标记很重要，最后重复利用他}else{stack.push(e);//因为前面删除了一次根节点，所以根节点再次进栈e=e->rchild;//让右子树进栈while(e){stack.push(e);e=e->lchild;//让右子树中的左子树进栈}}}输入：abc##de##f##即可验证
完整代码展示
#include<iostream>
#include<cstdio>
#include<stack>
#define false 0
#define ok 1
#define stack_size 100
using namespace std;
typedef struct bitnode{char data;struct bitnode *lchild,*rchild;
}bitnode,*bitree;
//创建一个二叉树（以先序建立）
int creatbitree(bitree &t){char ch;if(cin>>ch&&ch=='#'){t=NULL;return false;
}else{t=(bitree)malloc(sizeof(bitnode));t->data=ch;creatbitree(t->lchild);creatbitree(t->rchild);}return ok;
}
void visit(char data){cout<<data<<" ";
}
//递归运算三种遍历
int prebitree(bitree &t){if(t){visit(t->data);prebitree(t->lchild);prebitree(t->rchild);}return ok;
}//先序递归遍历
int midbitree(bitree &t){if(t){midbitree(t->lchild);visit(t->data);midbitree(t->rchild);}return ok;
}//中序递归遍历
int houbitree(bitree &t){if(t){houbitree(t->lchild);houbitree(t->rchild);visit(t->data);}return ok;
}//后序递归遍历
int pre_bitree(bitree t){stack<bitree>stack;bitree p=t;while(p||!stack.empty()){if(p!=NULL){cout<<p->data<<" ";//先输出根结点stack.push(p);//p=p->lchild;}else{p=stack.top();stack.pop();p=p->rchild;}
}
return ok;
}
int mid_bitree(bitree t){stack<bitree>stack;bitree p=t;while(p||!stack.empty()){if(p!=NULL){stack.push(p);//先让根结点进栈。p=p->lchild;//然后让左子树进栈}else{p=stack.top();//获得栈顶元素stack.pop();//删除栈顶元素cout<<p->data<<" ";//输出栈顶元素p=p->rchild;//让右子树进栈}}return ok;//这一部分看图就可以理解
}
int hou_bitree(bitree t){stack<bitree>stack;bitree e,previsit;//e表示可移动的结点，pre表示已将访问过的上一个结点e=t;while(e){stack.push(e);//根节点进栈e=e->lchild;//左子树进栈}while(e||!stack.empty()){e=stack.top();stack.pop();if(e->rchild==NULL||e->rchild==previsit){cout<<e->data<<" ";previsit=e;//这个标记很重要，最后重复利用他}else{stack.push(e);//因为前面删除了一次根节点，所以根节点再次进栈e=e->rchild;//让右子树进栈while(e){stack.push(e);e=e->lchild;//让右子树中的左子树进栈}}}return ok;
}
int main(int argc, char const *argv[]) {bitree t;creatbitree(t);prebitree(t);cout<<"_____________________________"<<endl;midbitree(t);cout<<"_____________________________"<<endl;houbitree(t);cout<<"_____________________________"<<endl;pre_bitree(t);cout<<"_____________________________"<<endl;mid_bitree(t);cout<<"_____________________________"<<endl;hou_bitree(t);cout<<"_____________________________"<<endl;cout<<endl;return 0;
}
编译结果
