树
一、二叉树
1.1链式存储:
typedef struct BiTNode{
ElemType data; //数据域
struct BiTNode *lchild,*rchild; //左右孩子指针域
}BiTNode,*BiTree;
1.2二叉树的遍历
1.先序遍历
递归算法:
void PreOrder(BiTree T){
if(T!=NULL){
visit(T); //访问根结点
PreOrder(T->lchild); //递归遍历左子树
PreOrder(T->rchild); //递归遍历右子树
}
}
非递归算法:
void preOrder(BTNode *bt){
if(bt!=NULL){
BTNode *Stack[maxSize]; //定义一个栈
int top=-1;
BTNode *p;
Stack[++top]=bt; //根结点入栈
while(top!=-1){ //栈不空时循环
p=Stack[top--];
visit(p); //出栈并访问
if(p->rchild!=NULL) //右孩子存在则入栈
Stack[++top]=p->rchild;
if(p->lchild!=NULL) //左孩子同理
Stack[++top]=p->lchid;
}
}
}
2.中序遍历
递归算法:
void InOrder(BiTree T){
if(T!=NULL){
InOrder(T->lchild); //递归遍历左子树
visit(T); //访问根节点
InOrder(T->rchild); //递归遍历右子树
}
}
非递归算法:
算法思想:
- 根结点入栈
- 循环:走到最左,沿路入栈。栈不空的时候,出栈并访问栈顶P;处理P的右孩子
- 栈空结束
void inorderNonrecursion(BTNode *bt)
{
if(bt!=NULL)
{
BTNode *Stack[maxSize];
int top=-1;
BTNode *p;
p=bt;
while(top!=-1||p!=NULL)
{
while(p!=NULL) //左孩子存在,则左孩子入栈
{
Stack[++top]=p;
p=p->lchild;
}
if(top!=-1) //在栈不空的情况下,出栈并输出栈结点
{
p=Stack[top--];
visit(p); //visit()是访问p的函数,在这里执行打印结点值得操作
p=->rchild;
}
}
}
}
3.后序遍历
递归算法:
void PostOder(BiTree T){
if(T!=NULL){
PostOrder(T->lchild); //递归遍历左子树
PostOrder(T->rchild); //递归遍历右子树
visit(T); //访问根结点
}
}
非递归算法:
算法思想:后序非递归遍历二叉树是先访问左子树,再访问右子树,最后访问根节点。
- 沿着根的左孩子,依次访问入栈,直到左孩子为空。此时栈内元素依次为A,B,D。
- 读栈顶元素:若其右孩子不空,且未被访问过,将右子树转执行1。
- 否则,栈顶元素出栈并访问
void PostOrder(BiTree T){
InitStack(S);
p=T;
r=NULL;
while(p||IsEmpty(S)){
if(p){ //走到最左边
push(S,p);
p=p->lchild;
}
else{ //向右
GetTop(S,p); //读栈顶结点(非出栈)
if(p->rchild&&p->rchild!=r){ //若右子树存在,且未被访问过
p=p->rchild; //转向右
push(S,p); //压入栈
p=p->lchild; //再走到最左
}
else{ //否则,弹出结点并访问
pop(S,p); //将结点弹出
visit(p->data); //访问该结点
r=p; //记录最近访问过的结点
p=NULL; //结点访问完后,重置p指针
}
}//else
}//while
}
4.层次遍历
算法思想:
要进行层次遍历,需要借助一个队列。先将二叉树的根节点入队,然后出队,访问出队结点,若它有左子树,则将左子树根节点入队;若它有右子树,则将右子树根节点入队。然后出队,访问出队结点......如此反复,直到对列为空。
递归算法:
void levelOrder(BiTree T){
initQueue(Q); //初始化辅助队列
BiTree p;
EnQueue(Q,T); //将根结点入队
while(!IsEmpty(Q)){ //队列不空则循环
DeQueue(Q,p); //对头结点出队
visit(p); //访问出队结点
if(p->lchild!=NULL)
EnQueue(Q,p->lchild); //左子树不空,则左子树根结点入队
if(p->rchild!=NULL)
EnQueue(Q,p->rchild); //右子树不空,则右子树根结点入队
}
}
非递归算法:
#define MAX_NODE 50
void LevelclerTraverse(BTNode *T)
{
BTNode *Queue[MAX_NODE],*p=T;
int front=0,rear=0;
if(p!=NULL)
{
Queue[++rear]=p; /*根结点入队*/
while(front<rear)
{
p=Queue[++front]; //出队
visit(p->data);
if(p->lchild!=NULL)
Queue[++rear]=p->lchild; /*左子树入队*/
if(p->rchild!=NULL)
Queue[++rear]=p->rchild; /*右子树入队*/
}
}
}
二、树与二叉树的应用
2.1 二叉排序树(BST)
特点:
- 左子树结点值 < 根结点值 < 右子树点值
- 队二叉排序树进行中序遍历,可以得到一个递增的有序序列
2.1.1 二叉排序树的查找
二叉排序树非递归代码:
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;
}
递归实现代码:
//在二叉排序树中查找值为key的结点(递归实现)
BSTNode *BSTSearch(BSTreeT,int key){
if(T==NULL)
return NULL; //查找失败
if(key==T->data)
return T; //查找成功
else if(key<T->data)
return BSTSearch(T->lchild,key); //在左子树中找
else
return BSTSearch(T->rchild,key); //在右子树中找
}
2.1.2 二叉排序树的插入
算法思想:若原二叉排序树为空,则直接插入结点;否则若关键字 k 小于根结点值,则插入到左子树,若关键字 k 大于根节点值,则插入到右子树。插入的结点一定是一个信添加的子叶子结点,且查找失败时的查找路径上访问的最后一个结点的左孩子和有孩子。
int BST_Insert(BiTree &T,KeyType k){
if(T==NULL){ //原树为空,新插入的记录为根结点
T=(BiTree)malloc(sizeof(BSTNode));
T->data=k;
T->lchild=T->rchild=NULL;
return 1;
}
else if(k==T->data) //树中存在相同的关键字的结点,插入失败
return 0;
else if(k<T->data)
return BST_Insert(T->lchild,k); //插入到T的左子树中
else
return BST_Insert(T->rchild,k); //插入到T的右子树中
}
2.1.3 二叉树的构造
void Creat_BST(BiTree &T,KeyType str[],int n)
{
T=NULL; //初始时T为空树
int i=0;
while(i<n) //依次将每个关键字插入到二叉树中
{
BST_Insert(T,str[i]);
i++;
}
}
2.1.4 二叉树的删除
- 若被删除结点z是叶子结点,则直接删除,不会破坏二叉排序树的性质
- 若结点z只是一棵左子树或者右子树,则让z的子树成为z父结点的子树,代替z的位置
- 若结点z有左、右两棵子树,则令z的直接后继(或者直接前驱)替代z,然后从二叉排序树中删去这个直接后继(或直接前驱),这样就转换成了第一或第二种情况
三、树与森林
3.1 树的存储结构
孩子兄弟表示法:
typedef struct CSNode{
ElemType data; //数据域
struct CSNode *firstchild,*nextsibling; //第一个孩子和右兄弟指针
}CSNode,*CSTree;
这种存储表示法比较灵活,其最大的优点就是可以方便地实现树转换为二叉树的操作,易于查找结点的孩子等,但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点,则查找结点的父结点也很方便。
//二叉链表示法
typedef struct BITNode
{
int data;
struct BITNode* lchild, *rchild;
};
typedef struct BITNode BITNode;
typedef struct BITNode *BITree;
void main()
{
BITNode t1, t2, t3, t4, t5;
t1.data = 1;//结点
t2.data = 2;
t3.data = 3;
t4.data = 4;
t5.data = 5;
//建立关系
t1.lchild = &t2;
t1.rchild = &t3;
t2.lchild = &t4;
t3.lchild = &t5;
system("pause");
return;
}
//指针方法
void main()
{
BITNode *p1, *p2, *p3, *p4, *p5;
p1 = (BITNode*)malloc(sizeof(BITNode));
p2 = (BITNode*)malloc(sizeof(BITNode));
p3 = (BITNode*)malloc(sizeof(BITNode));
p4 = (BITNode*)malloc(sizeof(BITNode));
p5 = (BITNode*)malloc(sizeof(BITNode));
p1->data = 1;
p2->data = 2;
p3->data = 3;
p4->data = 4;
p5->data = 5;
//
p1->lchild = p2;
p1->rchild = p3;
p2->lchild = p4;
p3->lchild = p5;
}
//双亲链表
#define MAX_TREE_SIZE 100
typedef struct BPTNode
{
int data;
int parentPosition;//指向双亲的指针
char LRTag;//左右孩子标志域
}BPTNode;//结点
typedef struct BPTree
{
BPTNode nodes[100];//因为节点之间是分散的,需要把节点存储在数组中
//树也是一个集合,如果单独存结点的话,结点之间没有任何关系.如果要是想让结点之间保留
//关系,可以用顺序数组,或链表存储.
int num_node;//结点数目
int root;//根节点的位置 //注意此域存储的是父亲结点在数组的下标
}BPTree; //树包含了结点
void main()
{
BPTree tree;
//根节点
tree.nodes[0].parentPosition = 100;
//B
tree.nodes[1].parentPosition = 0;
tree.nodes[1].data = 'B';
tree.nodes[1].LRTag = 1;
//c
tree.nodes[1].parentPosition = 0;
tree.nodes[1].data = 'C';
tree.nodes[1].LRTag = 2;
}
void preOrder(BITNode *root)
{
if (root == NULL)
{
return;
}
printf("%d ", root->data);
preOrder(root->lchild);
preOrder(root->rchild);
}
void inOrder(BITNode *root)
{
if (root == NULL)
{
return;
}
preOrder(root->lchild);
printf("%d\n ", root->data);
preOrder(root->rchild);
}
void postOrder(BITNode *root)
{
if (root == NULL)
{
return;
}
preOrder(root->lchild);
preOrder(root->rchild);
printf("%d\n ", root->data);
}
int sum;
void coutLeaf(BITNode *T,int *sum)
{
if (T != NULL)
{
if (T->lchild == NULL || T->rchild == NULL)
{
(*sum)++;//指针所指向内存空间的数据++
}
if (T->lchild)
{
coutLeaf(T->lchild,sum);
}
if (T->rchild)
{
coutLeaf(T->rchild,sum);
}
}
}
int Depth(BITNode *T)
{
int deptleft = 0;
int deptright = 0;
int deptval = 0;
if (T == NULL)
{
deptval = 0;
return deptval;
}
deptleft = Depth(T->lchild);
deptright = Depth(T->rchild);
deptval = 1 + (deptleft > deptright ? deptleft : deptright);
return deptval;
}
//拷贝树
BITNode *CopyTree(BITNode *T)
{
BITNode *newNode = NULL;
BITNode *newLp = NULL;
BITNode *newRp = NULL;
if (T == NULL)
{
return NULL;
}
if (T->lchild != NULL)
{
newLp = CopyTree(T->lchild);
}
else
{
newLp = NULL;
}
if (T->rchild != NULL)
{
newRp = CopyTree(T->rchild);
}
else
{
newRp = NULL;
}
newNode = (BITNode*)malloc(sizeof(BITNode));
if (newNode == NULL)
{
return NULL;
}
newNode->lchild = newLp;
newNode->rchild = newRp;
newNode->data = T->data;
return newNode;
}
BITNode * CreateBiThrTree(BITNode *T)
{
BITNode *node = NULL;
BITNode *pL = NULL;
BITNode *pR = NULL;
char h;
scanf("%c", &h);
if (h == '#')
{
return NULL;
}
else
{
node = (BITNode*)malloc(sizeof(BITNode));
memset(node, 0, sizeof(BITNode));
node->data = h;
CreateBiThrTree(T->lchild);
if (pL != NULL)
{
node->lchild = pL;
}
else
{
node->lchild = NULL;
}
CreateBiThrTree(T->lchild);
if (pR != NULL)
{
node->rchild = pR;
}
else
{
node->rchild = NULL;
}
}
return node;
}