此算法中的树结构为 "左儿子有兄弟链接结构"
在这样的一个二叉树中, 一个节点的左分支是他的大儿子节点, 右分支为他的大兄弟节点.
这里讲的树有递归前根, 中根, 后根遍历, 插入节点, 插入兄弟节点, 查找结点, 释放内存这些功能.
重点说一下查找节点这一算法:
- pSTreeNode CTree::Search( pSTreeNode pNode, TreeDataType Value )
- {
- if ( pNode == NULL )
- return NULL;
- if ( pNode->data == Value )
- return pNode;
- if ( pNode->pFirstChild == NULL && pNode->pNextBrother == NULL )
- return NULL;
- else
- {
- if ( pNode->pFirstChild != NULL ) // 首先判断根节点的左儿子节点是否为空, 若不为空, 通过引入指针来寻找节点
- {
- pSTreeNode pNodeTemp = Search( pNode->pFirstChild, Value );
- if ( pNodeTemp != NULL )
- return pNodeTemp;
- else
- {
- return Search( pNode->pNextBrother, Value );
- }
- }
- else // 否则在根节点的右兄弟节点中寻找
- return Search( pNode->pNextBrother, Value );
- }
- }
完整代码如下:
- #include <iostream>
- using namespace std;
- typedef struct STreeNode* pSTreeNode;
- typedef int TreeDataType;
- // 定义结构体
- struct STreeNode
- {
- TreeDataType data;
- pSTreeNode pFirstChild;
- pSTreeNode pNextBrother;
- // 结构体构造函数
- STreeNode( TreeDataType Value )
- {
- data = Value;
- pFirstChild = NULL;
- pNextBrother = NULL;
- }
- };
- // 定义类
- class CTree
- {
- public:
- CTree();
- CTree( TreeDataType Value );
- ~CTree();
- public:
- void Insert( TreeDataType parentValue, TreeDataType Value ); // parentValue: 该点的父亲节点; Value: 该点的值
- void InsertBrother( pSTreeNode pParentNode, TreeDataType Value );
- pSTreeNode Search( pSTreeNode pNode, TreeDataType Value );
- void Preorder( pSTreeNode pNode ); // 前序遍历
- void Inorder( pSTreeNode pNode ); // 中序遍历
- void postorder( pSTreeNode pNode ); // 后序遍历
- void FreeMemory( pSTreeNode pNode ); // 释放内存
- public:
- pSTreeNode pRoot;
- };
- // 构造函数
- CTree::CTree()
- {
- pRoot = NULL;
- }
- // 构造函数
- CTree::CTree( TreeDataType Value )
- {
- pRoot = new STreeNode( Value );
- }
- // 析构函数
- CTree::~CTree()
- {
- if (pRoot == NULL )
- return;
- FreeMemory( pRoot );
- }
- // 释放内存
- void CTree::FreeMemory( pSTreeNode pNode )
- {
- if ( pNode == NULL )
- return;
- if ( pNode->pFirstChild != NULL )
- FreeMemory( pNode->pFirstChild );
- if ( pNode->pNextBrother != NULL )
- FreeMemory( pNode->pNextBrother );
- delete pNode;
- pNode = NULL;
- }
- // 插入节点
- void CTree::Insert( TreeDataType parentValue, TreeDataType Value )
- {
- if ( pRoot == NULL )
- return;
- pSTreeNode pFindNode = Search( pRoot, parentValue );
- if ( pFindNode == NULL )
- return;
- if ( pFindNode->pFirstChild == NULL )
- {
- pFindNode->pFirstChild = new STreeNode( Value );
- return;
- }
- else
- {
- InsertBrother( pFindNode->pFirstChild, Value );
- return;
- }
- }
- // 插入右兄弟节点
- void CTree::InsertBrother( pSTreeNode pBrotherNode, TreeDataType Value )
- {
- if ( pBrotherNode->pNextBrother != NULL )
- InsertBrother( pBrotherNode->pNextBrother, Value );
- else
- {
- pBrotherNode->pNextBrother = new STreeNode( Value );
- return;
- }
- }
- // 查找函数
- pSTreeNode CTree::Search( pSTreeNode pNode, TreeDataType Value )
- {
- if ( pNode == NULL )
- return NULL;
- if ( pNode->data == Value )
- return pNode;
- if ( pNode->pFirstChild == NULL && pNode->pNextBrother == NULL )
- return NULL;
- else
- {
- if ( pNode->pFirstChild != NULL )
- {
- pSTreeNode pNodeTemp = Search( pNode->pFirstChild, Value );
- if ( pNodeTemp != NULL )
- return pNodeTemp;
- else
- {
- return Search( pNode->pNextBrother, Value );
- }
- }
- else
- return Search( pNode->pNextBrother, Value );
- }
- }
- // 前序遍历
- void CTree::Preorder( pSTreeNode pNode )
- {
- if (pNode == NULL)
- return;
- cout <<"" << pNode->data <<" ";
- Preorder( pNode->pFirstChild );
- Preorder( pNode->pNextBrother );
- }
- // 中序遍历
- void CTree::Inorder( pSTreeNode pNode )
- {
- if ( pNode == NULL )
- return;
- Inorder( pNode->pFirstChild );
- cout <<"" << pNode->data <<" ";
- Inorder( pNode->pNextBrother );
- }
- // 后序遍历
- void CTree::postorder( pSTreeNode pNode )
- {
- if ( pNode == NULL )
- return;
- postorder( pNode->pFirstChild );
- postorder( pNode->pNextBrother );
- cout <<"" << pNode->data <<" ";
- }
- // 主函数
- int main()
- {
- CTree* pTree = new CTree( 1 );
- pTree->Insert( 1, 2 );
- pTree->Insert( 1, 3 );
- pTree->Insert( 1, 4 );
- pTree->Insert( 1, 5 );
- pTree->Insert( 1, 6 );
- pTree->Insert( 1, 7 );
- pTree->Insert( 4, 8 );
- pTree->Insert( 5, 9 );
- pTree->Insert( 5, 10 );
- pTree->Insert( 6, 11 );
- pTree->Insert( 6, 12 );
- pTree->Insert( 6, 13 );
- pTree->Insert( 10, 14 );
- pTree->Insert( 10, 15 );
- cout <<"前序遍历:" << endl;
- pTree->Preorder( pTree->pRoot );
- cout <<endl;
- cout << "中序遍历:" << endl;
- pTree->Inorder( pTree->pRoot );
- cout <<endl;
- cout << "后序遍历:" << endl;
- pTree->postorder( pTree->pRoot );
- cout << endl;
- delete pTree;
- pTree = NULL;
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2875508.html