C++数据结构(树的基本操作) c++ 数据结构

先序遍历 中序遍历 后序遍历(都是相对根来说的,先左子树,后右子树是一定的)

树的遍历

求叶子结点

树的高度

拷贝二叉树

#include<stdlib.h>
#include<stdio.h>
//二叉链表示
struct BiTNode
{
	int data;
	struct BiTNode *Lchild, *rchild;
};
typedef struct BiTNode  BiTNode;
typedef struct BiTNode*  BiTTree;
void preOrder(BiTNode *root)
{
	if (root == NULL)
	{
		return;
	}
	printf("%d", root->data);
	//
	preOrder(root->Lchild);
	//
	preOrder(root->rchild);

}
void inOrder(BiTNode *root)
{
//中序
}
void postOrder(BiTNode *root)
{
//后序
}
void coutLeaf2(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);

		}
	}
}
void coutLeaf(BiTNode*T)
{
	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)//求高度就是,求左边 求右边 比大小 取大的+1
{
	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)//拷贝树
{
	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;
	}
	//malloc根节点
	newNode =(BiTNode*) malloc(sizeof(BiTNode));
	if (newNode == NULL)
	{
		return NULL;
	}
	newNode->Lchild = newLp;
	newNode->rchild = newRp;
newNode->data = T->data;
	return newNode;
}
void main()
{
	BiTNode t1, t2, t3, t4, t5;
	memset(&t1, 0, sizeof(BiTNode));
	memset(&t2, 0, sizeof(BiTNode));
	memset(&t3, 0, sizeof(BiTNode));
	memset(&t4, 0, sizeof(BiTNode));
	memset(&t5, 0, sizeof(BiTNode));
	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;
	//树的遍历
  	printf("%d\n", Depth(&t1));//高度
	printf("preOrder\n");
	preOrder(&t1);
	printf("inOrder\n");
	preOrder(&t1);
	printf("postOrder\n");
	preOrder(&t1);
	return;
}