大家好，又见面了，我是全栈君。
二叉树节点
代码语言：javascript复制#pragma once
#include <stdlib.h>
template<class T>class BinaryTreeNode
{
public:
T data;
BinaryTreeNode<T>* leftchild;
BinaryTreeNode<T>* rightchild;
BinaryTreeNode():leftchild(NULL),rightchild(NULL){}
BinaryTreeNode(T d):data(d),leftchild(NULL),rightchild(NULL){}
};二叉树的全部操作：建树。销毁树，先序后序中序便利的递归和非递归方式层序遍历
代码语言：javascript复制#include "BinaryTreeNode.h"
#include <queue>
#include <stack>
#include <iostream>
using namespace std;
/*
void CreatePreOrder(BinaryTreeNode<T>** root)
void LevelOrderTraverse()//层序遍历
void PreOrderTraverse(BinaryTreeNode<T>* root)//先序遍历递归
void PreOrderTraverse()//先序遍历非递归算法
void InOrderTraverse()//中序遍历的非递归方法
void PostOrderTraverse()//后序遍历非递归方法
int depth()//树深度
BinaryTreeNode<T>* Parent(BinaryTreeNode<T>*root,BinaryTreeNode<T>*node)//返回节点的双亲
BinaryTreeNode<T>* SiblingNode(BinaryTreeNode<T>*node)//返回兄弟节点
*/
template<class T>class BinaryTree
{
public:
BinaryTreeNode<T>* root;
BinaryTree():root(NULL){}//空树
/********************************先序创建链表****************************************/
void CreatePreOrder(BinaryTreeNode<T>** root)//或者BinaryTreeNode<T>* &root以下依次改变
{
char d;
cin>>d;
if (d=='#')
(*root) = NULL;
else
{
*root = new BinaryTreeNode<T>(d);
CreatePreOrder(&(*root)->leftchild);
CreatePreOrder(&(*root)->rightchild);
}
}
/********************************层序遍历****************************************/
void LevelOrderTraverse()
{
if (root==NULL)
return;
BinaryTreeNode<T>* p;
queue<BinaryTreeNode<T>*> myQueue;
myQueue.push(root);
myQueue.push(NULL);
while (!myQueue.empty())
{
p=myQueue.front();
myQueue.pop();
if (p==NULL)
{
if (myQueue.empty())
break;
cout<<endl;
myQueue.push(NULL);
}
else
{
cout<<p->data;
if (p->leftchild)
myQueue.push(p->leftchild);
if (p->rightchild)
myQueue.push(p->rightchild);
}
}
}
/********************************先序遍历递归****************************************/
void PreOrderTraverse(BinaryTreeNode<T>* root)
{
if (root)
{
cout<<root->data;
PreOrderTraverse(root->leftchild);
PreOrderTraverse(root->rightchild);
}
}
/********************************中序遍历递归****************************************/
void InOrderTraverse(BinaryTreeNode<T>* root)
{
if (root)
{
InOrderTraverse(root->leftchild);
cout<<root->data;
InOrderTraverse(root->rightchild);
}
}
/********************************后序遍历递归****************************************/
void PostOrderTraverse(BinaryTreeNode<T>* root)
{
if (root)
{
PostOrderTraverse(root->leftchild);
PostOrderTraverse(root->rightchild);
cout<<root->data;
}
}
/********************************先序遍历非递归****************************************/
void PreOrderTraverse()
{
if (root)
{
BinaryTreeNode<T>* p;
stack<BinaryTreeNode<T>*> myStack;
myStack.push(root);
while (!myStack.empty())
{
p=myStack.top();
myStack.pop();
cout<<p->data;
if (p->rightchild)
myStack.push(p->rightchild);
if (p->leftchild)
myStack.push(p->leftchild);
}
}
}
/********************************中序遍历非递归****************************************/
void InOrderTraverse()
{
if (root==NULL)
return;
BinaryTreeNode<T>* p;
stack<BinaryTreeNode<T>*> myStack;
myStack.push(root);
while (!myStack.empty())
{
while (myStack.top())
myStack.push(myStack.top()->leftchild);
myStack.pop();
if (!myStack.empty())
{
p=myStack.top();
myStack.pop();
cout<<p->data;
myStack.push(p->rightchild);
}
}
}
/********************************后序遍历非递归****************************************/
void PostOrderTraverse()
{
if (root==NULL)
return;
stack<BinaryTreeNode<T>*> myStack1;
stack<BinaryTreeNode<T>*> myStack2;
BinaryTreeNode<T> * p;
myStack1.push(root);
while (!myStack1.empty())
{
p=myStack1.top();
myStack1.pop();
myStack2.push(p);
if (p->leftchild)
myStack1.push(p->leftchild);
if(p->rightchild)
myStack1.push(p->rightchild);
}
while (!myStack2.empty())
{
p=myStack2.top();
myStack2.pop();
cout<<p->data;
}
}
/********************************树的深度****************************************/
int depth(BinaryTreeNode<T>* root)
{
int dep;
if (root==NULL)
dep=0;
else
{
dep=1 (depth(root->leftchild)>depth(root->rightchild)?depth(root->leftchild):depth(root->rightchild));
}
return dep;
}
/********************************返回双亲节点****************************************/
BinaryTreeNode<T>* Parent(BinaryTreeNode<T>*root,BinaryTreeNode<T>*node)
{
if (root==NULL || root==node)
return NULL;
if (root->leftchild==node||root->rightchild==node)
{
return root;
}
else if(Parent(root->leftchild,node))
{
return Parent(root->leftchild,node);
}
else
return Parent(root->rightchild,node);
}
/********************************返回双亲节点(重载)****************************************/
BinaryTreeNode<T>* ParentPre(BinaryTreeNode<T>*root,BinaryTreeNode<T>*node)//通过遍历树来搜索
{
if (root==node||root==NULL)
return NULL;
if(root)
{
if (root->leftchild==node||root->rightchild==node)
return root;
if (ParentPre(root->leftchild,node))
return ParentPre(root->leftchild,node);
else
return ParentPre(root->rightchild,node);
}
}
/********************************返回兄弟节点****************************************/
BinaryTreeNode<T>* SiblingNode(BinaryTreeNode<T>*node)
{
BinaryTreeNode<T>*p=Parent(root,node);
if (p)
{
if (p->leftchild==node)
return p->rightchild;
else
return p->leftchild;
}
return NULL;
}
/********************************销毁树****************************************/
void DestroyTree(BinaryTreeNode<T>*root)
{
if (root!=NULL)
{
DestroyTree(root->leftchild);
DestroyTree(root->rightchild);
delete root;
}
root=NULL;
}
};
发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/115881.html原文链接：https://javaforall.cn
