创建一颗二叉树

1、创建一颗二叉树header.h：#ifndef BCNF_Header_h#define BCNF_Header_htypedefint Item;typedefstruct nodestructnode * lchild;structnode * rchild;Item data;BiTNode,*BiTree;/*构造一棵新的二叉树*/BiTree InitBiTree(BiTNode *root);/*生成节点*/BiTNode *MakeNode(Item item,BiTNode *lchild,BiTNode *rchild);/*释放节点*/void FreeNode(BiTNo

2、de *pnode);/*清空一棵二叉树*/void ClearBiTree(BiTree tree);/*销毁一棵二叉树*/void DestroyBiTree(BiTree tree);/*判定是否为空*/int IsEmpty(BiTree tree);/*返回树的深度*/int GetDepth(BiTree tree);/*返回根*/BiTree GetRoot(BiTree tree);/*返回节点值*/Item GetItem(BiTNode *pnode);/*设置节点值*/void SetItem(BiTNode *pnode,Item item);/*设置左子树*/BiTr

3、ee SetLChild(BiTree parent,BiTree lchild);/*设置右子树*/BiTree SetRChild(BiTree parent,BiTree rchild);/*返回左子树*/ BiTree GetLChild(BiTree tree);/*返回右子树*/BiTree GetRChild(BiTree tree);/*插入新子树*/BiTree InsertChild(BiTree parent,int lr,BiTree child);/*删除子树*/void DeleteChild(BiTree parent,int lr);/*先序遍历二叉树*/voi

4、d PreOrderTraverse(BiTree tree,void(*visit)();/*中序遍历二叉树*/void InOrderTraverse(BiTree tree,void(*visit)();/*后序遍历二叉树*/void PostOrderTraverse(BiTree tree,void(*visit)();#endifmain.c：#include #include#includeHeader.hBiTree InitBiTree(BiTNode *root)BiTree tree = root;return tree;/*生成节点*/BiTNode *MakeNode

5、(Item item,BiTNode *lchild,BiTNode *rchild) BiTNode * pnode = (BiTNode *)malloc(sizeof(BiTNode); if(pnode)pnode-data = item;pnode-lchild = lchild; pnode-rchild = rchild;return pnode;/*释放节点*/void FreeNode(BiTNode *pnode) if(pnode!=NULL) free(pnode);/*清空一棵二叉树*/void ClearBiTree(BiTree tree)BiTNode * pn

6、ode = tree; if(pnode-lchild!=NULL)ClearBiTree(pnode-lchild);if(pnode-rchild!=NULL)ClearBiTree(pnode-rchild);FreeNode(pnode);/*销毁一棵二叉树*/void DestroyBiTree(BiTree tree) if(tree)ClearBiTree(tree);/*判定是否为空*/Item IsEmpty(BiTree tree) if(tree=NULL) return0;elsereturn1;/*返回树的深度*/int GetDepth(BiTree tree)in

7、t cd,ld,rd;cd = ld = rd =0;if(tree)ld = GetDepth(tree-lchild); rd = GetDepth(tree-rchild); cd = (ld rd ? ld : rd); return cd+1;else return0;/*返回根*/BiTree GetRoot(BiTree tree)return tree;/*返回节点值*/Item GetItem(BiTNode *pnode)return pnode-data;/*设置节点值*/void SetItem(BiTNode *pnode,Item item) pnode-data

8、= item;/*设置左子树*/BiTree SetLChild(BiTree parent,BiTree lchild) parent-lchild = lchild; return lchild;/*设置右子树*/BiTree SetRChild(BiTree parent,BiTree rchild) parent-rchild = rchild; return rchild;/*返回左子树*/BiTree GetLChild(BiTree tree)if(tree)return tree-lchild; returnNULL;/*返回右子树*/BiTree GetRChild(BiTr

9、ee tree)if(tree)return tree-rchild; returnNULL;/*插入新子树*/BiTree InsertChild(BiTree parent,int lr,BiTree child) if(parent)if( lr = 0& parent-lchild = NULL)parent-lchild = child;return child;if( lr = 1& parent-rchild = NULL)parent-rchild = child;return child; returnNULL;/*删除子树*/void DeleteChild(BiTree

10、parent,int lr)if(parent)if( lr = 0& parent-lchild != NULL)parent-lchild = NULL; FreeNode(parent-lchild);if( lr = 1& parent-rchild != NULL)parent-rchild = NULL; FreeNode(parent-rchild);/*先序遍历二叉树*/void PreOrderTraverse(BiTree tree,void(*visit)() BiTNode * pnode = tree;if(pnode) visit(pnode-data);PreOr

11、derTraverse(pnode-lchild,visit); PreOrderTraverse(pnode-rchild,visit);/*中序遍历二叉树*/void InOrderTraverse(BiTree tree,void(*visit)() BiTNode * pnode = tree;if(pnode)InOrderTraverse(pnode-lchild,visit); visit(pnode-data);InOrderTraverse(pnode-rchild,visit);/*后序遍历二叉树*/void PostOrderTraverse(BiTree tree,vo

12、id(*visit)() BiTNode * pnode = tree;if(pnode) PostOrderTraverse(pnode-lchild,visit); PostOrderTraverse(pnode-rchild,visit);visit(pnode-data);void print(Item item) printf(%d ,item);int main(int argc, constchar * argv) BiTNode * n1 = MakeNode(10,NULL,NULL);BiTNode * n2 = MakeNode(20,NULL,NULL);BiTNode

13、 * n3 = MakeNode(30,n1,n2);BiTNode * n4 = MakeNode(40,NULL,NULL);BiTNode * n5 = MakeNode(50,NULL,NULL);BiTNode * n6 = MakeNode(60,n4,n5);BiTNode * n7 = MakeNode(70,NULL,NULL);BiTree tree = InitBiTree(n7);SetLChild(tree,n3);SetRChild(tree,n6);printf(”树的深度为：%d,GetDepth(tree);printf(n先序遍历如下：”);PreOrderTraverse(tree,print);printf(n中序遍历如下：);In