二叉树的结构定义为:
struct BinTree { int data; BinTree* lchild; BinTree* rchild; };
树深度的递归算法:
//求树深度的递归算法,根深度为1 int Depth(BinTree T) { int m,n; if(!T) return 0; else { m=Depth(T->lchild); n=Depth(T->rchild); return (m>n?m:n)+1; } }
二叉树中以值为x的结点为根的子树深度:
//求二叉树中以值为x的结点为根的子树深度 int Get_Sub_Depth(BinTree T, int x) { int m,n; if(T) { if(T->data==x) return Depth(T);//找到了值为x的结点,求x为根的子树的其深度 else{ //在左右子树中继续寻找 if(T->lchild) m=Get_Sub_Depth(T->lchild,x); if(T->rchild) n=Get_Sub_Depth(T->rchild,x); } return m>n?m:n; } return 0; }
交换所有结点的左右子树:
//交换所有结点的左右子树 void Bitree_Revolute(BinTree* T) { if(T) { //交换左右子树 BinTree* temp; temp = (BinTree*)malloc(sizeof(BinTree)); temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; if(T->lchild) Bitree_Revolute(T->lchild); if(T->rchild) Bitree_Revolute(T->rchild); } }
根据顺序存储结构建立二叉链表:
//根据顺序存储结构建立二叉链表 int CreateBitree_SqList(BinTree &T,SqList sa) { BinTree ptr[sa.last+1]; //该数组储存与sa中各结点对应的树指针 if(!sa.last) { T=NULL; //空树 Return 1; } ptr[1]=(BTNode*)malloc(sizeof(BTNode)); ptr[1]->data=sa.elem[1]; //建立树根 T=ptr[1]; T->lchild=T->rchild=NULL; for(i=2;i<=sa.last;i++) { if(!sa.elem[i]) return 0; //顺序错误 ptr[i]=(BTNode*)malloc(sizeof(BTNode)); ptr[i]->data=sa.elem[i]; ptr[i]->lchild=ptr[i]->rchild=NULL; j=i/2; //找到结点i的双亲j if(i==j*2) ptr[j]->lchild=ptr[i]; //i是j的左孩子 else if(i==2*j+1)ptr[j]->rchild=ptr[i]; //i是j的右孩子 } return 1; }