1、二叉树的建立
#include<iostream> #include<stdlib.h> using namespace std; typedef struct BTNode{ char data; struct BTNode *lchild; struct BTNode *rchild; }BTNode; void createBTree(BTNode *&root) { char c; cin>>c; fflush(stdin); if(c=='#') { root=NULL; } else { root=(BTNode *)malloc(sizeof(BTNode)); root->data=c; cout<<"please print the left child"<<endl; createBTree(root->lchild); cout<<"please print the right child"<<endl; createBTree(root->rchild); } } int main() { BTNode *root; createBTree(root); }
2、二叉树的先序中序后序递归遍历
//二叉树的先序递归遍历 void preorderRaversal(BTNode *root) { if(root) { cout<<root->data<<" "; preorderRaversal(root->lchild); preorderRaversal(root->rchild); } } //二叉树的中序递归遍历 void inorderRaversal(BTNode *root) { if(root) { inorderRaversal(root->lchild); cout<<root->data<<" "; inorderRaversal(root->rchild); } } //二叉树的后续递归遍历 void postorderRaversal(BTNode *root) { if(root) { postorderRaversal(root->lchild); postorderRaversal(root->rchild); cout<<root->data<<" "; } }
3、二叉树的递归求深
int getDepth(BTNode *root) { int LD,RD; if(!root) return 0; else { LD=getDepth(root->lchild); RD=getDepth(root->rchild); return (LD>RD ? LD:RD)+1; } }
4、二叉树的先序非递归遍历
对任一节点p
1)访问p节点,并将p节点入栈
2)判断p节点的左孩子是否为空,若为空,则取栈顶节点并进行出栈操作,并将p右孩子置为当前的节点p,循环至1),若不为空,则将p的左孩子置为p
3)直到p为NULL,并且栈为空
//二叉树的先序非递归遍历 void preorderRaversal2(BTNode *root) { const stack<BTNode>::size_type stackSize=100; //给定栈的大小 stack<BTNode> BTNodeStack; //定义一个空栈 BTNode *p=root; while(p||!BTNodeStack.empty()) { while(p) { cout<<p->data<<" "; BTNodeStack.push(*p); p=p->lchild; } if(!BTNodeStack.empty()) { p=&BTNodeStack.top(); BTNodeStack.pop(); p=p->rchild; } } }
5、二叉树的中序非递归遍历
//中序非递归遍历 void inorderRaversal2(BTNode *root) { const stack<BTNode>::size_type stackSize=100; //给定栈的大小 stack<BTNode> BTNodeStack; //定义一个空栈 BTNode *p=root; while(p||!BTNodeStack.empty()) { while(p) { BTNodeStack.push(*p); p=p->lchild; } if(!BTNodeStack.empty()) { p=&BTNodeStack.top(); BTNodeStack.pop(); cout<<p->data<<" "; p=p->rchild; } } }
6、二叉树的后序非递归遍历
typedef enum{L,R} tagtype; typedef struct { BTNode *p; tagtype tag; }stacknode; void postorderRaversal2(BTNode *root) { const stack<stacknode>::size_type stackSize=100; //给定栈的大小 stack<stacknode> BTNodeStack; //定义一个空栈 BTNode *p=root; stacknode x; do { while (p) { x.p=p; x.tag=L; BTNodeStack.push(x); p=p->lchild; } while(!BTNodeStack.empty()&&BTNodeStack.top().tag==R) { x=BTNodeStack.top(); BTNodeStack.pop(); p=x.p; cout<<p->data<<" "; } if(!BTNodeStack.empty()) { BTNodeStack.top().tag=R; p=BTNodeStack.top().p->rchild; } }while(!BTNodeStack.empty()); }