二叉树

一.建立（以‘#’作为空子节点）

1.前序建立，递归思想

注意输入时要将每一个非空节点的子节点写为空才可结束递归，例如输入ABCD#E#####

typedef struct BiTNode { struct BiTNode *lchild; struct BiTNode *rchild; char data; } BiTreeNode, *BiTree; BiTree Create(BiTree &S) { char a; cin>>a; if (a== '#')S = NULL; else { S=(BiTNode *)malloc(sizeof(BiTNode)); S->data = a; S->lchild = Create(S->lchild); S->rchild = Create(S->rchild); } return S; }

2.由已知的字符串按照满二叉树结构建立二叉树

例如 ABCD##E

显然以前序建立的方法不能满足要求，所以建立采用了以下方法，主要用了一个字符串来储存字符串，然后依次建立，思想也是递归

void Create(BiTree *&s,char a[],int n) { if(n>=strlen(a)||a[n]=='#')s=NULL; else { s=(BiTNode*)malloc(sizeof(BiTNode)); s->data=a[n]; Create(s->lchild,a,2*n+1); Create(s->rchild,a,2*(n+1)); } }

3.数组存储，但因为很容易浪费空间，此处不做赘述

二.遍历

三种：前序，中序，后序

前序：根节点，左子树，右子树

中序：左子树，根节点，右子树

后序：左子树，右子树，根节点                               

举例

前序：ABDEGCFH       中序：DBGEACHF      后序：DGEBHFCA

代码实现，三种遍历此处都用递归来实现

void Preorder(BiTree *&s)//前序遍历 { if(s) { cout<<s->data<<' '; Preorder(s->lchild); Preorder(s->rchild); } } void Midorder(BiTree *&s)//中序遍历 { if(s) { Midorder(s->lchild); cout<<s->data<<' '; Midorder(s->rchild); } } void Postorder(BiTree *&s)//后序遍历 { if(s) { Postorder(s->lchild); Postorder(s->rchild); cout<<s->data<<' '; } }

平衡二叉树

/* 基本操作 node *root=NULL; root=insert(root,1); find(root,1) */ struct node { int val; node *lch; node *rch; }; //插入数值 node *insert(node *p,int x) { if(p==NULL) { node *q=new node; q->val=x; q->lch=q->rch=NULL; return q; } else { if(x<p->val) { p->lch=insert(p->lch,x); } else { p->rch=insert(p->rch,x); } return p; } } //查找数值 bool find(node *p,int x) { if(p==NULL)return false; else if(x==p->val)return true; else if(x<p->val) return find(p->lch,x); else return find(p->rch,x); } //删除数值 node *remove(node *p.int x) { if(p==NULL)return NULL; else if(x<p->val)p->lch=remove(p->lch,x); else if(x>p->val)p->rch=remove(p->rch,x); else if(p->lch==NULL) { node*q=p->lch; delete p; return q; } else if(p->lch->rch==NULL) { node*q=p->lch; q->rch=p->lch; delete p; return q; } else { node *q; for(q=p->lch;q->rch->rch!=NULL;q=q->lch); node *r=q->rch; q->rch=r->lch; r->lch=p->lch; r->rch=p->rch; delete p; return r; } return p; }