@[TOC]二叉树代码部分
二叉树的链式存储结构
typedef struct bitnode{ Elemtype data; struct bitnode *lchild ,*rchild; }bidnode ,*bitree
二叉树的遍历(递归调用)
先序遍历：
void preorder(bitree (T)) if（T!=NULL）{ visit(T); preorder(T->lchild); preorder(T->rchild); } }
中序遍历：
void inorder(bitree T）{ if(T!=NULL){ inorder (T->lchild); visit(T); inorder(T->rchild); } }
后序遍历：
void postorder(bitree){ if(T!=NULL){ postorder(T->lchild); postorder(T->rchild); visit(T); } }
递归算法和非递归算法的转化
中序遍历的非递归调用算法：
void inorder2(bitree T){ initstack(s);//初始化了一个栈s bitree p=T;//把T的地址给了指针变量p while(p||!Isempty(S)){ //啥时候循环？p=1即p不空，!Isempty(s)是指栈不空；最后栈空而且p=NULL if(p){ push(s,p); p=p->lchild } else{ pop(s,p);//意思就是出栈栈顶元素（这里的p你就理解成栈顶元素的地址就行了） visit(p); p=p->rchild; } } }
先序遍历的非递归算法：
void preorder2(bitree T){ initstack(s); bitree p=T; while(p||!isempty(S)){ if(p){ visit(p);//先访问p结点 push(s,p);//把该点压入栈中 p=p->lchild;//把左孩子的结点的地址给变量p } else{ pop(s,p); p=p->rchild; } } }
后序遍历的非递归算法:
void levellorder(bitree T){ initqueue(Q);//初始化队列 Bitree p;//定义p指针，指向二叉树结点类型的结构 Enqueue(Q,p);//根结点入队； while(!Isempty(Q)){ Dequeue(Q,p);//出队 visit(p); if(p->lchild!=NULL) enqueue(q,p->lchild); if(p->rchild!=NULL) enqueue(q,p->rchild); } }
线索二叉树
线索二叉树的储存结构;
typedef struct threadnode{ elemtype data; struct threadnode *lchild,*rchild; int ltag,rtag; }threadnode,*threadtree;
中序线索二叉树的构造：
void createinthread(threadtree T){ threadtree pre=NULL; if(T!=NULL){ inthread(T,pre);//非空二叉树 线索化 pre->rchild=NULL;//处理遍历的最后一个结点 pre->rtag=1; } } void inthread(threadtree &p,threadtree &pre){ if(p!=NULL){ InThread(p->lchild,pre); if(p->lchild==NULL){ P->lchild=pre; p->ltag=1; } if(pre!=NULL&&pre->rchild==NULL) pre->rchild=p; pre->rtag=1; } pre=p; inthread(p->rchild,pre); }
中序线索二叉树的遍历
threadnode *firstnode(threadnode *p){ while(p->ltag==0) p=p->lchild; return p; } threadnode *nextnode(threadnode *p){ if(p->rtag==0) return firstnode(p->rchild); else return p->rchild; } void inorder (threadnode *p){ for(threadnode*p=firstnode(T);p=NULL;p=Nextnode(p)) visit(p); }
树的存储结构
双亲表示法：
#define max_tree_size 100 typedef struct{ elemtype data; int parent; }ptnode; typedef struct{ ptnode nodes[max_tree_size]; int n; }ptree;
孩子表示法：
#define max_tree_size 100 typedef struct{ int child; struct cnode *next; }cnode; typedef struct{ elemtype data; struct cnode *child; }pnode; typedef struct{ pnode nodes[max_tree_size]; int n; }ctree;
孩子兄弟表示法;
typedef struct csnode{ elemtype data; struct csnode *firstchild,*nextsibling; }csnode,cstree;
并查集
并查集采用的是双亲表示(顺序存储结构)：
结构定义如下： #define max_tree_size 100 typedef struct{ elemtype data; int parent; }ptnode; typedef struct{ ptnode nodes[max_tree_size]; int n; }ptree; 由于data与数组编号一样的，那么就不需要上面这样定义结构体了 直接定义一个一维数组就可以了； 并查集结构定义如下： #define SIZE 100 int ufsets[SIZE]; 初始化： Initial(S); void Initial(int S[]){ for(int i=0;i<size;I++) S[I]=-1; } 查找操作： Find(S,x); int Find(int S[],int x){ while(S[x]>=0) x=S[x]; return x; } 合并操作： Union（S,Root1,Root2); void Union(int S[],int root1,int root2){ S[Root2]=Root1; }
树与二叉树的应用
二叉排序树
查找非递归调用算法： BSTnode *BST_search(bitree T,Elemtype key{ while(T!=NULL&&key!=T->data){ if(key<T->data) T=T->lchild; else T=T->rchild; } return T; } 插入： int BST_Insert (Bitree &T,KeyType k){ if(T==NULL){ T=(BiTree)malloc(sizeof(BSTNode)); T->key=k; T->lchild=T->rchild=NULL; return 1; } else if(k==T->key) return 0; else if(k<T->key) return BST_Insert(T->lchild,k); else return BST_insert(T->rchild,k); } 构造： void Creat_BST(Bitree &T,KeyType str[],int n){ T=NULL; int i=0; while(i<n){ BST_Insert(T,str[i]); i++; } }
平衡二叉树：
判断： void Judge AVL(Bitree bt,int &balance ,int &h){//bt是一个树的指针地址，balance,h分别是两个可以改变的数值.balance 1是平衡，0是不平衡 //为什么用引用，因为把该类型的变量传入函数中，调用的函数会对参数进行修改，之后要利用这些修改的参数值，所以用引用； int bl=0,br=0,hl=0,hr=0; if(bt==NULL){ h=0; balance=1; } else if(bt->lchild==NULL&&bt->rchild==NULL){ h=1; balance=1; } else{ Judge_AVL(bt->lchild,b1,h1);//函数调用 Judge_AVL(bt->rchild,br,hr); if(hl>hr) h=hl+1; else h=hr+1; if(abs(h1-hr)<2&&b1==1&&br==1) balance=1; else balance=0; } }
二叉树的应用
哈夫曼编码
固定长度编码：000001010010011100101011010110 helloworld 000 h 001 e 010 l 011 o 100 w 101 r 110 d
可变长度编码： helloworld:0001001101110000 00 h 01 e 0 l 1 o 10 w 11 r 000但是这种可变编码是无法实现的
