java用三叉链表构建二叉树_三叉链表实现二叉树的基本操作

三叉链表存储表示

改进于二叉链表，增加指向父节点的指针，能更好地实现结点间的访问。

存储结构/* 二叉树的三叉链表存储表示 */

typedef struct BiTPNode

{

TElemType data;

struct BiTPNode *parent,*lchild,*rchild; /* 双亲、左右孩子指针 */

}BiTPNode,*BiPTree;

下面给出二叉树采用三叉链表，实现了二叉树的构造、遍历、深度、宽度、结点个数、叶子个数 以及 结点的交换、层次、祖先、双亲、左孩子、右孩子、左兄弟、右兄弟各种功能：#include

using namespace std;

const int MaxBTreeSize = 20;

template

class BTNode

{

public:

T data;

BTNode* lchild;

BTNode* rchild;

BTNode* parent;

BTNode():lchild(NULL),rchild(NULL),parent(NULL)

{ }

};

template

class BTree

{

public: //提供接口

BTree();

BTree(const BTree& bTree);

~BTree();

const BTree& operator=(const BTree& bTree);

void createBTree();//按先序建立二叉树

void InitBiTree(); //初始化二叉树

void destoryBTree();//销毁二叉树

bool isEmptyBTree();//检查二叉树是否为空

void inOrderTraverse(); //中序遍历

void preOrderTraverse();//先序遍历

void postOrderTraverse(); //后序遍历

void levelOrderTraverse();//层序遍历

int heightBTree();//二叉树高度

int widthBTree(); //二叉树宽度

int nodeCountBTree(); //二叉树结点个数

int LeavesCountBTree();//二叉树叶子个数

int nodeLevelBTree(T item);//结点item在的层次

bool allParentBTree(T item);//找item的所有祖先

void findCommonAncestor(const BTNode* p1,const BTNode* p2,BTNode*& ancestor);//二叉树中2个节点p1, p2的最小公共祖先节点

void longPathBTree();//输出从每个叶子结点到根结点的最长路径

bool isFullBTree(); //判断二叉树是否是完全二叉树

void exchangeChildBTree();//交换二叉树的孩子

bool findBTree(const T item,BTNode*& ret)const; //查找结点

bool getParent(const BTNode* p,BTNode*& ret) const; //返回父亲

bool getLeftChild(const BTNode* p,BTNode*& ret) const; //返回左孩子

bool getRightChild(const BTNode* p,BTNode*& ret) const; //返回右孩子

bool getLeftSibling(const BTNode* p,BTNode*& ret) const; //返回左兄弟

bool getRightSibling(const BTNode* p,BTNode*& ret) const;//返回右兄弟

protected://为了继承

BTNode* root;

private://为了实现公有函数

void create(BTNode*& p);

//以p为根结点建树

void createParent(BTNode* p);

//为以p为根节点的树设置其指向双亲的结点

void copyTree(BTNode*& copyTreeRoot,BTNode* otherTreeRoot);

//把以otherTreeRoot为根节点的部分拷贝到copyTreeRoot为根节点的部分

void destory(BTNode*& p);

//销毁以p为根节点的部分

void inOrder(BTNode* p);

//中序遍历以p为根节点的部分

void preOrder(BTNode* p);

//先序遍历以p为根节点的部分

void postOrder(BTNode* p);

//后序遍历以p为根节点的部分

void levelOrder(BTNode* p);

//层次遍历以p为根节点的部分

int height(BTNode* p);

//计算以p为根节点的高度

int width(BTNode* p);

int max(int x,int y);

int min(int x,int y);

//计算以p为根，俩孩子的最值

int nodeCount(BTNode* p);

//计算以p为根节点的结点个数

int leavesCount(BTNode* p);

//计算以p为根节点的叶子个数

void nodeLevel(T item,BTNode* p,int level,int& nlevel);

//计算以p为根节点的中item所在层次，如有多个元素，则返回一个最小值(离根最近)，如果没有出现，则返回0

bool find(BTNode*p,const T item,bool& isFind,BTNode*& cur)const;

//在p指向的二叉树中，返回 值为item的指针

bool allParent(T item,BTNode* p,BTNode* path[MaxBTreeSize],int& len,int& seat,bool& isFind);

//找item的所有祖先

void longPath(BTNode* p,int len,int& maxLen,BTNode*& longNode);

输出从每个叶子结点到根结点的最长路径

bool isFull(BTNode* p);

//判断以p为根的二叉树是不是完全二叉树

void exchangeChild(BTNode*& p);

//交换以p为根节点的二叉树

};

template

BTree::BTree()

{

root = NULL;

}

template

BTree::BTree(const BTree& bTree)

{

if (bTree.root==NULL)

{

root = NULL;

}

else

{

copyTree(this->root,bTree.root);

}

}

template

BTree::~BTree()

{

destory(root);

}

template

const BTree& BTree::operator=(const BTree& bTree)

{

if (this!=&bTree)//避免自己赋值

{

if (root!=NULL)//

{

destory(root);//自己有成员，先销毁

}

if (bTree.root==NULL)

{

root = NULL;

}

else

{

copyTree(this->root,bTree.root);

}

}

return *this;

}

template

void BTree::createBTree()

{

cout<

create(root);

}

/*借助先序遍历创建二叉树*/

template

void BTree::create(BTNode*& p)

{

T newData