首页 > 代码库 > 二叉树与其它树
二叉树与其它树
树
树:树是一个非空的有限元素的集合,其中一个元素为根(root),余下的元素(如果有的话)组成t的子树。
层次关系:层次中最高层的元素为根。其下级的元素是余下元素所构成子树的根。
兄弟:有相同父母的孩子为兄弟(sibling)
叶子:树中没有孩子的元素称为叶子。
树根是树中唯一一个没有父节点的元素。
二叉树
概念:t是一个有限个元素的集合(可以为空)。当二叉树非空时其中有一个称为根的元素,余下的元素(如果有的话)被组成二个二叉树,分别为t的左子树和右子树。
二叉树与树的根本区别:
- 二叉树可以为空,但树不能为空
- 二叉树的每个元素都恰好有两棵子树(其中一个或两个可能为空)。而树中每个元素可 有若干子树
- 在二叉树中每个元素都是有序的,也就是说可以用左、右树来区别。而树的子树间是无序的。
二叉树地特性:
- 包含n个元素的二叉树的边数为n-1
- 若二叉树的高度为h,h>=0,则二叉树最少有h个元素,最多有2^h-1个元素。
- 包含n个元素的二叉树高度最大为n最小为log2(n+1)。 //这一点暂时不太懂。
- 设完全二叉树中一元素序号为i 1<=i<=n则有以下成立关系。(1)当i=1时,该元素为二叉树的根若i>1则该元素父节点的编号为i/2 (2)当2i>n时该元素无左孩子,否则其左孩子的编号为2i(3)若2i+1>n时,该元素无右孩子,否则其右孩子编号为2i+1。
二叉树的描述:
链表描述:
// BinaryTree.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include <iostream>#include <string>using namespace std;template<class T>class BinaryTreeNode{public: BinaryTreeNode(){LeftChild = RightChild = 0;} BinaryTreeNode(const T & e) {LeftChild = RightChild = 0;data =http://www.mamicode.com/ e;} BinaryTreeNode(const T & e,BinaryTreeNode * l ,BinaryTreeNode * r) { data = e; LeftChild = l; RightChild = r; } T data; BinaryTreeNode<T> * LeftChild; BinaryTreeNode<T> * RightChild;};template<class T>void Visit(BinaryTreeNode<T> * t){ cout<<t->data;}//前序遍历template<class T>void PreOrder(BinaryTreeNode<T> * t){ if(t) { Visit(t); PreOrder(t->LeftChild); PreOrder(t->RightChild); }}//中序遍历template<class T>void InOrder(BinaryTreeNode<T> * t){ if(t) { InOrder(t->LeftChild); Visit(t); InOrder(t->RightChild); }}//后序遍历template<class T>void PostOrder(BinaryTreeNode<T> * t){ if(t) { PostOrder(t->LeftChild); PostOrder(t->RightChild); Visit(t); }}//输出完全括号化的中缀表达式template<class T>void Infix(BinaryTreeNode<T> * t){ //输出表达示的中缀表达式 if(t) { cout<<"("; Infix(t->LeftChild); //左操作数 cout<<t->data; //符号 Infix(t->RightChild);//右操作数 cout<<")"; }}void Test(){ BinaryTreeNode<string> a1("a",0,0); BinaryTreeNode<string> a2("b",0,0); BinaryTreeNode<string> a3("*",&a1,&a2); BinaryTreeNode<string> a4("c",0,0); BinaryTreeNode<string> a5("d",0,0); BinaryTreeNode<string> a6("/",&a4,&a5); BinaryTreeNode<string> a7("+",&a3,&a6); PreOrder<string>(&a7); cout<<endl; InOrder<string>(&a7); cout<<endl; PostOrder<string>(&a7); cout<<endl; Infix<string>(&a7); cout<<endl;}int _tmain(int argc, _TCHAR* argv[]){ Test(); system("pause"); return 0;}
抽象数据类型BinaryTree
待序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。