杰人编程网

杰人编程网

树的基础实现代码

jieren365 0 6 次浏览 文章教程

树

一、二叉树

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);               //递归遍历右子树
    }
}

非递归算法：

算法思想：

  1. 根结点入栈
  2. 循环：走到最左，沿路入栈。栈不空的时候，出栈并访问栈顶P；处理P的右孩子
  3. 栈空结束
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);                           //访问根结点
    }
}

非递归算法：

算法思想：后序非递归遍历二叉树是先访问左子树，再访问右子树，最后访问根节点。

  1. 沿着根的左孩子，依次访问入栈，直到左孩子为空。此时栈内元素依次为A，B,D。
  2. 读栈顶元素：若其右孩子不空，且未被访问过，将右子树转执行1。
  3. 否则，栈顶元素出栈并访问
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）

特点：

  1. 左子树结点值 < 根结点值 < 右子树点值
  2. 队二叉排序树进行中序遍历，可以得到一个递增的有序序列

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 二叉树的删除

  1. 若被删除结点z是叶子结点，则直接删除，不会破坏二叉排序树的性质
  2. 若结点z只是一棵左子树或者右子树，则让z的子树成为z父结点的子树，代替z的位置
  3. 若结点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;
}
原文链接：，转发请注明来源！
杰人编程网 › 文章教程 › 树的基础实现代码