【无标题】二叉链表的基本操作

#include<stdio.h> #include<stdlib.h> #include<string.h> #include <iostream> using namespace std; //#define STACK_INIT_SIZE 100 typedef int Status; typedef char TElemType; #define OK 1 #define OVERFLOW -2 #define ERROR 0 typedef struct BiTNode//定义一个二叉链表 ,结点BiTNode,二叉链表*BiTree (一个指针）表示一颗二叉树，也可表示某一结点指针 { TElemType data;//结点数据域 struct BiTNode *lchild,*rchild;//左右孩子指针 }BiTNode,*BiTree; typedef struct StackNode//定义一个栈，用于完成二叉树遍历的非递归算法 { BiTNode *data;//数据域存放的是二叉树结点，也就是将一个树节点类型的指针作为数据放入栈结点的data中 struct StackNode *next;//指向下一个栈结点(data,next) }StackNode,*LinkStack; //初始化创建，按先序遍历创建 Status CreateBiTree(BiTree &T) { char ch; cin>>ch; if(ch==#)T=NULL;//递归结束，建空树 else //递归创建二叉树 { T=new BiTNode;//生成根结点 T->data =ch;//根结点的数据域置为ch CreateBiTree(T->lchild );//递归创建左子树 CreateBiTree(T->rchild );//递归创建右子树 } } Status PreOrderTraverse(BiTree T)

{ if(T)//二叉树为空 { cout<<T->data;//访问根结点 PreOrderTraverse(T->lchild);//前序遍历左子树 PreOrderTraverse(T->rchild);//前序遍历右子树 } } Status InOrderTraverse(BiTree T)//中序遍历 { if(T)//二叉树为空 { //cout<<T->data; InOrderTraverse(T->lchild);//中序遍历左子树 cout<<T->data;//访问根结点 InOrderTraverse(T->rchild);//中序遍历右子树 } }

Status PostOrderTraverse(BiTree T) { if(T)//二叉树为空 { // cout<<T->data; PostOrderTraverse(T->lchild);//后序遍历左子树 PostOrderTraverse(T->rchild);//后序遍历右子树 cout<<T->data;//访问根结点 } } void Copy(BiTree T,BiTree &NewT)//复制一颗和T完全相同的树 { if(T==NULL)//如果是空树，递归结束 { NewT=NULL;//复制空树 return; } else{ NewT=new BiTNode; NewT->data =T->data ;//复制根结点 Copy(T->lchild ,NewT->lchild );//递归复制左子树 Copy(T->rchild ,NewT->rchild );//递归复制右子树 //else } } Status Depth(BiTree T) { int m,n; //计算二叉树深度 if(T==NULL) return 0;//如果是空树，深度为0，递归结束 else { m=Depth(T->lchild );//递归计算左子树深度 n=Depth(T->rchild ) ;//递归计算右子树深度 if(m>n) return(m+1);//二叉树的深度为较大者加1 else return (n+1); } } Status NodeCount(BiTree T) { //统计结点个数 if(T==NULL) return 0;//如果空树，结点个数为0，递归结束 else return NodeCount(T->lchild )+ NodeCount(T->rchild )+1;//结点个数为左右子树结点个数加根结点个数 } Status LeafCount(BiTree T) { //统计叶结点个数 if(T==NULL) return 0;//如果空树，叶结点个数为0，递归结束 else if(T->lchild ==NULL&&T->rchild ==NULL)//非空树但是无孩子 return 1; else return LeafCount(T->lchild )+ LeafCount(T->rchild );//叶结点个数为左右子叶结点个数 } int main() {//ABC##DE#G##F###输入内容 BiTree T ; BiTree NewT1; printf("创建一个树："); CreateBiTree(T); printf(" 先序遍历："); PreOrderTraverse(T); printf(" 中序遍历："); InOrderTraverse(T); printf(" 后序遍历："); PostOrderTraverse(T); Copy(T,NewT1); //cout<<" 复制的树为：" ; printf(" 复制二叉树先序遍历为："); PreOrderTraverse( NewT1); printf(" 二叉树的深度：%d",Depth(T)); printf(" 结点个数为为：%d", NodeCount(T)) ; printf(" 叶子结点个数为：%d",LeafCount(T)); return 0; }