数据结构篇：二叉树（一：二叉树的基础创建，遍历及其他）

先给出结构

struct BiTree {
	char data;
	BiTree *lchild,*rchild;
};

二叉树的创建

只能用先序法创建，单独的中序或后序都无法进行创建，原因和解决办法我会在下一篇博客进行完成

BiTree * Tree :: PreCreateBiTree() {
	BiTree *T;
	char c;
	cin>>c;
	if(c=='#') {
		T=NULL;
	} else {
		T=new BiTree;
		if(!T) {
			cout<<"请求内存失败。"<<endl;
		} else {
			T->data=c;
		}
		T->lchild=PreCreateBiTree();
		T->rchild=PreCreateBiTree();
	}
	return T;
}

二叉树深度 （高度）      左图       3                       右图      4

int Tree::HeightOfthis(BiTree *T) {
	if(!T) return 0;
	else {
		return HeightOfthis(T->lchild)>HeightOfthis(T->rchild)?HeightOfthis(T->lchild)+1:HeightOfthis(T->rchild)+1;
	}
}

二叉树叶子数（即没有分支结点的结点） 左图              2                 右图              3

int Tree :: LeafOfthis(BiTree *T) {
	if(!T) {
		return 0;
	} else if(  (T->lchild == NULL) && (T->rchild == NULL) ) {
		return 1;
	} else {
		return  (BranchOfthis(T->lchild) + BranchOfthis(T->rchild));
	}

}

二叉树分枝数    左图      3        右图         5（只需要把节点数减一即可）

	cout<<"分支数为："<<tree.NodeOfthis(biTree)-1<<endl;

 

完整程序

#include <iostream>
#include <string.h>
using namespace std;

struct BiTree {
	char data;
	BiTree *lchild,*rchild;
};
class Tree {
		BiTree *pt;
	public :
		Tree() {
			pt=NULL;
		}
		BiTree * PreCreateBiTree();
		void PreOrderTraverse(BiTree *T);
		void InOrderTraverse(BiTree *T);
		void LastOrderTraverse(BiTree *T);
		int HeightOfthis(BiTree *T);
		int NodeOfthis(BiTree *T);
		int LeafOfthis(BiTree *T);

};

BiTree * Tree :: PreCreateBiTree() {
	BiTree *T;
	char c;
	cin>>c;
	if(c=='#') {
		T=NULL;
	} else {
		T=new BiTree;
		if(!T) {
			cout<<"请求内存失败。"<<endl;
		} else {
			T->data=c;
		}
		T->lchild=PreCreateBiTree();
		T->rchild=PreCreateBiTree();
	}
	return T;
}

void Tree::PreOrderTraverse(BiTree *T) {
	if(!T) {
		return ;
	} else {
		cout<<T->data<<" ";
		PreOrderTraverse(T->lchild);
		PreOrderTraverse(T->rchild);
	}
}
void Tree::InOrderTraverse(BiTree *T) {
	if(!T) {
		return ;
	} else {
		InOrderTraverse(T->lchild);
		cout<<T->data<<" ";
		InOrderTraverse(T->rchild);
	}
}
void Tree::LastOrderTraverse(BiTree *T) {
	if(!T) {
		return ;
	} else {
		LastOrderTraverse(T->lchild);
		LastOrderTraverse(T->rchild);
		cout<<T->data<<" ";
	}
}

int Tree::HeightOfthis(BiTree *T) {
	if(!T) return 0;
	else {
		return HeightOfthis(T->lchild)>HeightOfthis(T->rchild)?HeightOfthis(T->lchild)+1:HeightOfthis(T->rchild)+1;
	}
}

int Tree :: NodeOfthis(BiTree *T) {
	if(!T) return 0;
	else {
		return 1+NodeOfthis(T->lchild)+NodeOfthis(T->rchild);
	}
}

int Tree :: LeafOfthis(BiTree *T) {
	if(!T) {
		return 0;
	} else if(  (T->lchild == NULL) && (T->rchild == NULL) ) {
		return 1;
	} else {
		return  (LeafOfthis(T->lchild) + LeafOfthis(T->rchild));
	}

}


int main() {
	Tree tree;
	BiTree *biTree;
	cout<<"请以先序顺序输入数元素，以'#'代表虚空元素"<<endl;
	biTree = tree.PreCreateBiTree();
	cout<<"先序遍历结果为: "<<endl;
	tree.PreOrderTraverse(biTree);
	cout<<endl;
	cout<<"中序遍历结果为: "<<endl;
	tree.InOrderTraverse(biTree);
	cout<<endl;
	cout<<"后序遍历结果为: "<<endl;
	tree.LastOrderTraverse(biTree);
	cout<<endl;
	cout<<"高度为："<<tree.HeightOfthis(biTree)<<endl;
	cout<<"节点数为："<<tree.NodeOfthis(biTree)<<endl;
	cout<<"叶子数为："<<tree.LeafOfthis(biTree)<<endl;
	cout<<"分支数为："<<tree.NodeOfthis(biTree)-1<<endl;
	return 0;
}